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

Question

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

Answer 1

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]

Answer 2

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.

Answer 3

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