到目前为止,我知道像AVL树和红黑树这样的自平衡BST可以在O(log n)次内完成这些操作。
然而,要使用这些结构,我们必须自己实现AVL树或RB树。
我听说有一个算法/实现这四个操作而不使用自平衡 BST。
有了我们自己定义的结构,我们就需要写这么多行。然而,我听说有可能用不到 100 行的代码支持这四个运算符:\
你们对如何做到这一点有什么想法吗?
除了BST之外,还有其他可能的选择吗?
正如评论中提到的,如果您想维护一组整数并且可以进行坐标压缩作为预处理步骤(例如,因为您的算法是离线的并且知道所有未来的查询),您可以使用支持每次操作 O(log n) 内的数字插入/删除/排序/选择。下面是一个 C++ 示例:
int tree[N]; // where N is the number of compressed coordinates
const int maxl = floor(log(N)/log(2));
void insert(int i) { // 1 <= i <= N
for (; i <= N; i += i & -i) ++tree[i];
}
void remove(int i) { // 1 <= i <= N
for (; i <= N; i += i & -i) --tree[i];
}
int rank(int i) { // 1 <= i <= N
int sum = 0;
for (; i; i -= i & -i) sum += tree[i];
return sum;
}
int select(int k) { // k is 1-based
int ans = 0, s = 0;
for (int i = maxl; i >= 0; --i) // maxl = largest i s.t. (1<<i) <= N
if (s + tree[ans + (1<<i)] < k) {
ans += 1<<i;
s += tree[ans];
}
return ans+1;
}
The select
功能有点神奇。它重用高位的结果来计算前缀和ans + (1<<i)
在 O(1) 中,这非常酷恕我直言:)这样只需要 O(log n) 时间,而不是使用标准二分搜索很容易实现的 O(log^2 n) 时间。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)