World's most popular travel blog for travel bloggers.

Conditional RB Tree union

, , No Comments
Problem Detail: 

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?

Asked By : Trinarics
Answered By : jbapple

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback