merge two splay tree

Question

How to merge two splay tree with amortized cost of log(n)?

Answer 1

I assume that the splay trees you want to merge hold n objects each. (i.e. in total, we have 2n objects). Then I think it is not possible to merge them with amortized log(n) cost, unless you impose some further assumptions. If you do not have any information about the objects contained in the trees, you will have to look at least at each element of one of the two trees, thus having cost O(n).

However, if you can make certain assumptions about the objects, you might be able to do it in O(log(n)). You might extract certain subtrees so you can insert the whole subtree into the other splay tree. However, I don't know an exact algorithm how to acchieve O(log(n)). For example, if we know that the biggest object in Tree1 is smaller than the smallest object in Tree2, then we might just splay the leftmost node of Tree2 and then we hang the root of Tree1 under the new root of Tree2.