查找二进制树O（1）中的位数

假设我有一个平衡的BST（二叉查找树）。每个树节点都包含一个特殊字段count，该字段计算该节点的所有后代+节点本身。他们称这个数据结构为order statistics binary tree。查找二进制树O（1）中的位数

此数据结构支持的O两个操作（logN）的：

rank(x) - 元素是小于x
findByRank(k)号码 - 查找节点与rankk ==

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

来源

2012-08-10 Michael

我认为中位数将是树的根 – Gir 2012-08-10 12:21:16

我同意吉尔。但是，只有树完全平衡，这才是真实的。 – brano 2012-08-10 12:23:32

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

来源

2012-08-10 12:22:26

如果一棵树是平衡的但不是“完整的”？ – Michael 2012-08-10 12:25:19

您可以使用计数来决定旅行的方式。在这种情况下不确定O（1），尽管 – Gir 2012-08-10 12:31:00

@Michael它取决于你对平衡的定义，如果你知道两个根的子树具有完全相同数量的子元素，则根将是中值。 – 2012-08-10 12:32:24

除非树完整，否则中位数可能是叶节点。所以在一般情况下，成本将是O（logN）。我想有一个数据结构，它具有所需的属性和一个O（1）findMedian操作（可能是一个跳过列表+一个指向中间节点的指针;尽管我不确定findByRank和rank操作），但是平衡BST不是其中之一。

来源

2012-08-10 13:48:35

是的，我们可以实现一个_special_数据结构来查找O（1）中的中位数，例如2个二进制堆或您建议的跳过列表。我想知道如果我能用增强均衡BST来做到这一点。 – Michael 2012-08-10 17:19:38

在平衡顺序统计树中，查找中位数为O（log N）。如果在O（1）时间内找到中位数很重要，则可以通过维护一个指向中位数的指针来扩充数据结构。当然，捕获是在每个插入或删除操作期间需要更新这个指针。更新指针会花费O（log N）时间，但由于这些操作已经花费O（log N）时间，所以更新中值指针的额外工作并不会改变它们的大O代价。

实际上，这只有在与插入/删除次数相比进行大量“查找中位数”操作时才有意义。

如果需要，可以使用(doubly) threaded binary tree将插入/删除期间的中值指针更新为O（1），但插入/删除仍将为O（log N）。

来源

2012-08-11 20:39:42

查找二进制树O（1）中的位数

回答

相关问题