Best way to join two red-black trees

Question

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?

Answer 1

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.