# Joining two red-black trees

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.
• Your question is answered on stackoverflow: stackoverflow.com/a/3224033/940550. By the way, it took me just a few minutes to find this link. – Yuval Filmus Aug 11 '13 at 16:30
• Step 1) Open your browser. Step 2) Write on google how to join two red black trees; press enter. Step 3) press the first link. It's a comprehensible presentation about red black trees, which includes details about joining two red black trees... – Rontogiannis Aristofanis Aug 12 '13 at 15:25
• That said, note that questions about the stuff you find googling are very welcome! – Raphael Aug 12 '13 at 19:31
• @yuval-filmus Isn't this a more specialized case that the ones you googled? The restriction on the keys tell me that the should be a faster algorithm than than the general merge case. – wcochran Aug 14 '17 at 22:46

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))$.
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))$.