在AVL树中查找中位数

Question

我有一个 AVL 树，我想在 O(1) 中返回中值元素。
我知道每次插入新元素时都可以保存指向它的指针，而无需更改插入的运行时间（通过保存子树的大小并遍历直到找到第 n/2 个大小的子树）。
但我想知道我是否可以利用以下事实来做到这一点：在每次插入中，中位数都会“向右”移动，而在每次删除中，中位数都会“向左”移动。
以更一般的方式：如何使用前驱和后继跟踪 AVL 树中的第 i 个元素？

Answer 1

给定一个AVL（自平衡二叉搜索树），找到中位数。请记住，即使树是平衡的，您也不能只取根元素，因为即使树是平衡的，您也不知道中位数是否恰好是左儿子或右儿子的根元素。用于查找 AVL 中值的迭代算法。该算法基于每个 AVL 树的属性，您可以使用中序遍历获得包含该树的元素的排序集合。利用这个属性，我们可以获得节点的排序集合，然后找到中位数。该算法的时间和空间复杂度为 O(N)，其中 N 是树中的节点数。

public class AvlTreeMedian {

  BinaryTreeInOrder binaryTreeInOrder;

  public AvlTreeMedian() {
    this.binaryTreeInOrder = new BinaryTreeInOrder();
  }

  public double find(BinaryNode<Integer> root) {
    if (root == null) {
      throw new IllegalArgumentException("You can't pass a null binary tree to this method.");
    }

    List<BinaryNode<Integer>> sortedElements = binaryTreeInOrder.getIterative(root);
    double median = 0;
    if (sortedElements.size() % 2 == 0) {
      median = (sortedElements.get(sortedElements.size() / 2).getData() + sortedElements.get(
          sortedElements.size() / 2 - 1).getData()) / 2;
    } else {
      median = sortedElements.get(sortedElements.size() / 2).getData();
    }
    return median;
  }
}

Answer 2

我认为 AVL 树不是最好的数据结构，但这让我想起了以下 leetcode 问题：https://leetcode.com/problems/find-median-from-data-stream/description/

我想你可以做的是：

1. 维护2个堆，左MaxHeap和右MinHeap。正确的堆 包含大于左堆最大值的所有值。同样地 左堆包含的值全部小于或等于最小值 左边的堆。
2. 每次插入都会在将新值插入到正确的堆中后自动平衡堆。如果新值 > 左堆的 max，添加到右侧，否则添加到右侧堆
3. 每次删除也会自动平衡堆。给定一个值，我们可以使用左根和左根来找出它位于哪个堆中 正确的堆然后堆化无论我们从哪个堆中删除它（ O(log n) 运算）
4. 然后我们就可以在 O(1) 中得到中位数。如果两个堆共享相同数量的元素，则得到中位数 = (maxLeft + minRight) / 2， 否则，如果其中一个堆比另一个堆拥有更多元素 （在任何时候它都不应有超过 1 个额外元素 由于我之前描述的自动平衡，比另一个更好）然后 只需返回较大堆的根（根据定义，这是 中位数）。