13. Red-Black Trees

Exercises

13.1-1

Red-black tree of black-height 2. The image was produced with the data structure visualizations tool.

If you color the nodes 4 and 12 into black (children of the root node 8), then the resulting tree will have black-height of 3. If you color all nodes into black, then you will get a tree of black-height 4.

13.1-2

The node 36 would be placed as the right child of red node 35 in Figure 13.1 (see the book). Sure, this will not be a legal red-black tree. It cannot be colored red, as property 4 would be violated. It cannot be colored black neither, since property 5 would be violated; from node 38 there would be two simple paths toward descendant leaves with different numbers of black nodes.

Correct red-back tree after inserting node 36 into the tree from Figure 13.1. The image was produced with the data structure visualizations tool.

13.1-3

Available in the latest revision of the IM.

13.1-4

Available in the latest revision of the IM.

13.1-5 🌟

Shows that the longest simple path from a node $x$ in a red-black tree to a descendant leaf has length at most twice that of the shortest simple path from node $x$ to a descendant leaf.

Available in the latest revision of the IM.

13.1-6

Available in the latest revision of the IM.

The formulas in the IM are wrong, since they also count NIL leaves (external nodes). The largest possible number of internal nodes in a red-black tree with black-height $k$ is $2^{2k}-1$, whilst the smallest possible number is $2^k-1$.

13.1-7

Available in the latest revision of the IM.

13.1-8 🌟

Proves that in a red-black tree, a red node cannot have exactly one non-NIL child.

Available in the latest revision of the IM.

13.2-1

Available in the latest revision of the IM.

13.2-2

Available in the latest revision of the IM.

13.2-3

Available in the latest revision of the IM.

13.2-4 🌟

Shows that any arbitrary $n$-node binary search tree can be transformed into any other arbitrary $n$-node binary search tree using $O(n)$ rotations.

Available in the latest revision of the IM.

★ 13.2-5

Available in the latest revision of the IM.

The solution in the IM has a minor error in the proof that doesn't impact the end result. Namely, the expansion of $(n-k-1)^2=n^2-2kn-2n+k^2+2k+1$ contains the $2k$ term, while the text in the IM has $k$.

13.3-1

Available in the latest revision of the IM.

13.3-2

Use the data structure visualizations tool and watch the resulting tree as you insert the nodes. You can adjust the animation speed to clearly see the re-colorings and rotations.

13.3-3

Available in the latest revision of the IM.

13.3-4

Available in the latest revision of the IM.

13.3-5

Available in the latest revision of the IM.

13.3-6

Observe that all nodes accessed via parent pointers in RB-Insert-Fixup are exactly those that are encountered by RB-Insert while finding the location for the new node. Therefore, RB-Insert should store them in a stack, initialized with the sentinel T.nil. RB-Insert-Fixup would pop and push nodes from this stack, as needed. The procedures for rotations would need to receive an additional parameter, the rotated node's parent.

The size of this stack will be commensurate with the height of a RB tree, which is $O(\lg n)$. Pushing and popping nodes execute in $O(1)$ time, so the asymptotic runtime of RB-Insert would remain the same.