Java Red-Black Tree Assignment

Part 3: Red-black trees

Left-leaning red-black trees, as they are described in the Sedgewick and Wayne text, undergo 3 possible transformations as they grow: rotateLeft, rotateRight, and flipColors. You may refer to the text or my lecture notes for the details of each of these tree transformations.

In red-black tree diagrams, you will see 2 ways to represent color. In the first, edges are colored, either red or black. In the other version, color information is stored within each node, and edges are not colored. In this second version, the root of the tree is always black. We will use the second version, in which nodes have color, to draw red-black trees.

1. Draw the red-black tree that is equivalent to the 2-3 tree from problem 3 of the last section, prior to the insertions of O and P.

2. Show the results of adding E and then D to the tree below. If you wish, you may draw intermediate trees, showing the transformations that occur. Or, you may draw just 1 tree, reflecting the final state of the tree after both insertions are complete.

Show the results of adding K to the tree below. If you wish, you may draw intermediate trees, showing the transformations that occur. 3. 4. Draw the 2-3 tree that is equivalent to the last red-black tree you drew for problem 3