是否有一个balanced BST
结构也可以跟踪每个节点中的子树大小?
在Java
中,TreeMap
是一棵红黑树,但不在每个节点中提供子树大小。
以前,我确实写了一些BST,可以跟踪每个节点的子树大小,但它并不平衡。
问题是:
O(lg(n))
basic operations)
Java
impl很棒,但其他语言(例如c
__、go
__)也会有所帮助。
BTW:
这样就可以在不遍历子树的情况下获得大小。
可能的应用:
发布于 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
在Scheme和Haskell中也有可用的实现。
发布于 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
复制相似问题