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