动态维护变量中位数实战：二叉搜索树在实时数据流的应用

实时数据流场景下，数据会持续不断产生，需要动态计算当前所有数据的中位数，传统方式每次插入新数据后重新排序的时间复杂度较高，难以满足实时性要求。二叉搜索树凭借有序性和高效的插入、查询特性，成为该场景下的优质解决方案。

二叉搜索树维护中位数的核心思路

二叉搜索树的核心特性是左子树所有节点值小于根节点，右子树所有节点值大于根节点，中序遍历可以得到有序序列。要维护中位数，需要额外记录两个信息：当前树的总节点数，以及树中序遍历的前半部分最大节点和后半部分最小节点。

具体逻辑如下：

• 插入新节点时，按照二叉搜索树规则插入，同时更新总节点数
• 如果总节点数为奇数，中位数就是中序遍历的第 (n+1)/2 个节点
• 如果总节点数为偶数，中位数是中序遍历的第 n/2 和第 n/2 +1 个节点的平均值
• 为了提升查询效率，可以在节点中额外维护子树节点数量，避免每次都做完整中序遍历

带子树计数的二叉搜索树实现

首先定义二叉搜索树的节点结构，每个节点存储值、左右子节点指针，以及以当前节点为根的子树的总节点数：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    int subTreeSize; // 以当前节点为根的子树节点总数

    TreeNode(int val) {
        this.val = val;
        this.subTreeSize = 1;
        this.left = null;
        this.right = null;
    }
}

插入节点与更新子树大小

插入节点时，递归找到合适的位置插入，同时更新路径上所有节点的子树大小：

public class MedianFinder {
    private TreeNode root;

    public MedianFinder() {
        root = null;
    }

    // 插入新值
    public void addNum(int num) {
        root = insert(root, num);
    }

    private TreeNode insert(TreeNode node, int num) {
        if (node == null) {
            return new TreeNode(num);
        }
        if (num < node.val) {
            node.left = insert(node.left, num);
        } else {
            node.right = insert(node.right, num);
        }
        // 更新当前节点的子树大小
        node.subTreeSize = 1 + getSize(node.left) + getSize(node.right);
        return node;
    }

    // 获取节点子树大小，处理空节点情况
    private int getSize(TreeNode node) {
        return node == null ? 0 : node.subTreeSize;
    }
}

查询第k小元素

利用每个节点存储的子树大小，可以快速找到中序遍历的第k小元素，不需要完整遍历整棵树：

private int findKth(TreeNode node, int k) {
    int leftSize = getSize(node.left);
    if (k <= leftSize) {
        // 第k小元素在左子树
        return findKth(node.left, k);
    } else if (k == leftSize + 1) {
        // 当前节点就是第k小元素
        return node.val;
    } else {
        // 第k小元素在右子树，需要查找右子树的第 k - leftSize -1 小元素
        return findKth(node.right, k - leftSize - 1);
    }
}

动态获取中位数

根据总节点数的奇偶性，调用findKth方法获取对应位置的元素计算中位数：

public double findMedian() {
    int totalSize = getSize(root);
    if (totalSize % 2 == 1) {
        // 奇数，中位数是第 (totalSize + 1)/2 小元素
        return findKth(root, (totalSize + 1) / 2);
    } else {
        // 偶数，中位数是第 totalSize/2 和 totalSize/2 +1 小元素的平均值
        int leftMid = findKth(root, totalSize / 2);
        int rightMid = findKth(root, totalSize / 2 + 1);
        return (leftMid + rightMid) / 2.0;
    }
}

方案复杂度分析

该方案的时间复杂度如下：

如果二叉搜索树出现极端倾斜的情况，时间复杂度会退化为O(n)，实际生产中可以结合平衡二叉搜索树（如AVL树、红黑树）来避免该问题，保证稳定的时间复杂度。

二叉搜索树中位数实时数据流动态维护修改时间：2026-06-23 14:42:23