performance - 从 AVL 树中获取中位数？

Question

如果您有一个 AVL 树，从中获取中位数的最佳方法是什么？中位数将定义为排序列表中索引为 ceil(n/2)(索引从 1 开始)的元素。

如果列表是

1 3 5 7 8

中位数是 5。如果列表是

1 3 5 7 8 10

中位数是 5。

如果可以扩充树，我认为最好让每个节点都知道子树的大小(节点数)，(即 1 + left.size + right.size)。使用这个，我能想到的最好的方法是使中值搜索时间为 O(lg n)，因为您可以通过比较索引来遍历。

有没有更好的办法？

Answer 1

如果您需要优化中值查询，扩充 AVL 树以存储子树大小通常是最好的方法。它需要时间 O(log n)，这是相当快的。

如果您要多次计算中位数，则可以使用增广树并缓存中位数，以便您可以在时间 O(1) 中读取它。每次执行插入或删除操作时，您可能需要重新计算时间 O(log n) 的中位数，这会稍微减慢速度但不会影响渐近成本。

另一种选择是通过树中的节点串接一个双向链表，这样您就可以在恒定时间内从一个节点导航到它的后继或前导节点。如果你这样做，那么你可以存储一个指向中间元素的指针，然后在插入或删除时，根据需要将指针向左或向右移动。如果您删除中位数本身，您可以根据需要向左或向右移动指针。这不需要任何扩充并且可能会更快一些，但它会向每个节点添加两个额外的指针。

希望这对您有所帮助!