Java Binary search trees, Two-three trees, red-black trees homework

Part 2: Two-three trees

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.

Part 1: Binary Search Trees H N I M A H K QZ 1. Considering binary search tree (a), give (i) the root, (ii) the root's children, ii) the leafs, (iv) the depth of the each leaf, (v) the height of I, and (vi) the height of the tree. Show the state of tree (a) after the following sequence of items have been added: E, N, o, sequence of insertions (which should have 12 nodes), or drawing up to 5 trees which reflect 2. D, C. You have a choice between drawing just one tree which resulits from the entire intermediate results. Show the state of tree (b) after the following sequence of items have been removed: G, H, J, N, M. You have a choice between drawing just one tree which results from the entire sequence of deletions (the tree should have 7 nodes left), or drawing up to 5 trees which 3. reflect intermediate results