如果您有 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) 时间，因为您可以通过比较索引来遍历。
有没有更好的办法？
问问题
2802 次
1 回答
6
如果您需要优化中值查询，则增强 AVL 树以存储子树大小通常是这里的最佳方法。它需要时间 O(log n)，非常快。
如果您要计算中位数很多次，您可能会使用增广树并缓存中位数，以便您可以在 O(1) 时间内读取它。每次进行插入或删除时，您可能需要重新计算时间 O(log n) 的中位数，这会稍微减慢速度，但不会影响渐近成本。
另一种选择是将双向链表通过树中的节点串接，以便您可以在恒定时间内从节点导航到其后继或前任。如果你这样做，那么你可以存储一个指向中间元素的指针，然后在插入或删除时，根据需要将指针向左或向右移动。如果您删除中位数本身，您可以随意向左或向右移动指针。这不需要任何扩充并且可能会更快一些，但它会在每个节点中添加两个额外的指针。
希望这可以帮助！
于 2014-05-22T18:08:21.137 回答