algorithm - 是否有一个平衡的 BST，每个节点都保持子树的大小？

Question

是否有一个平衡的 BST 结构也可以跟踪每个节点中的子树大小？

在 Java 中，TreeMap 是一棵红黑树，但不提供每个节点的子树大小。

以前，我确实写过一些 BST，可以跟踪每个节点的子树大小，但它不是平衡的。

问题是:

• 是否有可能实现这样的树，同时保持 (O(lg(n)) 基本操作的效率)？
• 如果是，那么有没有第 3 方库提供这样的实现？
  Java impl 很棒，但其他语言(例如 c、go) 也会有帮助。

顺便说一句:

• 应该在每个节点中跟踪子树的大小。
  这样就可以在不遍历子树的情况下得到大小。

可能的应用:

• 跟踪项目的排名，其值(排名所依赖的)可能会随时更改。

Answer 1

Weight Balanced Tree (也称为亚当斯树或有界平衡树)保持每个节点中的子树大小。

这也使得在 log(n) 时间内从开始或结束找到第 N 个元素成为可能。

我的 implementation in Nim is on github .它具有以下属性:

• 通用(参数化)键值映射
• 在 O(log(N)) 时间内插入(add)、查找(get)和删除(del)
• 键序迭代器(inorder 和 revorder)
• 在 O(log(N)) 时间内从开始或结束(getNth)开始的相对位置查找
• 在O(log(N))时间内通过key获取位置(rank)
• 使用树键的高效集合操作
• 将扩展映射到集合操作，并为重复项设置可选的值合并控制

还有可用的 Scheme 和 Haskell 实现。