Term
What is the minimum and maximum number of nodes in a complete binary tree of height h? 

Definition
min = 2^h
max = 2^(h+1)  1 


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

Definition
min = 2^(h+1) 1
max = 2^(h+1)  1 


Term
What is the AVL balance property? 

Definition
At every node, the height of its left subtree differs from the height of its right subtree by
no more than 1. 


Term
Give a Obound on the worst case running time for: inserting in an AVL tree of size n? 

Definition
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). 


Term
Give a Obound on the worst case running time for: deleteMin in a binary min heap of size n? 

Definition
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 


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

Definition
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. 


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

Definition


Term
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? 

Definition
min = 2^h  1
max = 2^h  1 


Term
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. 

Definition

