SUNY Geneseo Department of Computer Science

Ordered Trees

Previous Lecture

Questions?

Typo? Last line on page 439 should read "...or is in each of T-prime's children..."

Ordered Trees

Section 13.3 through 13.3.4

Binary trees can maintain sorted collections

• Search
• Visit every item in order in no more than Θ(n) time

"Inorder" property:

• Left subtree holds values less than root
• Right subtree has values greater than root

Inductions on height of tree

Proof by contradiction

Traverse algorithm visits no node twice and makes exactly n visits

Moral: trees can support fast "database" operations

• ... and ability to order trees is key to doing it

Algorithms for adding an item (insertion) and finding an item (search)

Start inserting from greatest element

What sort of induction do the proofs in this reading use?

• All strong inductions (on height)
• Strong inductions are common with trees, because neither of the multiple recursive sub-structures of a size-k tree reliably has size exactly k-1.

Performance Analysis of Simple Tree Algorithms

    traverse()
        if ! this.isEmpty()
            this.getLeft().traverse()
            process this.getRoot()
            this.getRight().traverse()

How would you derive the number of primitive tree messages this sends to traverse a tree of n items?

Recurrence relation

• f(n) = 1 if n = 0
• f(n) = 4 + f(size of left subtree) + f(size of right subtree)
  • = 4 + f(n1) + f(n2) if n > 0
  • (Note: n1 + n2 = n-1)

Observation: actual distribution of n1 and n2 doesn't seem to matter

• So: assume some easy distribution (e.g., n1 = n2 = (n-1)/2, or n1 = n-1 and n2 = 0)
• Solve recurrence for that easy case
• And then prove solution works for the general recurrence

Mini-assignment: find closed form for an "easy" version of recurrence

Next Lecture