SUNY Geneseo Department of Computer Science
Analysis
of Tree Search
{Date}
CSci 141, Fall 2003
Prof. Doug Baldwin
Return to
List of Lectures
Previous Lecture
Questions?
Binary Tree Search
boolean search( x )
if this.isEmpty()
return false
else if x.compareTo( this.root() ) > 0
return this.right().search( x )
else if x.compareTo( this.root() ) < 0
return this.left().search( x )
else
return true
Correctness proof
- Theorem: search(x) returns true if x is in tree and returns false if x
not in tree
- Induction on size of tree
- Base case: tree of size of 0, i.e., empty tree
- Algorithm returns false because of "this.isEmpty()" test
- And x can't be in tree
- Induction hypothesis:
- Mini-assignment...
- Assume search(x) returns true if x is in tree and returns false if x
not in tree for trees of k-1 or fewer items (k-1 >= 0)
- Strong induction
- Show search(x) returns true if x is in tree and returns false if x not
in tree for trees of k items
- Tree is not empty because k >= 1
- 3 possibilities
- root = x:
- Search returns true because algorithm falls through to last
"else"
- root > x
- Search recursively in left, which has no more than k-1 items
- Use induction hypothesis, i.e.,...
- Search(x) returns true if x is in left tree and returns false
if x not in left tree
- By search tree ordering, x must be left subtree if in tree at
all
- root < x
- Search recursively in right
- Proof is similar to root > x case
Or prove this by induction on height
- Base case: height 0, i.e., empty tree
- Induction hypothesis: search(x) returns true if x is in tree and returns
false if x not in tree for a tree of height < k (k >= 1)
- Show search(x) returns true if x is in tree and returns false if x not
in tree for tree of height k
- 3 possibilities,
- Apply induction hypothesis to recursive searches in left and right subtrees
How fast is it?
- Count primitive binary tree operations
- Recurrence for primitive tree operations as function of tree's height, h
- Worst case (x < root, and left subtree is height h-1)
- f(h) = 1 if h = 0
- f(h) = 4 + f(h-1) if h > 0
- Closed form: f(h) = 4h + 1
- How does number of items (n) relate to height (h)?
Next Lecture