<p>You may find this reference helpful: Brown and Tarjan, <a href="ftp://db.stanford.edu/pub/cstr/reports/cs/tr/77/625/CS-TR-77-625.pdf" rel="noreferrer">A Fast Merging Algorithm</a>, 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$.</p>

<p>You could also see a discussion of different techniques for merging ordered sets in section 11.5 of this paper on <a href="http://www.cs.au.dk/~gerth/papers/finger05.pdf" rel="noreferrer">finger search trees</a></p>

CC BY-SA 3.0
2012-02-27T14:15:51.200Z
Both the $O(n\log \frac{m}{n})$ time bound and the matching lower bound assume that $m\ge n$.
Jeffε
CC BY-SA 3.0
2012-02-27T19:50:06.203Z
I thought that that was implied by the time bound, but I edited the question to make it explicit.
Joe
CC BY-SA 3.0
2012-02-27T05:40:56.410Z
2012-02-27T19:49:38.950Z
2012-02-27T19:49:38.950Z
Joe
<p><strong>You can merge trees in $\bf\mathcal{O}(1)$ worst-case time</strong> whilst still supporting: insert, delete and search in $\mathcal{O}(log\ n)$.</p>

<p><a href="http://dx.doi.org/10.1007/11841036_18" rel="nofollow">Brodal, Gerth Stølting, Christos Makris, and Kostas Tsichlas. <strong>‘Purely Functional Worst Case Constant Time Catenable Sorted Lists’</strong>. <em>In Proceedings of the 14th Conference on Annual European Symposium - Volume 14, 172–183. ESA’06. London, UK, UK: Springer-Verlag,</em> 2006.</a>
[<a href="http://citeseerx.ist.psu.edu/viewdoc/download;?doi=10.1.1.70.1493&amp;rep=rep1&amp;type=pdf" rel="nofollow">PDF</a>]</p>

CC BY-SA 3.0
2012-06-26T17:31:42.170Z
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.
Jeffε
CC BY-SA 3.0
2012-06-26T17:54:00.840Z
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$."
A T
CC BY-SA 3.0
2012-06-25T17:33:24.973Z
2012-06-25T17:33:24.973Z
A T
<p>In <a href="http://arxiv.org/abs/1002.4248">ArXiv:1002.4248</a>, John Iacono and Özgür Özkan describe a relatively simple algorithm to merge two binary search trees in $O(\log^2 n)$ <em>amortized</em> time; the analysis is the hard part.  [<strong>Update:</strong> 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)$ <em>amortized</em> time. </p>

<p>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.</p>

CC BY-SA 3.0
2012-06-26T14:25:06.930Z
See my answer where I refer to a tree data-structure supporting $\mathcal{O}(1)$ merges that has $\mathcal{O}(log\ n)$ insert, delete and search.
A T
CC BY-SA 3.0
2012-02-27T06:00:07.257Z
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.
jbapple
CC BY-SA 3.0
2012-02-27T06:22:54.393Z
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.
Jeffε
CC BY-SA 3.0
2012-02-27T08:39:35.797Z
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__")?
mmtauqir
CC BY-SA 3.0
2012-02-27T09:39:34.343Z
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.
Jeffε
CC BY-SA 3.0
2012-02-27T15:35:29.517Z
@JɛﬀE: 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.
jbapple
CC BY-SA 3.0
2012-02-27T05:37:24.090Z
2012-02-27T09:45:01.393Z
2012-02-27T09:45:01.393Z
Jeffε
<p>I'm looking for an algorithm to merge two binary search trees of arbitrary size and range.  The <em>obvious</em> 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 <code>O(n+m)</code> where <code>n</code> and <code>m</code> are the size of each tree respectively.</p>

<p>However, I've been told that this could be done in <code>O(h)</code>, where <code>h</code> 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).  </p>

CC BY-SA 3.0
2012-03-04T20:16:05.110Z
@AT Yes, but we didn't know that the keys from one BST was mutually exclusive from the other.
efritz
CC BY-SA 3.0
2012-03-04T20:16:26.420Z
@AT Also, the height of a BST is not necessarily logn.
efritz
CC BY-SA 3.0
2012-03-05T13:58:45.993Z
On the contrary, the height of BSTs are `O(log n)`. [Proof](http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Proof_of_asymptotic_bounds)
A T
CC BY-SA 3.0
2012-03-05T18:27:47.590Z
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.
efritz
CC BY-SA 3.0
2012-03-01T22:23:07.517Z
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.
efritz
CC BY-SA 3.0
2012-03-03T03:35:17.763Z
Am I missing something, wouldn't merging binary trees be easily done in `O(log n)` with a simple move node function?
A T
<ds.algorithms><ds.data-structures><tree>
Merging Two Binary Search Trees
efritz
# Merging Two Binary Search Trees

(Asked by: username_0 on 2012-02-26)

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

**Tags:** ds.algorithms, ds.data-structures, tree

> **Comments:**
> **username_0**: 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.  
> **username_1**: Am I missing something, wouldn't merging binary trees be easily done in `O(log n)` with a simple move node function?  
> **username_0**: @AT Yes, but we didn't know that the keys from one BST was mutually exclusive from the other.  
> **username_0**: @AT Also, the height of a BST is not necessarily logn.  
> **username_1**: On the contrary, the height of BSTs are `O(log n)`. [Proof](http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Proof_of_asymptotic_bounds)  
> **username_0**: 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.  

---

## 3 answers

### Answer by username_3 on 2012-02-27. Score: 26 | Accepted answer

In [ArXiv:1002.4248](http://arxiv.org/abs/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 username_2 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.

> **Comments:**
> **username_4**: 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 username_2's answer). The restricted set of operations allows for a better analysis than the $O(n \lg \frac{m}{n})$ one.  
> **username_3**: 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.  
> **username_5**: 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__")?  
> **username_3**: 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.  
> **username_4**: @JɛﬀE: 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.  
> **username_1**: See my answer where I refer to a tree data-structure supporting $\mathcal{O}(1)$ merges that has $\mathcal{O}(log\ n)$ insert, delete and search.  

---

### Answer by username_2 on 2012-02-27. Score: 10

You may find this reference helpful: Brown and Tarjan, [A Fast Merging Algorithm](ftp://db.stanford.edu/pub/cstr/reports/cs/tr/77/625/CS-TR-77-625.pdf), 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](http://www.cs.au.dk/~gerth/papers/finger05.pdf)

> **Comments:**
> **username_3**: Both the $O(n\log \frac{m}{n})$ time bound and the matching lower bound assume that $m\ge n$.  
> **username_2**: I thought that that was implied by the time bound, but I edited the question to make it explicit.  

---

### Answer by username_1 on 2012-06-25. Score: 0

**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.](http://dx.doi.org/10.1007/11841036_18)
[[PDF](http://citeseerx.ist.psu.edu/viewdoc/download;?doi=10.1.1.70.1493&rep=rep1&type=pdf)]

> **Comments:**
> **username_3**: 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.  
> **username_1**: 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$."  

---

