Sorted dictionary structure supporting efficient merges?

Question

Many balanced tree structures (red/black trees, splay trees, etc.) and some other sorted dictionary structures (skiplists) support a join operation that takes in two dictionaries where all keys in the first structure are less than all keys in the second, then combines the two dictionaries into a single sorted dictionary in time $O(\log n)$, where $n$ is the total number of keys. However, this only works if there is no overlap in the ranges of keys stored in those trees.

Similarly, many priority queues (binomial heaps, Fibonacci heaps, etc.) support $O(\log n)$-time merges. These merges work regardless of what keys are stored, but given that the data structures are priority queues we can't do lookups for random elements in the resulting structure.

Is there a sorted dictionary structure that supports merges of arbitrary dictionaries in time $O(\log n)$ while simultaneously supporting normal sorted dictionary operations (insertions, deletions, lookups, successor/predecessor queries, etc.) in time $O(\log n)$, or a lower-bound proof that such structures can't exist?

Answer 1

If you have a balanced binary search tree data structure with the finger search tree property (a search for an item $d$ positions away takes time $O(\log d)$), such as for instance a splay tree, then if you insert a sorted sequence of $k$ items into it the total time for the insertion will be $O(k\log(n/k))$.

Now, suppose that you want to support insertions, destructive merges, and searches. For the insertions and searches, just use the existing search tree operations. For a merge, always merge the smaller tree into the larger one, and use an inorder traversal of the smaller tree to get its sorted order in linear time. Then, insert the elements of the smaller tree one at a time into the larger tree in this sorted order.

If an element $x$ is inserted then merged into a sequence of larger trees with sizes $n_1, n_2,\dots$ then the amount of time for the insertion and merges (counting only $x$'s fraction of the total merge time) will be $O(\log n_1)$, $O(\log(n_2/n_1))$, $\dots$, which add in a telescoping sequence to $O(\log n)$. So if one uses an amortization scheme in which this logarithmic total time for a potential sequence of merges is charged to the insertion operation for $x$, then we still get $O(\log n)$ amortized time per insertion or search, and only $O(1)$ amortized time per merge.

Deletions complicate this analysis, but not much. One way to handle them would be to do a semi-lazy deletion, where a deleted item is removed from its tree but not removed from the count of items in this tree, so that when we decide which of two trees is smaller or larger we count all the items that were ever in the tree. Then, the $n$ in the $O(\log n)$ time per operation should be the total number of items ever inserted or deleted rather than the number currently present. If these two numbers ever grow too far apart you can make an update that re-adjusts all the counts to their actual numbers, resetting the data structure to a state with no lazy-deleted items; the amortized time for this update can be charged against the deletion operations you had to perform to get the numbers so far apart. Or possibly you can make the merge amortization work directly with non-lazy deletions, but I haven't worked out the details of that part.