# Shared Flashcard Set

## Details

Data Structures and Algorithms Midterm 1
CSE 373
10
Computer Science
10/17/2011

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 O-bound 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 O-bound 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 O-bound 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
 min = 1 max = 2^d
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
 FALSE
Supporting users have an ad free experience!