algorithm - 在二叉树中查找 O(1) 的中位数

Question

假设我有一个平衡的 BST(二叉搜索树)。每个树节点都包含一个特殊字段count，它计算该节点的所有后代+节点本身。他们称这种数据结构为顺序统计二叉树。

这个数据结构支持两个O(logN)的操作:

• rank(x) -- 小于x
的元素个数
• findByRank(k) -- 找到 rank == k
的节点

现在我想添加一个新操作 median() 来求中位数。如果树是平衡的，我可以假设这个操作是 O(1) 吗？

Answer 1

除非树是完整的，否则中位数可能是叶节点。所以在一般情况下，成本将为 O(logN)。我想有一个具有请求属性和 O(1) findMedian 操作的数据结构(可能是一个跳跃列表+一个指向中值节点的指针；我不确定 findByRank 和 rank 操作)但是平衡的 BST 不是其中之一。