CPSC 220 Fall 2007
HW 12: Red-Black Trees

1. Carefully read section 13.6 in L&C, except the last part on element removal.

2. Do exercise 13.5 in L&C. Be sure to show the red-black tree you get from adding the given elements in the order shown using the algorithm discussed in the chapter.

3. Both AVL trees and red-black trees are balanced binary search trees, and both guarantee that an N-element tree will have height O(log N).
   1. Which type of tree is "more" balanced, that is, which is stricter in its balance requirements?

   2. Of the three binary search tree operations (insertion, deletion, and search), which one(s) are made more efficient by the stricter balance requirement? Why? Compare it to the balanced tree with the less strict balance requirement, not to a regular binary search tree.

   3. Which operation(s) are made less efficient by the stricter balance requirement? Why? Again, compare to the other balanced tree, not to a regular binary search tree.