<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>Unfortunately splitting causes problems, and would result in $\mathcal{O}(log\ n\ log\ log\ n)$ search and update times.</p>

<p>Brodal, Gerth Stølting, Christos Makris, and Kostas Tsichlas. <a href="http://dx.doi.org/10.1007/11841036_18" rel="nofollow"><strong>‘Purely Functional Worst Case Constant Time Catenable Sorted Lists’</strong></a>. <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 href="http://www.cs.au.dk/~gerth/papers/esa06trees.pdf" rel="nofollow">PDF</a>]</p>

CC BY-SA 3.0
2012-06-28T13:37:46.623Z
Thanks! That's the answer I had found after some more search as pointed in the comments of another answer here.
Dimitris Leventeas
CC BY-SA 3.0
2012-06-25T17:31:42.387Z
2013-10-31T22:14:19.933Z
2013-10-31T22:14:19.933Z
A T
<p><a href="http://en.wikipedia.org/wiki/Treap" rel="nofollow">Treaps</a> support both operations in $O( \log n)$ time with high probability. The trick is to give the splitting element $0$ priority making it the root, splitting the trees, and then reverting its priority to the original value. Merging is done similarly. </p>

CC BY-SA 3.0
2010-10-18T13:40:54.647Z
2013-10-31T18:05:53.293Z
2013-10-31T18:05:53.293Z
Sariel Har-Peled
<p>I am not expert here . Any way I give a try here</p>

<p>For merge operation
,Find the largest element in $S1$ say $w$ (log(n)), we know that it does not contain right child as it is the largest element. we know that every element in $S2$ is greater than $w2$. surely $root(S1)$ will be >= $w$ so make $right(w)->root(S1)$ which is order of O(1)</p>

<p>For Spit operation
Search the element $k$ in $S$ (logn) we know that. we reach at the node say $y$ we know that all elements in $right(y)$ will give greater than $k$ .$right(y)$ be the new $S2$ tree and $S$ without $right(y)$ will be $S1$ </p>

<p>i do not think merge function or split can be done in constant time.</p>

<p>Sorry if it is wrong  </p>

CC BY-SA 2.5
2010-10-13T10:53:18.063Z
The problem is tree balance. For merging, suppose the two trees are equally large and both are perfectly balanced. After you graft the right subtree onto the left subtree at its rightmost node, the tree will be unbalanced by a factor of 2.
Per Vognsen
CC BY-SA 2.5
2010-10-13T10:54:05.790Z
Using the described process we obtain non balanced trees. The search time in those trees could be as high as O(n). Subsequently, we can't guarantee a cost of `O(log n)` in the operation of `merge` or `split` using this process. As a side note, there is a tree which offers the merge (`join`) operation in `O(1)` which I found through a link in the comments. http://www.cs.au.dk/~gerth/pub/esa06trees.html
Dimitris Leventeas
CC BY-SA 2.5
2010-10-13T13:13:57.947Z
sorry the worst case for the approach here is O(n) as the tree here is not the height balanced one. Sorry for the mistake and thanks for the correction.
Prabu 
CC BY-SA 2.5
2010-10-18T19:48:23.120Z
you might want to update your answer to reflect this.
Suresh Venkat
CC BY-SA 2.5
2010-10-13T04:48:51.397Z
2010-10-13T04:48:51.397Z
Prabu 
<p>We need to have an efficient operation of merging or splitting two binary search trees $S_1$ and $S_2$. There are given the following.</p>

<p>The element with the largest value in $S_1$ is smaller than the element with the smallest value in $S_2$. Abusing the notation $S_1 &lt; S_2$.</p>

<p>We define as <code>merge</code> operation the operation which requires the two trees $S_1$ and $S_2$ and produces a valid binary search tree $S$ containing all of their elements.</p>

<p>Similarly, $S$ is <code>split</code> in two binary search trees $S_1$ and $S_2$ given an element $k$ for which (abusing the terminology again) $S_1 \le k &lt; S_2$.</p>

<p>The best solution I have come up with in order to convince myself that this is possible, is by using splay trees. To <code>merge</code> we put the smallest element of $S_2$ as the root of the new tree with $S_1$ as the left subtree and $S_2$ as the right subtree (alternative we use the largest element of $S_1$ if it smaller). Amortized time $O(\log n)$. Similarly, we split by searching for the element $k$... Amortized time $O(\log n)$ again.</p>

<p>Is there anything better?</p>

<p>(Sorry for the lack of imagination in my question, this is my first post here.)</p>

