min = 2^h

max = 2^(h+1) - 1

 What is the minimum and maximum number of nodes in a perfect binary tree of height 

h?

min = 2^(h+1) -1 

max = 2^(h+1) - 1

At every node, the height of its left subtree differs from the height of its right subtree by 

no more than 1.

Give a O-bound on the worst case running time for:  inserting in an AVL tree of size n?

worst case: O(log n)

AVL trees are balanced, and a new element goes at the fringe, so this must take take logarithmic time 

(best, average, worst, or any other case). Some of you suggested that we might get lucky and find a 

NULL child high in the tree where the new element should go. However, if such a NULL child 

existed, its parent would be out of balance (one child has large height, the other has 

height of –1).

worst case: O(log2 n). At worst, the new root percolates down to the bottom, and a binary min heap 

has at most log2 n  levels.  At each level must compare with 2 children to decide if need to 

percolate down and if so which one to swap with

Give a O-bound on the worst case running time for: Floyd’s buildHeap to build a binary heap of n elements?

worst case: O(n)

This was discussed in class and is proven in the text. We check n/2 elements, and most of them can only percolate a small number of  steps down.  

What is the minimum and maximum number of nodes at depth d in a complete binary tree?

min = 1

max = 2^d

What is the minimum and maximum number of nodes in the right subtree of the root of a perfect binary tree, where the height of the entire tree (not the subtree) is h and h ≥1? 

min = 2^h - 1

max = 2^h - 1

TRUE or FALSE: Given an AVL tree containing 31 nodes, after inserting the 32nd value, it is possible that we might have to do three or more rotations in order to maintain the balance property.