8
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ What other operations must the sorted dictionary have, and how fast just they be? Without requirements on the sorted of insert and lookup, doubly linked lists will do just fine, but the non-merge operations take linear time, in the length of the list, which can be superlinear in the number of distinct keys. $\endgroup$ – jbapple Apr 21 '16 at 14:05
  • $\begingroup$ I was assuming we'd support the other sorted dictionary operations (insert, delete, lookup, successor, predecessor) and that they'd ideally all run in $O(\log n)$ time. $\endgroup$ – templatetypedef Apr 21 '16 at 16:08
  • $\begingroup$ I suggest you edit your question to include this information in the question... $\endgroup$ – D.W. Apr 22 '16 at 7:35
  • $\begingroup$ Do I understand it correctly that you need a sorting data structure (dictionary or otherwise) that can be merged in time $O(\log n)$ with $n$ being the total number of elements? $\endgroup$ – Shahab Apr 22 '16 at 15:49
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ In this amortization scheme, the merge time of two sets is based on the size of the largest structure that they will ever be merged into? Does this make the merge time $\log U$, where $U$ is the size of the universe? $\endgroup$ – jbapple Apr 23 '16 at 14:29
  • $\begingroup$ No, just log of the max number of items ever in a tree at the same time. $\endgroup$ – David Eppstein Apr 24 '16 at 7:20

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.