SUNY Geneseo Department of Computer Science

Binary Tree Search

Previous Lecture

Misc

Hand out Homework 2

Lab handout available in labs tomorrow

Questions?

Binary (Search) Trees

Messages

• root()
• left()
• right()
• isEmpty()
• BinaryTree()
• BinaryTree( x, left, right )

Searching a binary search tree

1. Compare data you seek to root
2. If data equals root, stop
3. If data is less than root, repeat in left subtree
4. If data greater than root, repeat in right subtree

Mini-assignment: phrase search w/ tree messages

    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
            // root = x
            return true

x.compareTo(y)

• Wants to return <, =, >
• Really returns int
  • < 0 if x < y
  • = 0 if x = y
  • > 0 if x > y

Does this really work?

• Induction proof on size of tree
  • (or on height of tree)
  • Height = number of levels between root and farthest leaf
• Base case: tree of size 0, i.e., empty tree
  • Algorithm returns false because of "this.isEmpty()" test
  • And x can't be in tree
• Induction hypothesis:
  • Mini-assignment

Next Lecture