5.6.2 Red-Black Trees

1.

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

2.

Draw the complete binary search tree of height 3 on the keys {1, 2, ^... , 15}. Add the NIL leaves and colour the nodes in three different ways such that the black-heights of the resulting red-black trees are 2, 3, and 4.

3.

Show the red-black trees that result after successively inserting the keys 41, 38, 31, 12, 19, 8 into an initially empty red-black tree. Now show the RB trees that result from the successive deletion of the keys in the order 8, 12, 19, 31, 31, 38, 41.

4.

Suppose that a node x is inserted into an RB tree and then immediately deleted. Is the resulting RB tree the same as the initial RB tree? Justify your answer.

5.

Construct the RB-trees that result by repeated insertions in each of the following cases, starting from an initially empty tree.

(a)

1, 2,..., 15

(b)

8, 4, 12, 6, 14, 2, 10, 7, 11, 5, 9, 3, 8, 1, 15

(c)

1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, 8