Question: The join operation takes two dynamic sets S 1 and S 2 and an element x such that for any x 1 S 1
The join operation takes two dynamic sets S1 and S2 and an element x such that for any x1 ∈ S1 and x2 ∈ S2, we have x1.key ≤ x.key ≤ x2.key. It returns a set S = S1 ⋃ {x} ⋃ S2. 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 (T1, x, T2), which destroys T1 and T2 and returns a red-black tree T = T1 ⋃ {x} ⋃ T2. Let n be the total number of nodes in T1 and T2.
b. Assume that T1.bh ≥ T2.bh. Describe an O(lg n)-time algorithm that finds a black node y in T1 with the largest key from among those nodes whose black height is T2.bh.
c. Let Ty be the subtree rooted at y. Describe how Ty ⋃ {x} ⋃ T2 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 T1.bh ≤ T2.bh.
f. Argue that the running time of RB-JOIN is O(lg n).
Step by Step Solution
3.45 Rating (161 Votes )
There are 3 Steps involved in it
a The blackheight of a redblack tree is defined as the number of black nodes on the path from the root to a leaf not counting the leaf itself The blackheight of a leaf is considered to be 0 Maintainin... View full answer
Get step-by-step solutions from verified subject matter experts
Study Help