CSC 311: Data Structures

(Fall 2007)

Assignment 4: Chapter 10

Due by December 4 , Thursday, 2007

All questions are equally scored.

1. How many different binary search trees can store the keys {1, 2, 3, 4}? How many different AVL trees can the keys {1, 2, 3, 4}?

2. Consider the sequence of keys {5, 16, 22, 45, 2, 10, 18, 30, 50, 12, 1}. Draw the result of inserting entries with these keys (in the given order) into

a. An initially empty (2, 4) tree.

b. An initially empty red-black tree.

3. Consider a tree T storing 100,000 entries. What is the worst-case height of T in the following cases?

a. T is a binary search tree.

b. T is an AVL tree.

c. T is a red-black tree.

d. T is a (2, 4) tree.

4. Explain how to use an AVL tree or a red-black tree to sort n comparable elements in O(nlogn) time in the worst case.

5. Show that the nodes of any AVL tree T can be colored “red” and “black” so that T becomes a red-black tree.