CC BY-SA 2.5
2010-10-12T15:26:06.860Z
you could use red-black trees and make this worst-case O(log n) if you care.
Suresh Venkat
CC BY-SA 2.5
2010-10-12T15:43:41.293Z
An answer to another question might be useful: http://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree/1166#1166
Tsuyoshi Ito
<ds.data-structures><tree>
Split or merge Binary Search Trees in O(log n)
Dimitris Leventeas
# Split or merge Binary Search Trees in O(log n)

(Asked by: username_0 on 2010-10-12)

We need to have an efficient operation of merging or splitting two binary search trees $S\_1$ and $S\_2$. There are given the following.

The element with the largest value in $S\_1$ is smaller than the element with the smallest value in $S\_2$. Abusing the notation $S\_1 < S\_2$.

We define as `merge` operation the operation which requires the two trees $S\_1$ and $S\_2$ and produces a valid binary search tree $S$ containing all of their elements.

Similarly, $S$ is `split` in two binary search trees $S\_1$ and $S\_2$ given an element $k$ for which (abusing the terminology again) $S\_1 \le k < S\_2$.

The best solution I have come up with in order to convince myself that this is possible, is by using splay trees. To `merge` we put the smallest element of $S\_2$ as the root of the new tree with $S\_1$ as the left subtree and $S\_2$ as the right subtree (alternative we use the largest element of $S\_1$ if it smaller). Amortized time $O(\log n)$. Similarly, we split by searching for the element $k$... Amortized time $O(\log n)$ again.

Is there anything better?

(Sorry for the lack of imagination in my question, this is my first post here.)

**Tags:** ds.data-structures, tree
> **Comments:**
> **username_1**: you could use red-black trees and make this worst-case O(log n) if you care.  
> **username_2**: An answer to another question might be useful: http://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree/1166#1166  

---

## 3 answers

### Answer by username_3 on 2012-06-25. Score: 6 | Accepted answer

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

Unfortunately splitting causes problems, and would result in $\mathcal{O}(log\ n\ log\ log\ n)$ search and update times.

Brodal, Gerth Stølting, Christos Makris, and Kostas Tsichlas. [**‘Purely Functional Worst Case Constant Time Catenable Sorted Lists’**](http://dx.doi.org/10.1007/11841036_18). *In Proceedings of the 14th Conference on Annual European Symposium - Volume 14, 172–183. ESA’06. London, UK, UK: Springer-Verlag,* 2006.
[[PDF](http://www.cs.au.dk/~gerth/papers/esa06trees.pdf)]

> **Comments:**
> **username_0**: Thanks! That's the answer I had found after some more search as pointed in the comments of another answer here.  

---

### Answer by username_4 on 2010-10-18. Score: 8

[Treaps](http://en.wikipedia.org/wiki/Treap) support both operations in $O( \log n)$ time with high probability. The trick is to give the splitting element $0$ priority making it the root, splitting the trees, and then reverting its priority to the original value. Merging is done similarly.


---

### Answer by username_5 on 2010-10-13. Score: -1

I am not expert here . Any way I give a try here

For merge operation
,Find the largest element in $S1$ say $w$ (log(n)), we know that it does not contain right child as it is the largest element. we know that every element in $S2$ is greater than $w2$. surely $root(S1)$ will be >= $w$ so make $right(w)->root(S1)$ which is order of O(1)

For Spit operation
Search the element $k$ in $S$ (logn) we know that. we reach at the node say $y$ we know that all elements in $right(y)$ will give greater than $k$ .$right(y)$ be the new $S2$ tree and $S$ without $right(y)$ will be $S1$

i do not think merge function or split can be done in constant time.

Sorry if it is wrong

> **Comments:**
> **username_6**: The problem is tree balance. For merging, suppose the two trees are equally large and both are perfectly balanced. After you graft the right subtree onto the left subtree at its rightmost node, the tree will be unbalanced by a factor of 2.  
> **username_0**: Using the described process we obtain non balanced trees. The search time in those trees could be as high as O(n). Subsequently, we can't guarantee a cost of `O(log n)` in the operation of `merge` or `split` using this process. As a side note, there is a tree which offers the merge (`join`) operation in `O(1)` which I found through a link in the comments. http://www.cs.au.dk/~gerth/pub/esa06trees.html  
> **username_5**: sorry the worst case for the approach here is O(n) as the tree here is not the height balanced one. Sorry for the mistake and thanks for the correction.  
> **username_1**: you might want to update your answer to reflect this.  

---

