在二叉树中找出O(1)的中位数

Question

假设我有一个平衡的BST(二叉搜索树).每个树节点都包含一个特殊字段count,该字段计算该节点的所有后代+节点本身.他们称这种数据结构order statistics binary tree.

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

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

现在我想添加一个新的操作median()来查找中位数.如果树是平衡的,我可以假设此操作是O(1)吗？

Answer 1

如果树是完整的（即所有级别都完全填满），是的，可以。