For top-down deletion from a leaf, we note that if the leaf from which the deletion is to occur is the root, then the result is an empty red-black tree. If the leaf is connected to its parent by a red pointer then it is part of a 3-node ora 4-node. a~d the leaf may be deleted from the tree. If the pointer from the parent to the leaf is a black pointer then the leaf I is a 2-node. Deletion from a 2-node requires a backward restructuring pass. To avoid this, we ensure that the deletion leaf has a red pointer from its parent. This is accomplished by using the insertion transformations in the reverse direction, together with red-black transformations corresponding to the 2-3-4 deletion transformations (3) and (4) tq is a 2-node whose nearest sibling is a 3- or 4-node). and a 3-node transformation that switches from one 3-node representation to the other as necessary to ensure that the search for the element to be deleted moves down a red pointer.

Since most of the insertion and deletion transformations can be accomplished by color changes and require no pointer changes or data. shifts, these operations take less time using red-black trees than when a 2-3-4 tree is represented using nodes of type Two34Node. The development of the bottom-up deletion transformations is left as an exercise.

**Joining and Splitting Red-Black Trees**

In Section 5.7.5. we defined the following operations on binary search trees: Three way·· Join, Twoway.Ioin, and Sput . Each of these can be performed in logarithmic time nil red-black trees. The operation CThree WayJoin (A, .r, B) can be performed as follows

**Case 1:**

If A and B have the same rank (see properties Ql to Q5), then let C be constructed by creating a new root with data data member x; color data members black; LejrChild data member A; and Righttlhild data member B. The rank of C is one more than the ranks of A and B.C8S~ 2: If rank (A) > rank (8), then follow RightChild pointers from A to the first node Y that has rank equal to rank (B). Properties Ql to Q5 guarantee the existence of such a node. Let p (Y) be the parent of Y. From the definition of Y, it follows that rank (p (Y» = rank (Y) + 1. Hence, the pointer from p (Y) to Y is a black pointer. Create a new node, Z, with data data member x; color data members black; LeftChild Y (i.e., node Yand its subtrees become the left subtree

of Z); and RightChild B. Z is made the right child of p (Y), and the link from p (Y) to Z has color red. Note that this transformation does not change the number of black pointers on any root-to-extemal-node path. However, it may cause the path from the root to Z to contain two consecutive red pointers. If this happens, then the transformations used to handle this in a bottom-up insertion are performed. These transformations may increase the rank of the tree b)’ one. Case 3: The case rank (A) < rank (B) is similar to Case 2 .

**Analysis of join**

The correctness of the function just described is easily established.

Case I takes O( I) time; each of the remaining two cases takes 0(1rank (A) – rank (B) I)

time under the assumption that the rank of each red-black tree is known prior to computing

the join. Hence, a three-way join can be done in O(log n) time, where n is the

number of nodes in the two trees being joined. A two-way join can be performed in a

similar manner. Note that there is no need- to add parent data members to the nodes to

perform a join, as the needed parents can be saved on a stack as we move from the root

to the node Y

We now turn our attention to the split operation. Assume for simplicity that the splitting key. i, is actually present in the red-black tree A. Under this assumption, the split operation A. Split (i, B, ,X, C) can be performed as in Program 10.10.

**Step 1:** Search A for the node P that contains the record with key i. Copy the record to the reference parameter x. Initialize Band C to be the left and right subtrees of P, respectively.

**Step 2:**for (Q = parem(P);Q;P = Q, Q == parent(Q)) if( P == Q~LefIChild) C.ThreeWayJoin(C. Q~data. Q~RighlChild) else B.ThreeWayJoilllQ~LefIChild. Q~data. B);

We first locate the splitting element, .r, in the red-black tree. Let P be the node that contains this element. The left subtree of P contains elements with key less than i. B is initialized to be this subtree. All elements in the right subtree of P have a key larger than

