SUNY Geneseo Department of Computer Science

Building and Searching Ordered Binary Trees

Previous Lecture

Misc

Hand out Lab 11

Questions?

Building and Searching Ordered Binary Trees

Reading summary: sections13.3.3 and 13.3.4

• Constructing ordered tree:
  • Put values less than root in left subtree,
  • Values greater than root in right subtree
• Search:
  • Look at root
  • If value you want is less than root, look in left subtree
  • Else look in right subtree

How do you know these work?

• Proved in reading
• Summary
  • Base case for both: no values in tree, correctness follows vacuously/trivially
  • Induction hypothesis: construction/search is correct for trees of height < H
  • Construction/search correct for height H because either root is result (for search) or if value < root, recursively process left subtree (correct by induction hypothesis, left subtree is correct one to process by sort property), similar argument for right subtree

Try building and searching a tree

Duplicates

• How would you define the "sort property" in order to allow trees to have duplicate values?
  • Roughly, elements in left subtree <= root, root < elements in right subtree, left and right subtrees are sorted
  • Records in database trees usually ordered by "key" field
• Do the insertion and search algorithms in the text work for this definition?
  • Insert doesn't -- inserts second copy to right of first copy
  • Fix by changing "< root" to "<= root" in insert

Next

Performance of insertion and search

Read section 13.3.5

Next Lecture