ITEC 122 2007fall ibarland

home—info—lectures—hws—exams

tree-height-struct-induct
structural induction
tree height vs size

abstract class Tree { /* ... */ }

class EmptyTree extends Tree {
  int size() { return 0; }
  int height() { return 0; }
  }
    
class Branch extends Tree {
  Tree left;
  Tree right;
  String data;
  
  int size() { return 1 + this.left.size() + this.right.size(); }
  int height() { return 1 + Math.max( this.left.height(), this.right.height() ) ; }
}

Let P be a statement indexed by trees (instead of indexed by numbers like in our previous induction proofs)

P(t) = “t.size() < 2^t.height()”.

1. EmptyTree case: Let et be an EmptyTree.
   1. Then P(et) = “et.size() < 2^et.height()”.
   2. By looking at the code for EmptyTree, we see that this translates to 0 < 2⁰=1, which is true.
2. Branch case: Let b be any Branch.
   3. Our inductive hypothesis is P(b.left)∧P(b.right). That is, b.left.size() < 2^{b.left.height()} and b.right.size() < 2^{b.right.height()}
   4. We need to show, in the inductive step, P(b). That is, we need to show b.size() < 2^b.height().
   5. Inductive step:
      b.left.size() < 2^{b.left.height()} (inductive hypothesis)
      b.right.size() < 2^{b.right.height()} (inductive hypothesis)
      b.right.size() +1 ≤ 2^{b.right.height()} (since both sides are integers, the amount of the inequality is at least 1)
      b.left.size() + b.right.size() + 2 ≤ 2^{b.left.height()} + 2^{b.right.height()} (adding two inequalities only strengthens it).
      (1+b.left.size() + b.right.size()) +1 ≤ 2^{b.left.height()} + 2^{b.right.height()} (algebra)
      b.size()+1 ≤ 2^{b.left.height()} + 2^{b.right.height()} (def'n of b.size())
      b.size()+1 ≤ 2^{max(b.left.height(), b.right.height())} + 2^{max(b.left.height(), b.right.height())} (increasing the exponent will not weaken the inequality)
      b.size()+1 ≤ 2·2^{max(b.left.height(), b.right.height())} (algebra)
      b.size()+1 ≤ 2^{1+max(b.left.height(), b.right.height())} (algebra)
      b.size()+1 ≤ 2^b.height() (by code for height)
      b.size() < 2^b.height() (re-convert the ≤ to < by subtracting 1 from the left side.)
   6. Thus we have shown by structural induction that whether t is an EmptyTree or a Branch, P(t) holds whenever P holds for all sub-Trees of t. Thus by structural induction, we conclude ∀t.P(t).

home—info—lectures—hws—exams

©2007, Ian Barland, Radford University Last modified 2007.Oct.30 (Tue)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu