从获取AVL树中位数？ [英] Get median from AVL tree?

问题描述

如果你有一个AVL树，什么是得到它的中位数的最好方法？中位数将被定义为具有索引CEIL元素（N / 2）（索引从1开始）中的排序的列表。

If you have an AVL tree, what's the best way to get the median from it? The median would be defined as the element with index ceil(n/2) (index starts with 1) in the sorted list.

因此​​，如果名单是

1 3 5 7 8

中位数为5。如果该列表是

the median is 5. If the list was

1 3 5 7 8 10

1 3 5 7 8 10

中位数为5。

如果你可以增加的树，我认为这是最好让每个节点知道子树的大小（节点数），（即1 + left.size + right.size）。利用这一点，最好的办法我能想到的品牌中位数搜索O（LG n）的时间，因为你可以通过比较索引遍历。

If you can augment the tree, I think it's best to let each node know the size (number of nodes) of the subtree, (i.e. 1 + left.size + right.size). Using this, the best way I can think of makes median searching O(lg n) time because you can traverse by comparing indexes.

有没有更好的办法？

推荐答案

增广的AVL树存储子树的大小一般是最好的办法在这里，如果你需要以优化位数的查询。这需要时间O（log n）的，这是pretty的快。

Augmenting the AVL tree to store subtree sizes is generally the best approach here if you need to optimize over median queries. It takes time O(log n), which is pretty fast.

如果你会计算平均庞大的次数，你可能会使用一种增强的树，也是缓存中值，以便可以在时间O（1）阅读。每次做一个插入或删除，则可能需要重新计算中位数时间为O（log n）的，它会慢下来了一点，但不会影响渐进成本。

If you'll be computing the median a huge number of times, you could potentially use an augmented tree and also cache the median value so that you can read it in time O(1). Each time you do an insertion or deletion, you might need to recompute the median in time O(log n), which will slow things down a bit but not impact the asymptotic costs.

另一种选择是将线穿过树的节点的双向链表，这样就可以从一个节点到其继承人或predecessor在固定时间内进行导航。如果你这样做，那么你可以存储一个指针到中间的元素，然后在插入或缺失，移动指针向左或向右适当。如果删除位数本身，你可以左右移动指针或向右，只要你愿意。这不需要任何增强，并可能会快一点，但它增加了两个额外的指针到每个节点。

Another option would be to thread a doubly-linked list through the nodes in the tree so that you can navigate from a node to its successor or predecessor in constant time. If you do that, then you can store a pointer to the median element, and then on an insertion or a deletion, move the pointer to the left or to the right as appropriate. If you delete the median itself, you can just move the pointer left or right as you'd like. This doesn't require any augmentation and might be a bit faster, but it adds two extra pointers into each node.

希望这有助于！

这篇关于从获取AVL树中位数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！