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

Improve this question
$\endgroup$
7
  • $\begingroup$ I do not know erick I have the same question too. $\endgroup$
    – user8556
    Feb 26, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 18:27

3 Answers 3

Reset to default
25
$\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.

Improve this answer
$\endgroup$
6
  • $\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, 2012 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, 2012 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$
    – mmtauqir
    Feb 27, 2012 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, 2012 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, 2012 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

Improve this answer
$\endgroup$
2
  • 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, 2012 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, 2012 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]

Improve this answer
$\endgroup$
2
  • 1
    $\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, 2012 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, 2012 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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