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

Question

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

该数据结构支持 O(logN) 的两种操作：

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

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

Answer 1

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

Answer 2

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

Answer 3

在平衡顺序统计树中，找到中位数是 O(log N)。如果在 O(1) 时间内找到中位数很重要，您可以通过维护指向中位数的指针来扩充数据结构。当然，问题是您需要在每次插入或删除操作期间更新此指针。更新指针将花费 O(log N) 时间，但由于这些操作已经花费 O(log N) 时间，更新中值指针的额外工作不会改变它们的大 O 成本。

实际上，与插入/删除的数量相比，这仅在您执行大量“查找中值”操作时才有意义。

如果需要，您可以通过使用（双）线程二叉树将插入/删除期间更新中值指针的成本降低到 O(1) ，但插入/删除仍将是 O(log N)。