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

C++
1
2
3
4
5
6
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)\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用