是否存在平衡的BST，每个节点都保持子树大小？
是否有一个balanced BST结构也可以跟踪每个节点中的子树大小？
在Java中，TreeMap是一棵红黑树，但不在每个节点中提供子树大小。
以前，我确实写了一些BST，可以跟踪每个节点的子树大小，但它并不平衡。
问题是：
- 是否可以实现这样的树，同时保持(__
O(lg(n))
basic operations)
- 的效率如果可以，那么有没有第三方库提供这样的实施？
Java impl很棒，但其他语言(例如c__、go__)也会有所帮助。
BTW:
- 应跟踪每个节点中的子树大小。
这样就可以在不遍历子树的情况下获得大小。
可能的应用：
- 跟踪项目的排名，其值(排名所依赖的)可能会随时更改。
回答 2
Stack Overflow用户
发布于 2019-03-01 03:43:25
Weight Balanced Tree (也称为Adams树，或有界平衡树)保持每个节点中的子树大小。
这也使得可以在log(n)时间内找到从开始或结束开始的第N个元素。
我的implementation in Nim is on github。它具有以下属性：
- 泛型(参数化)键、值映射和插入(
)、查找(get)和删除(del) in O((N)) time
- 键序迭代器(按相对位置从O(log(N)中的开始或结束(getNth)开始按顺序排序和删除)time
- 按O(log(N)中的键获取位置(等级))使用树键
- 映射扩展设置操作，使用可选值合并控件设置重复操作
在Scheme和Haskell中也有可用的实现。
Stack Overflow用户
发布于 2019-03-01 04:06:23
这被称为“顺序统计树”：https://en.wikipedia.org/wiki/Order_statistic_tree
将大小添加到任何类型的平衡二叉树(红黑、avl、b树等)中非常容易，或者您可以使用直接处理大小的平衡算法，如权重平衡树(@DougCurrie答案)或(更好的)大小平衡树：https://cs.wmich.edu/gupta/teaching/cs4310/lectureNotes_cs4310/Size%20Balanced%20Tree%20-%20PEGWiki%20sourceMayNotBeFullyAuthentic%20but%20description%20ok.pdf
不幸的是，我不认为有任何标准库实现，但如果您查找它，您可以找到开放源码。你可能想要你自己的。
https://stackoverflow.com/questions/54930936
复制相似问题