# Merging two splay trees whose ranges may overlap in $O(\log N)$

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)$$?

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

• What do you think? This site encourages you to show your thoughts or partial progress toward solving the problems. People can then make the answers more helpful for you and for future readers. – John L. Jan 16 '19 at 14:03
• I don't understand your very last statement. Perhaps some piece of information is missing. – Yuval Filmus Jan 16 '19 at 14:15
• Seems like you want to merge two arbitrary trees. You might find this link helpful, though it's not about splay trees: cstheory.stackexchange.com/questions/10407/… – Dmitri Urbanowicz Jan 16 '19 at 14:50

No, you cannot merge two splay trees whose ranges may overlap in $$O(\log N)$$, where $$N$$ is the total number of nodes. You may have to move at least $$\Theta(N)$$ nodes in general or average situations.