17
$\begingroup$

I'm looking for an algorithm to merge two binary search trees of arbitrary size and range. The obvious way I would go about implementing this would be to find entire subtrees whose range can fit into an arbitrary external node in the other tree. However, the worst case running time for this type of algorithm seems to be on the order of O(n+m) where n and m are the size of each tree respectively.

However, I've been told that this could be done in O(h), where h is the height of the tree with the larger height. And I'm completely lost on how this is possible. I've tried experimenting with rotating one the trees first, but rotating a tree into a spine is already O(h).

$\endgroup$
  • $\begingroup$ I do not know erick I have the same question too. $\endgroup$ – user8556 Feb 26 '12 at 23:54
  • $\begingroup$ To be fair, this was a question given in an Algorithms homework. It turns out that O(h) is too strict of a runtime, as the question forgot to give more necessary information: That all of the keys from one tree were smaller than all of the keys in the right tree. $\endgroup$ – efritz Mar 1 '12 at 22:23
  • $\begingroup$ Am I missing something, wouldn't merging binary trees be easily done in O(log n) with a simple move node function? $\endgroup$ – A T Mar 3 '12 at 3:35
  • $\begingroup$ @AT Yes, but we didn't know that the keys from one BST was mutually exclusive from the other. $\endgroup$ – efritz Mar 4 '12 at 20:16
  • 1
    $\begingroup$ This is a red-black tree, not a BST. A red black (as well as AVL trees and heaps) are special kinds of trees that keep a height-bound property. Vanilla BSTs can be a single spine. Try inserting a non-decreasing or non-increasing series of numbers into a BST and you'll see that the height of these trees are actually n. Only full or complete binary trees have a height logarithmic to their total number of nodes. $\endgroup$ – efritz Mar 5 '12 at 18:27
24
$\begingroup$

In ArXiv:1002.4248, John Iacono and Özgür Özkan describe a relatively simple algorithm to merge two binary search trees in $O(\log^2 n)$ amortized time; the analysis is the hard part. [Update: As Joe correctly observes in his answer, this algorithm is due to Brown and Tarjan.] They also describe a more complicated dictionary data structure, based on biased skip lists, that supports merges in $O(\log n)$ amortized time.

On the other hand, a worst-case bound of $O(\log n)$ is impossible. Consider two binary search trees with $n$ nodes, one storing the even integers between $2$ and $2n$, the other storing the odd integers between $1$ and $2n-1$. Merging the two trees creates a new binary search tree storing all integers between $1$ and $2n$. In any such tree, a constant fraction of the nodes have different parity than their parents. (Proof: The parent of an odd leaf must be even.) Thus, merging the even and odd trees requires changing $\Omega(n)$ pointers.

$\endgroup$
  • $\begingroup$ One note: if I have read the description in this paper correctly, these trees do not support insert and delete. The $O(\lg^2 n)$ merge just follows the procedure for merging finger search trees (described in Joe's answer). The restricted set of operations allows for a better analysis than the $O(n \lg \frac{m}{n})$ one. $\endgroup$ – jbapple Feb 27 '12 at 6:00
  • 1
    $\begingroup$ The improved analysis is due to amortization, not a restriction of the allowed operations. Insertions and deletions can be supported with splits and merges (actually "joins") in the same $O(log n)$ amortized time bound. $\endgroup$ – Jeffε Feb 27 '12 at 6:22
  • $\begingroup$ Just out of curiosity, does the $\Omega(n)$ time get affected if the trees are stored in arrays instead of linked-lists (which I assume is what you meant when saying "changing ... pointers")? $\endgroup$ – mtahmed Feb 27 '12 at 8:39
  • $\begingroup$ By default, "binary search trees" are pointer-based structures (not "linked lists"); each node points to its two kids and possibly its parent. But the lower bound doesn't depend on the precise representation. There are $\binom{2n}{n}$ ways to merge two $n$-node binary search trees, so any comparison-based algorithm needs at least $\log_2 \binom{2n}{n} \ge 2n - O(\log n)$ comparisons to choose the right one. $\endgroup$ – Jeffε Feb 27 '12 at 9:39
  • 1
    $\begingroup$ @JɛffE: I agree that splits and joins are supported, but I don't think that creating or destroying trees are. So, for instance, if I want to delete "x" from the alphabet, I don't get just "a..wyz", but also "x". The size of the universe (which is $n$, see section 2.1) doesn't change. Also, the intro to section 1 notes that the sets must partition the universe, which I interpret (perhaps incorrectly) to mean that each element in the universe is in some tree. So, the way I read it, this construction does not work over unbounded universes. That's how I should I written my comment above. $\endgroup$ – jbapple Feb 27 '12 at 15:35
9
$\begingroup$

You may find this reference helpful: Brown and Tarjan, A Fast Merging Algorithm, in which the authors show how to merge balanced binary (AVL) trees in $O(n \log \frac{m}{n})$ which is optimal (for comparison based algorithms). $m$ and $n$ are the lengths of the sorted lists represented by the binary search trees, and it is assumed that $m \geq n$.

You could also see a discussion of different techniques for merging ordered sets in section 11.5 of this paper on finger search trees

$\endgroup$
  • 2
    $\begingroup$ Both the $O(n\log \frac{m}{n})$ time bound and the matching lower bound assume that $m\ge n$. $\endgroup$ – Jeffε Feb 27 '12 at 14:15
  • $\begingroup$ I thought that that was implied by the time bound, but I edited the question to make it explicit. $\endgroup$ – Joe Feb 27 '12 at 19:50
0
$\begingroup$

You can merge trees in $\bf\mathcal{O}(1)$ worst-case time whilst still supporting: insert, delete and search in $\mathcal{O}(log\ n)$.

Brodal, Gerth Stølting, Christos Makris, and Kostas Tsichlas. ‘Purely Functional Worst Case Constant Time Catenable Sorted Lists’. In Proceedings of the 14th Conference on Annual European Symposium - Volume 14, 172–183. ESA’06. London, UK, UK: Springer-Verlag, 2006. [PDF]

$\endgroup$
  • $\begingroup$ Their data structure supports join in O(1) amortized time, not merge. All elements in one tree must be smaller than all elements in the other. $\endgroup$ – Jeffε Jun 26 '12 at 17:31
  • $\begingroup$ Ahh, true. Had to reread the article: "Join($T_i$ ,$T_j$), joins the two trees in one tree. Trees $T_i$ and $T_j$ are ordered in the sense that all elements of $T_j$ are either smaller or larger than the smallest or largest element of $T_i$ . Assume without loss of generality that $w(T_i) = w(T_j)$. In this case, tree $T_j$ is attached to tree $T_i$ , and the result of this operation is the tree $T_i \centerdot T_j$ is attached to a node on the spine of $T_i$." $\endgroup$ – A T Jun 26 '12 at 17:54

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.