SUNY Geneseo Department of Computer Science

Analyzing Tree Traversals

Previous Lecture

Misc

Hand out Lab 12

Questions?

Performance Analysis of Tree Traversal Algorithms

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

Recurrence

• f(n) = 1 if n = 0
• f(n) = 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
• Prove solution works for the general recurrence

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

• f(n) = 5n + 6?
  • Via table/examples
• Change recurrence to
  • f(n) = 4 + f(n-1) if n > 0
  • f(n) = 1 if n = 0
  • Then f(n) = 4n + 1 (from "kn+c" rule)
• But!
  • Assuming n1 = n-1 implies n2 = 0
  • f(n) = 4 + f(n-1) + f(0)
    • = 4 + f(n-1) + 1
    • = 5 + f(n-1) if n > 0
  • So f(n) = 5n + 1

Proofs: induction on n

• 5n + 6 fails base case right away
• 5n + 1:
  • Base case, n = 0
    • f(n) = 1 = 5 * 0 + 1
  • Induction hypothesis
    • f(k-1) = 5(k-1) + 1
  • Show f(k) = 5k + 1
    • f(k) = 5 + f(k-1) f/ recurrence
    • = 5k - 4 + 5
    • = 5k + 1
• But need to prove that the original recurrence with n1 and n2 has closed form f(n) = 5n + 1
  • Strong induction on n
  • Base case, n = 0, as above
  • Induction hypothesis: assume f(x) = 5x + 1 for all x < k
  • Show f(k) = 5k + 1
    • f(k) = 4 + f(k1) + f(k2) where k1 + k2 = k-1
    • Therefore k1 < k, k2 < k
    • f(k) = 4 + 5k1 + 1 + 5k2 + 1 f/ induction hypothesis
    • = 4 + 5(k1+k2) + 1 + 1
    • = 4 + 5(k-1) + 1 + 1 since k1 + k2 = k - 1
    • = 5 + 5k - 5 + 1
    • = 5k + 1

What if we tried n1 = n2 = (n-1)/2?

• f(n) = 4 + f( (n-1)/2 ) + f( (n-1)/2 )
  • = 4 + 2f( (n-1)/2 )
• You could solve this by looking for patterns and proving, although exponential and/or logarithmic terms might creep in to the analysis.

Performance of Search-Style Algorithms

Section 13.3.5 (read this for Wednesday)

    search( x )
        if this.isEmpty()
            return false
        else if x == this.getRoot()
            return true
        else if x < this.getRoot()
            return this.getLeft().search( x )
        else
            return this.getRight().search( x )

Next Lecture