Is there any map data structure that allows fast merging?

views:

137

answers:

Is there any map data structure that allows fast merging?

Are there any map data structures that have at least O(log n) insertion, deletion, access, and merging?

Most self-balancing binary trees such as AVL trees and red-black trees have most of these properties, but I believe they have O(n log n) merging. Are there any data structures that have faster merging?

Edit: I have looked around, and I can't find anything like this. If there is no such data structure, I would love some insight into why this is not possible.

+1 A:

I'd take a look at splay trees. You'll probably end up paying the merging cost along the way, but you should be able to inject another tree in and put the cost off until later.

Joe Beda 2009-06-04 00:23:05

That looks cool, I might use it... I just don't like the idea of destructive reads.

Zifre 2009-06-04 19:58:43

@Zifre: The reads really aren't destructive. If anything they generally *improve* the structure of the tree -- and they do not change its external representation.

Captain Segfault 2009-06-05 21:00:10

The constant factor on splay trees is pretty bad. If you merge infrequently enough, you may come out ahead with an "inferior" worst-case running time for merges.

Dave 2009-06-06 16:36:13

Also, the improvement that Captain Segfault is referring to is known as the Dynamic Optimality conjecture, of which some special cases have been established. It states in essence that for any access sequence, a splay tree uses at most O(1) times as many operations as any other binary tree. This has many consequences, for example: if some items are accessed very frequently, then they become cheaper than O(log n) to access.

Dave 2009-06-06 16:42:39

ansaurus

tags:

views:

answers:

Is there any map data structure that allows fast merging?

related questions