Red Black Trees

Assignment

1. Show what a red-black tree would look like after each of the following insertions: 10, 20, 5, 7, 8, 4, 3, 2, 1.
2. Show the smallest red-black tree possible where inserting an item into it causes case 1' (that's the mirror of case 1) to be put into action. Show the tree both before and after the insertion.
3. Repeat the above question for case 2'.
4. Repeat the above question for case 3'.
5. Show a red-black tree where inserting a node into a red-black tree causes first one of the six cases to be applied and then the new current node requires yet another one of the six cases to be applied. Show the original tree, the tree after the first case applies, and the final tree after both cases have been applied.

   ---

   What to Submit

   • Hand in a sheet of paper with answers to the above questions.

   ---

   John Paxton
   Last Modified: November 29, 1999