c++ - 设置 + 第 n 个元素 : fast implementation

Question

对于以下数据结构:

• 在 O(lg(n)) 中添加一个元素
• 在 O(lg(n)) 中删除一个元素
• 在 O(lg(n)) 中找到第 k 个元素

我们可以使用平衡 BST，其中每个节点都有其子树的大小，但它需要实现编码速度不快的红黑树。

有更好的解决方案吗？

Answer 1

您正在寻找的一般结构类型是用 Indexed 或 Indexable 限定的，这是一种增加了计数的结构，能够通过索引访问元素。

您可以使用:

• 索引树:Binary Search Tree ( Red-Black Tree , AVL Tree ), B-Tree , Finger-Tree , ...
• 索引 Skip-List

(也许还有其他一些 :p)

我倾向于认为 Skip-Lists 比 BST 更容易实现，因为您可以使用随机高度而不是所有平衡的东西。