Joining two red-black trees

Question

I have

1. two red-black trees $T_1$ of black height $H_1$ and $T_2$ of black height $H_2$
2. such that all the nodes $N$ belonging to $T_1$ are less than (in value) all the nodes $N$ of $T_2$
3. and a key $K$ such that $K$ is greater than all the nodes of $T_1$ and less than all the nodes of $T_2$.

I wanted to devise an algorithm to combine $T_1$, $K$ and $T_2$ into a single red-black tree $T$.

I could delete each element from either $T_1$ or $T_2$ and put it in other tree. But that will give me an algorithm of time-complexity $2^{H_1}$ or $2^{H_2}$ (depending on the tree from which I have deleted the elements from). I would like to have an algorithm which is $O(\max(H_1,H_2))$.

Definitions :

Black-height is the number of black-colored nodes in its path to the root.

Red-Black tree : A binary search tree, where each node is coloured either red or black and

• The root is black All NULL nodes are black
• If a node is red, then both its children are black
• For each node, all paths from that node to descendant NULL nodes have the same number of black nodes.

Answer 1

Your question surprisingly has an answer on stackoverflow, no doubt dating before this site. The question gives an algorithm of time complexity $O(\max(H_1,H_2))$, and claims that it can be improved to $O(\min(H_1,H_2))$.

By the way, oftentimes $O(H_1 + H_2)$ is used for $O(\max(H_1,H_2))$.

Answer 2

I think the trick to join in $O(\min(H_1,H_2)$ is to do operations like finding height in parallel and stop after doing it for the smaller one. Note that like many other common data structures, any subtrees of a RB-tree is already an RB-tree. We only need to fix the part above the modification.

It is instructive to try to do this first for simple BST. Given two BSTs with heights $h_1$ and $h_2$ and a key between their keys, merge them into one BST with the height $\max(h_1,h_2) + O(1)$ in time $O(\min(h_1,h_2))$.