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?