Joining two red-black trees I have 


two red-black trees $T_1$ of black height $H_1$ and $T_2$ of black height $H_2$
such that all the nodes $N$ belonging to $T_1$ are less than (in value) all the nodes $N$ of $T_2$
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 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))$.