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)$.

1
2
3
4
5
6
7
8
RB-JOIN'(T[y], x, T[2])
    z.left = T[y]
    z.right = T[2]
    z.parent = T[y].parent
    z.key = x
    if T[y].parent.left = T[y]
        T[y].parent.left = z
    else T[y].parent.right = z

d. Red, because if both the colors of the roots of $T_y$ and $T_2$ are black and the color of $x.parent$ is red, then the color of $x$ is black and it'll change both the colors of the roots of $T_y$ and $T_2$ and recursively adjust to ensure that $\text{BLACK-HEIGHT}$ doesn't change.

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)$.