什么数据结构在时间和空间上都支持以下集合操作？集合操作的数据结构
我能想到的3点不同的方式来执行这些操作，假设我们有两套，它们的大小都是N：
位阵列：
1. O(N) 2.O(N) 3.O(1) 4.O(1) 5.O(1)
哈希表：
1. O(N) 2.O(N) 3.O(1) 4.O(1) 5.O(1)
有序树：
1. O(NlogN) 2.O(NlogN) 3.O(logN) 4.O(logN) 5.O(logN)
位阵列和Hashtable的速度快，但他们使用了太多的内存，有序树是速度慢，但消耗的内存更少。
请注意：集可以包含其他类型的除了整数，如浮点数或字符串
哪些数据结构是快速和普通，和空间效率？
一个选项是用布隆过滤器来扩充您的有序树，以加速ismemberof型号测试。
我认为的整体行为会是这样的：
1. O(N log(N)) 2. O(?) 3.O(1) 4.O(log(N)) 5.O(log(N))
但是具体细节将取决于过滤器的大小，您集的大小和你的域的大小。
另一个选项可能是Judy Arrays。我听说过这种用途的好处，但没有亲身经历。
还有一种选择是forrest approach（而不是纯二叉树）。
我建议Binary Heap（最简单的一个），Binomial Heap（加快联盟）和Fibonacci Heap（最难实施，但具有最知名的标准操作摊销时间）。
操作 二元堆 二项式堆 斐波那契堆（摊销）
1.联合 为O（n） O（logn）时间 O（1）
2。差 O（nlogn） O（nlogn） O（nlogn）
3.查找（ismemberof） 为O（n） 为O（n） 为O（n）
4。添加 O（LGN） O（LGN） O（1）
5。删除 O（LGN） O（LGN） O（LGN）
然而，这些结构大多使用时插入，查找/解压分钟（最大），工会和删除需要操作。 找到和差异操作仍然有运行时间差。
什么是你正在尝试使用这种数据结构的应用程序？ – 2012-08-01 06:14:52
为什么不能哈希表（散集）保存任意（但可比）对象就像一个有序的树？ – 2012-08-01 06:16:19
对于日志分析，不是所有的操作都需要，但我很好奇。 – outlaw 2012-08-01 06:16:37