性能 – 从AVL树获得中位数？

如果你有一个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)时间,因为你可以通过比较索引进行遍历.

有没有更好的办法？

如果需要优化中值查询,则增加AVL树以存储子树大小通常是最佳方法.它需要时间O(log n),这非常快.

如果您要计算中位数很多次,您可能会使用扩充树并缓存中值,以便您可以在时间O(1)中读取它.每次进行插入或删除时,您可能需要重新计算时间中位数O(log n),这会使事情减慢一些但不会影响渐近成本.

另一种选择是通过树中的节点对双向链表进行线程化,以便您可以在恒定时间内从节点导航到其后继节点或前导节点.如果这样做,那么您可以存储指向中间元素的指针,然后在插入或删除时,将指针移动到适当的左侧或右侧.如果你删除中位数,你可以根据需要左右移动指针.这不需要任何扩充,可能会更快,但它会在每个节点中添加两个额外的指针.

希望这可以帮助！