I have two splay trees, $A$ and $B$.
When every element in $A$ is smaller than every element in $B$, we can merge them in $O(\log N)$.
My question is; when all elements of $A$ are not necessarily smaller than all elements of $B$, how can we still merge $A$ and $B$ in $O(\log N)$?
What I have already tried:
Splay $A$'s largest element, splay $B$'s smallest element. The root $R_A$ of $A$ doesn't have a right child anymore, and the root $R_B$ of $B$ doesn't have a left child anymore. Compare $R_A$ and $R_B$. If $R_B$ is bigger than $R_A$, make $R_B$ the right child of $R_A$, which fails when $R_A$ is larger than $R_B$.