13-2 Join operation on red-black trees

The join operation takes two dynamic sets $S_1$ and $S_2$ and an element $x$ such that for any $x_1 \in S_1$ and $x_2 \in S_2$, we have $x_1.key \le x.key \le x_2.key$. It returns a set $S = S_1 \cup \{x\} \cup S_2$. In this problem, we investigate how to implement the join operation on red-black trees.

a. Given a red-black tree $T$, let us store its black-height as the new attribute $T.bh$. Argue that $\text{RB-INSERT}$ and $\text{RB-DELETE}$ can maintain the $bh$ attribute without requiring extra storage in the nodes of the tree and without increasing the asymptotic running times. Show that while descending through $T$, we can determine the black-height of each node we visit in $O(1)$ time per node visited.

We wish to implement the operation $\text{RB-JOIN}(T_1, x, T_2)$, which destroys $T_1$ and $T_2$ and returns a red-black tree $T = T_1 \cup \{x\} \cup T_2$. Let $n$ be the total number of nodes in $T_1$ and $T_2$.

b. Assume that $T_1.bh \ge T_2.bh$. Describe an $O(\lg n)$-time algorithm that finds a black node $y$ in $T_1$ with the largest key from among those nodes whose black-height is $T_2.bh$.

c. Let $T_y$ be the subtree rooted at $y$. Describe how $T_y \cup \{x\} \cup T_2$ can replace $T_y$ in $O(1)$ time without destroying the binary-search-tree property.

d. What color should we make $x$ so that red-black properties 1, 3, and 5 are maintained? Describe how to enforce properties 2 and 4 in $O(\lg n)$ time.

e. Argue that no generality is lost by making the assumption in part (b). Describe the symmetric situation that arises when $T_1.bh \le T_2.bh$.

f. Argue that the running time of $\text{RB-JOIN}$ is $O(\lg n)$.

a.

• Initialize: $bh = 0$.
• $\text{RB-INSERT}$: if in the last step the root is red, we increase $bh$ by $1$.
• $\text{RB-DELETE}$: if $x$ is root, we decrease $bh$ by $1$.
• Each node: in the simple path, decrease $bh$ by $1$ each time we find a black node.

b. Move to the right child if the node has a right child, otherwise move to the left child. If the node is black, we decease $bh$ by $1$. Repeat the step until $bh = T_2.bh$.

c. The time complexity is $O(1)$.

RB-JOIN'(T[y], x, T[2])
    TRANSPLANT(T[y], x)
    x.left = T[y]
    x.right = T[2]
    T[y].parent = x
    T[2].parent = x

d. Red. Call $\text{INSERT-FIXUP(T[1], x)}$.

The time complexity is $O(\lg n)$.

e. Same, if $T_1.bh\le T_2.bh$, then we can use the above algorithm symmetrically.

f. $O(1) + O(\lg n) = O(\lg n)$.