Input: 2 RB Trees A B, so that both values in a certain range, so that B's range is smaller than A in both sides. Ex. B's range can be [100...200] and A's range is [0...1000]
Output: Unite A and B to one RB Tree AB.

How can I unite these 2 trees in $O(log(n))$ time and with additional space $O(1)$?

I have tried splitting tree A into 3 trees A1,A2,A3, so that: A1 < A2 , B < A3
A2 contains all that values that are equal-bigger than Min(B) and smaller-equal to Max(B). I did it using the RB Tree Split algorithm, and all the splitting sums up to $O(log(n))$ time.

Now I know what to do with A1 and A3 but what should I do with A2 and B? I know I should use the fact that B contains A2's range but how does it help me?


You can't. As shown by Brown and Tarjan on the first page of "A Fast Merging Algorithm", merging two sequences with overlapping ranges has a worst-case bound of $\Theta (m \lg (n/m))$ comparisons.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.