Chapter 6 - Heap and Tree Proofs

Note that tree here means binary tree.

A complete tree is a full tree.

 

1. There are at most 2^h leaves in a binary tree of height h. That is the nodes at the bottom level.

   Base

   h=1, no more than 2¹ = 2 leaves since a binary tree

   IH

   Assume there are at most 2^h-1 leaves in binary trees of height h-1 or less.

   Show

   At most 2^h leaves in a binary tree of height h.

   Induction

   By IH a tree of height h-1 would have at most 2^h-1 leaves.

   The height of the tree can be extended from h-1 to h by adding the maximum number of siblings (2) at each of the 2^h-1 leaves.

   Since there are at most 2^h-1 leaves extended to a maximum of 2 siblings, there are at most 2*2^h-1 = 2^h leaves in a binary tree of height h.

    

2. A complete binary tree of height d has 2^d leaf nodes.

   Base: d=0, has 2⁰ =1 leaf nodes

   IH:    For height d there are 2^d leaf nodes.

   Show:

   For height d+1 there are 2^d+1 leaf nodes.

   Induction:

   By IH for height d there are 2^d leaf nodes.

   Extending tree to height d+1 requires adding 2 siblings to each of 2^d leaf nodes, 2*2^d siblings.

   For height d+1 there are 2*2^d = 2^d+1 leaf nodes.

    

3. A complete tree of height h has 2^h−1 non-leaf nodes.

   Note that a tree of height h has levels at depth 0 to h.

   Base:

   h=1, has 2¹−1 = 1 non-leaf nodes

   IH:   

   Assume a complete tree of height h-1 has 2^h-1−1 non-leaf nodes.

   Induction:

   By IH a complete tree of height h-1 has 2^h-1−1 non-leaf nodes.

   By Problem 2 a complete tree of height h-1 has 2^h-1 leaf nodes.

   Extending to height h requires adding 2 siblings to each of 2^h-1 leaf nodes, making them non-leaf nodes of a height h tree.

   Summing the 2^h-1 − 1 non-leaf nodes for a height h-1 tree and the 2^h-1 nodes added by extending the leaves to make a height h tree yields:

   2h-1 Previously leaf nodes

   +

   2h-1 − 1 Previously non-leaf nodes

   = 2h−1 non-leaf nodes.

   Another solution is to sum the non-leaf nodes of a tree of height h:

   2⁰+2¹+2²+...+2^h-1 = = 2^h-1

    

4. Show that a complete tree of height h has 2^h+1−1 nodes.

   By Problem 2 a complete tree of height h has 2^h leaf nodes.

   By Problem 3 a complete tree of height h has 2^h−1 non-leaf nodes.

   The sum of the nodes is: 2^h + 2^h−1 = 2^h+1−1
   

    

5. Show that an n-node heap tree has height h = ⌊ lg n ⌋.

   By Problem 4, a complete tree of height h has at most 2^h+1−1 nodes.

   An incomplete tree of height h as few as 2^h − 1 + 1 = 2^h nodes.

   One more than a complete tree of height h-1 which has 2^h−1 nodes.

   Then

   2^h ≤ n ≤ 2^h+1−1 < 2^h+1

   so h ≤ lg n < h+1.

   Since h is an integer, h = ⌊ lg n ⌋, by definition of  ⌊ ⌋.

   Important because if we can perform operations (insert, delete, update) proportional to the height, these operations run in logarithmic time.

    

6. Show that, with the array representation for storing an n-element heap, the index of the non-leaf nodes are at most ⌊ n/2 ⌋.

   If the number of non-leaf nodes is more than ⌊ n/2 ⌋  then the right child of the last non-leaf node would lie outside the boundary of the heap (its array index would be greater than n = 2* ⌊ n/2 ⌋ + 1, which is greater than n), a contradiction.

   Hence the index of the non-leaf nodes are at most ⌊ n/2 ⌋. That is all parent nodes are indexed from 1 .. ⌊ n/2 ⌋.

    

7. Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by ⌊ n/2 ⌋ + 1,  ⌊ n/2 ⌋ + 2, ..., n.

   In the array representation of a heap, all non-leaf nodes are stored before leaf nodes.

   Problem 6 has shown that the index of the non-leaf nodes are at most ⌊ n/2 ⌋.

   Also, by definition, the parent of node n is ⌊ n/2 ⌋, parents cannot be leaf nodes.

   Thus  ⌊ n/2 ⌋ cannot be a leaf node.

   Hence there are exactly ⌊ n/2 ⌋ non-leaf nodes and therefore the leaves are indexed by ⌊ n/2 ⌋ + 1,  ⌊ n/2 ⌋ + 2, ..., n.