在二叉树中找到O(1)的中位数 [英] Find median in O(1) in binary tree

问题描述

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

Suppose I have a balanced BST (binary search tree). Each tree node contains a special field count, which counts all descendants of that node + the node itself. They call this data structure order statistics binary tree.

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

This data structure supports two operations of O(logN):

• rank(x)-小于x
的元素数
• findByRank(k)-查找具有rank == k
的节点

• rank(x) -- number of elements that are less than x
• findByRank(k) -- find the node with rank == k

现在，我想添加一个新的操作median()来找到中位数.如果树是平衡的，我可以假定此操作为O(1)吗?

Now I would like to add a new operation median() to find the median. Can I assume this operation is O(1) if the tree is balanced?

推荐答案

如果树是完整的(即所有级别都已完全填满)，可以.

If the tree is complete (i.e. all levels completely filled), yes you can.

这篇关于在二叉树中找到O(1)的中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！