CS410, Summer 1998
Quiz #4
July 7
							Name:
Consult no sources.

[Answers included with the questions]

1. Why are we learning red-black trees instead of just using the
ordinary BST's we learned on Monday?

A red-black tree has height O(log n) whereas an ordinary BST may have height
as large as n.  Since all our standard BST operations take time proportional
to the height, this is a much better worst-case guarantee.


2. Finish this diagram of a right rotation by labelling the subtrees
A, B, C on the right of the arrow.

                |                       |
                y                       x
              /  \      =========>     / \
             x   C                    A   y
           /  \                          / \
           A  B                         B   C

3. One of these binary trees can be colored to be a red-black tree and
   the other cannot.  Color the one that can and explain why the other cannot:

         O                             *
        / \                           / \ 
       O   O                         O   *
          / \                       / \   \
         O   O                     *   *   O
        /   / \                         \
       O   O   O                         O
              /   
             O

   The one on the left cannot be colored because the paths vary in length from
   2 to 5 and in red-black trees the heights can vary by only a factor of 2.



4. Insert 5 into the red-black tree below:

	10 *
       /  \
      9 O  12 *
     /
    4 *
     \
      5 O
(No rebalancing is necessary since the parent of the new node is black.)

Grading:
1. Two points for explaining the O(log n) guarantee.
2. Two points, no partial credit.
3. Four points: one point for correctly identifying which can be colored,
		one point for explaining why the uncolorable is uncolorable,
		two points for coloring the colorable
			(one point if just messed up the length 2 path)
4. Two points, 1/2 point for inserting in the right place but not doing
   the red black part correctly.