HW 12: Red-Black Trees

- Carefully read section 13.6 in L&C, except the last part on element
removal.
- 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.
- 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).
- Which type of tree is "more" balanced, that is, which is stricter in its
balance requirements?
- 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.
- 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.

- Which type of tree is "more" balanced, that is, which is stricter in its
balance requirements?