# 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 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. – Dimitris Leventeas Jun 28 '12 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. – Per Vognsen Oct 13 '10 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 – Dimitris Leventeas Oct 13 '10 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. – Prabu Oct 13 '10 at 13:13
• you might want to update your answer to reflect this. – Suresh Venkat Oct 18 '10 at 19:48