data-structures - 是否有任何允许快速合并的地图数据结构？

Question

是否有至少具有O(log n)插入、删除、访问和合并的地图数据结构？

大多数自平衡二叉树，例如AVL 树和红黑树，都具有这些属性中的大部分，但我相信它们具有O(n log n)合并功能。有没有合并速度更快的数据结构？

编辑：我环顾四周，找不到这样的东西。如果没有这样的数据结构，我很想了解为什么这是不可能的。

Answer 1

我会看看张开的树。您可能最终会在此过程中支付合并成本，但您应该能够注入另一棵树并将成本推迟到以后。

Answer 2

您是否需要为仅定义了比较的任意键类型创建树，或者如果它仅适用于具有固定大小二进制表示的类型（int、long、float、double ......），是否可以？如果是后者，那么二叉基数树是一种具有非常有效的合并的数据结构（如果幸运的话，O(1)，最坏的情况是 O(N)）。

有关数据结构的详细信息，请参阅Chris Okasaki 和 Andrew Gill 的Fast Mergeable Integer Maps。

Scala Collections Library 包含一个ints和longs的实现。所有其他java 原始类型都可以转换为int 或long，例如使用java.lang.Double.doubleToLongBits for Double。