# Split or merge Binary Search Trees in O(log n)

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

• you could use red-black trees and make this worst-case O(log n) if you care. Oct 12, 2010 at 15:26
• An answer to another question might be useful: cstheory.stackexchange.com/questions/1045/… Oct 12, 2010 at 15:43

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’. In Proceedings of the 14th Conference on Annual European Symposium - Volume 14, 172–183. ESA’06. London, UK, UK: Springer-Verlag, 2006. [PDF]

• Thanks! That's the answer I had found after some more search as pointed in the comments of another answer here. Jun 28, 2012 at 13:37

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

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

• 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. Oct 13, 2010 at 10:53
• 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. cs.au.dk/~gerth/pub/esa06trees.html Oct 13, 2010 at 10:54
• 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. Oct 13, 2010 at 13:13
• you might want to update your answer to reflect this. Oct 18, 2010 at 19:48