5
$\begingroup$

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.
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 11 '13 at 16:30
  • $\begingroup$ 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... $\endgroup$ – Rontogiannis Aristofanis Aug 12 '13 at 15:25
  • $\begingroup$ That said, note that questions about the stuff you find googling are very welcome! $\endgroup$ – Raphael Aug 12 '13 at 19:31
  • $\begingroup$ @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. $\endgroup$ – wcochran Aug 14 '17 at 22:46
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "any subtrees of a RB-tree is already an RB-tree" -- to be picky: you might have to change the color of the root, thus changing black-height. $\endgroup$ – Raphael Aug 13 '13 at 8:15
  • $\begingroup$ @Raphael, you are right. $\endgroup$ – Kaveh Aug 13 '13 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.