algorithm - 集合操作的数据结构

Question

什么数据结构在时间和空间上都有效地支持以下集合操作？

1. 工会
2. 区别
3. 是成员
4. 添加
5. 删除

我可以想到 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)

Bit Array 和HashTable 速度快但占用内存太多，Ordered Tree 速度慢但占用内存少。

请注意:集合中可能包含整数以外的其他类型，如 float 或字符串

还有哪些其他数据结构既快速又通用，而且节省空间？

Answer 1

一种选择是使用布隆过滤器来扩充您的有序树，以加速 ismemberof 类型测试。

我认为整体行为应该是这样的:

1. O(N log(N) )  2. O( ? )  3.O(1)  4.O(log(N))  5.O( log(N) )

然而，具体细节将取决于过滤器的大小、集合的大小和域的大小。

另一个选项可能是 Judy Arrays .对于这种用途，我听说过关于它们的好消息，但没有个人经验。

还有一个选项是 forrest approach (而不是纯二叉树)。