i, and C is initialized to be this subtree. In Step 2, we trace the path from P to the root of the red-black tree A. During this traceback, two kinds of subtrees are encountered. One of these contains elements with keys that are larger than i as well as all keys in C. This happens when the traceback moves from a left child of a node to its parent. The other kind of subtree contains elements with keys that are smaller than i, as well as smaller than all keys in B. This happens when we move from a right child to its parent. In the former case a three-way join with C is performed, and in the latter a three-way join with ‘B is performed. One may verify that the two-step procedure outlined here does indeed implement the split operation for the case when i is the key of a record in the tree A. It is easily extended to handle the case when the tree A contains no record with key i.

**Analysis of split:**

Call a node red if the pointer to it from its parent is red. The root and

all nodes that have a black pointer from their parent are black. Let r (X) be the rank of node X in the un split tree. First we shall show that during a split, if P is a black node in the unsplit tree. and Q _ O. then

**EXERCISES**

1. (a) Show that every binary tree’ obtained by transforming a 2-3-4 tree as described in the text satisfies properties Q1to Q5.

(b) Show that every binary tree that satisfies properties Ql to Q5 represents a 2-3-4 tree and can be obtained from this 2-3-4 tree using the transformations of the text.

2. Write a function to convert a 2-3-4 tree into its red-black representation. What is the time complexity of your function? .

3. Write a function to convert a red-black tree into its 2-3-4 representation. What is the time complexity of your function?

4. Let T be a red-black tree with rank r. Write a function to compute the rank of each node in the tree. The time complexity of your function should be linear in the number of nodes in the tree. Show that this is the case.

5. Compare the worst-case height of a red-black tree with n nodes and that ‘of an AVL tree with the same number of nodes.

6. Rewrite function Two 34::/nsert (Program 10.9) so that it inserts an element into a 2-3-4 tree represented as a red-black tree.

7. Obtain the symmetric transformations for Figures 10.33Jrnd 10.34.

8. Obtain a function to delete an element y from a 2-3-4 tree represented as a redblack tree. Use the top-down method. Test the correctness of this function by running it on a computer. Generate your own test data.

9. Do the previous exercise using the bottom-up method.

10. The number of color data members in a node of a red-black tree may be reduced to one. In this case the color of a node represents the color of the pointer (if any) from the node’s parent to that node. Write the corresponding insert and delete functions using the top-down approach. How would this change in the node structure affect the efficiency,of the insert and delete functions?

11. Do the previous exercise using the bottom-up approach.

12. (a) Use the strategy described in this section to obtain a C++ function to compute a three-way join. Assume the existence of a function rebalance (X) that performs the necessary transformations if the tree pointer to node X is the second of two consecutive red pointers. The complexity of-this function may be assumed to be O(level (X».

(b) Prove the correctness of your function.

(c) What is the time complexity of your function?

13. Obtain a function to perform a two-way join on red-black trees. You may assume the existence of functions to search, insert, delete, and perform a three-way join. What is the time complexity your two-way join function?

14. Use the strategy suggested in Program 10.10 to obtain a C++ function to perform the split operation in a red-black tree T. The complexity of your algorithm must be O(height (T». Your function must work when the splitting key i is present in T and when it is not present in T.

15. Complete the complexity proof for the split operation by showing that whenever Q has a black child, the total work done in Step 2 of the splitting algorithm from initiation to the time that Q reaches the current node is O(r(Q».

16. Program the search, insert, and delete operations for AVL trees, 2-3 trees, 2-3-4 trees, and red-black trees.

(a) Test the correctness of your functions.

(b) Generate a random sequence of n inserts of distinct values. Use this sequence to initialize each of the data structures. Next, generate a random sequence of searches. inserts, and deletes. In this sequence, the probability of a search should be 0.5, that of an insert 0.25, and that of a delete 0.25. The sequence length is m. Measure the time needed to perform the II! operations in the sequence using each of the above data structures.

(c) Do part (b) for n = 100. 1000, 10,000, and ]00,000 and II! = n, 2n, and 4n.

(d) What can you say about the relative performance of these data structures?