CODEWITHSUNDEEP
algorithmdata-structurestreered-black-tree
T.Meyer
T.Meyer

Reputation: 55

Best way to join two red-black trees

The easiest way is to store two trees in two arrays, merge them and build a new red-black tree with a sorted array which takes O(m + n) times.

Is there an algorithm with less time complexity?

Upvotes: 3

Views: 8070

Answers (3)

user13557576
user13557576

Reputation:

I think that if you have a generic Sets (so generic red-black tree) you can't choose the solution which was suggested @Sam Westrick. Because he assumes that all elements in the first set are less then the elements in the second set. Also into the Cormen (the best book to learn algorithm and data structures) specifies this condition to join two red-black tree.

Upvotes: 0

Sam Westrick
Sam Westrick

Reputation: 1286

You can merge two red-black trees in time O(m log(n/m + 1)) where n and m are the input sizes and, WLOG, m ≤ n. Notice that this bound is tighter than O(m+n). Here's some intuition:

  • When the two trees are similar in size (m ≈ n), the bound is approximately O(m) = O(n) = O(n + m).
  • When one tree is significantly larger than the other (m ≪ n), the bound is approximately O(log n).

You can find a brief description of the algorithm here. A more in-depth description which generalizes to other balancing schemes (AVL, BB[α], Treap, ...) can be found in a recent paper.

Upvotes: 4

Flika205
Flika205

Reputation: 552

Due to the fact that you need to compare each element in both m and n Red-Black Trees, you will have to deal with a minimum of O(m+n) time complexity, there's a way to do it O(1) space complexity, but that is something else which has nothing to do with your qu. if you are not iterating and checking each element in each Red-Black Tree, you cannot guarantee that your new Red-Black Tree will be sorted. I can think of another way of merging two Red-Black Trees, which called "In-Place Merge using DLL", but this one would also result O(m+n) time complexity.

  1. Convert the given two Red-Black Trees into Doubly Linked List, which has O(m+n) time complexity.
  2. Merge the two sorted Linked Lists, which has O(m+n) time complexity.
  3. Build a Balanced Red-Black Tree from the merged list created in step 2, which has O(m+n) time complexity.

Time complexity of this method is also O(m+n).

So due to the fact you have to compare the elements each Tree with the other elements of the other Tree, you will have to end up with at least O(m+n).

Upvotes: -2

Related Questions