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 &lt; 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 &lt; 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.)
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.