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