0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – John L. Jan 16 '19 at 14:03
  • $\begingroup$ I don't understand your very last statement. Perhaps some piece of information is missing. $\endgroup$ – Yuval Filmus Jan 16 '19 at 14:15
  • $\begingroup$ 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/… $\endgroup$ – Dmitri Urbanowicz Jan 16 '19 at 14:50
1
$\begingroup$

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.

It contains no information at all when we know "whose ranges may overlap". The ranges of any two splay trees may overlap.

It contains no information at all when we know all elements of A are not necessarily smaller than all elements of B. That is the same as all elements of A are not necessarily larger than all elements of B.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.