The join operation takes two dynamic sets S₁ and S₂ and an element x such that for any x₁ ∈ S₁ and x₂ ∈ S₂, we have x₁.key ≤ x.key ≤ x₂.key. It returns a set S = S₁ ⋃ {x} ⋃ S₂. 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 RB-INSERT and 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 RB-JOIN (T₁, x, T₂), which destroys T₁ and T₂ and returns a red-black tree T = T₁ ⋃ {x} ⋃ T₂. Let n be the total number of nodes in T₁ and T₂.

b. Assume that T₁.bh ≥ T₂.bh. Describe an O(lg n)-time algorithm that finds a black node y in T₁ with the largest key from among those nodes whose black height is T₂.bh.

c. Let Ty be the subtree rooted at y. Describe how Ty ⋃ {x} ⋃ T₂ can replace Ty 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₁.bh ≤ T₂.bh.

f. Argue that the running time of RB-JOIN is O(lg n).