树与堆：二叉树、平衡树与优先队列

发布于 2026-08-17 15:07 · 最后编辑于 2026-08-17 15:07 · 字数 3,139 👁 39 次阅读

本文覆盖二叉树（遍历/完全/满）、BST、AVL 树、红黑树、堆（堆排序/优先级队列）和 Trie 树，重点理解各数据结构的适用场景和操作复杂度，以及设计背后的"为什么"。

章节	说明
二叉树基础	定义、存储、三种遍历
二叉搜索树（BST）	插入/删除/查找，三种删除场景
平衡二叉树	AVL 树与红黑树，工程选型对比
堆	最大堆/最小堆、核心操作、堆排序、应用
Trie 树	字符串前缀匹配，空间优化

二叉树基础

核心概念

概念	说明	为什么这样定义
根节点	没有父节点的节点	树的唯一入口，所有遍历从此出发
叶子节点	没有子节点的节点	递归终止条件，遍历边界
高度（Height）	从底层往上数，从 0 开始	衡量树的深度，影响操作复杂度
深度（Depth）	从根节点往下数，从 0 开始	衡量节点距根的距离
层（Level）	从根节点往下数，从 1 开始	按层遍历（BFS）的自然分层

满二叉树 vs 完全二叉树

满二叉树：叶子节点全在最底层，每个非叶子节点都有左右两个子节点。节点数恰好为 2ⁿ-1。

完全二叉树：叶子节点在最底下两层，最后一层叶子节点靠左排列，其他层节点数达到最大。

为什么完全二叉树适合数组存储？ 节点位置可以用下标直接计算（父节点 i/2，左子 2i，右子 2i+1），无需额外指针，节省内存。堆就是完全二叉树的典型应用。

存储方式

链式存储：每个节点有 left、right 两个指针，灵活，适合大多数树（BST、AVL、红黑树）。

数组顺序存储（适合完全二叉树）：

根节点存储在 i=1 的位置（i=0 空置，方便计算）
左子节点：2*i
右子节点：2*i+1
父节点：i/2（整除）

三种遍历

tree traversal

三种遍历本质上是递归访问顺序不同：前序先处理根，后序先处理子树，中序在 BST 中天然得到有序序列。

// 前序遍历：根 → 左 → 右
// 用途：复制树结构、序列化/反序列化
void preOrder(Node root) {
    if (root == null) return;
    print(root);          // 先处理根
    preOrder(root.left);
    preOrder(root.right);
}

// 中序遍历：左 → 根 → 右
// 用途：BST 中序遍历得到有序序列（排序的副产品）
void inOrder(Node root) {
    if (root == null) return;
    inOrder(root.left);
    print(root);          // 根在中间
    inOrder(root.right);
}

// 后序遍历：左 → 右 → 根
// 用途：计算目录大小、删除树（先删子节点再删父节点）
void postOrder(Node root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    print(root);          // 最后处理根
}

遍历时间复杂度：O(n)，每个节点恰好被访问一次。

二叉搜索树（BST）

二叉搜索树（Binary Search Tree） 满足：左子树所有节点 < 根节点 < 右子树所有节点。

为什么这个性质有用？ 查找时每次比较都能排除一半子树，平均 O(logn)，中序遍历直接输出有序序列，天然支持范围查找。

插入与删除

tree bst

删除节点的三种情况

情况	操作	原因
叶子节点	直接删除	无子节点，不影响树结构
只有一个子节点	用子节点替代	子节点继承位置，BST 性质不变
有两个子节点	找右子树最小节点（中序后继）替代，再删该节点	中序后继是比被删节点大的最小值，替代后 BST 性质保持

// 查找操作（迭代版，避免递归栈开销）
Node find(Node root, int data) {
    while (root != null) {
        if (data < root.val) root = root.left;
        else if (data > root.val) root = root.right;
        else return root;
    }
    return null;
}

操作复杂度

操作	平均	最坏（退化为链表）
查找	O(logn)	O(n)
插入	O(logn)	O(n)
删除	O(logn)	O(n)
中序遍历（输出有序序列）	O(n)	O(n)

退化场景：按升序插入 [1,2,3,4,5]，BST 退化为链表，高度 n，查找 O(n)。这是 AVL/红黑树存在的根本原因。

BST vs 散列表

维度	BST	散列表
时间复杂度	O(logn)	O(1)
有序输出	支持（中序遍历）	不支持
范围查找	支持	不支持
内存消耗	较少	较多（装载因子）

需要有序性或范围查找时选 BST；只需快速点查时选散列表。

平衡二叉树

BST 在最坏情况下退化为链表，平衡二叉树通过旋转操作维持树高在 O(logn)。

AVL 树

AVL 树严格要求任意节点左右子树高度差不超过 1（平衡因子 ∈ {-1, 0, 1}）。

查找/插入/删除：O(logn)
每次插入/删除后可能需要旋转（单旋或双旋）调整
适合查询多、更新少的场景（如只读索引）

红黑树

红黑树是一种近似平衡的二叉查找树，高度不超过 2log₂n。用颜色代替严格高度约束，换取更少的旋转次数。

五条性质：

节点是红色或黑色
根节点是黑色
叶子节点（NIL）是黑色
红色节点的两个子节点都是黑色（不能有连续红节点）
从任意节点到其叶子节点的路径，包含相同数目的黑色节点

为什么工程中用红黑树而不是 AVL 树？

维度	AVL 树	红黑树
平衡严格度	严格（高度差 ≤ 1）	近似（高度 ≤ 2log₂n）
查找效率	略高（树更矮）	略低
插入/删除调整	频繁旋转，成本高	旋转次数少（最多 3 次），成本低
适用场景	查多改少	插入/删除/查找均衡

工程选择红黑树的核心原因：大多数场景写操作不可忽视，红黑树通过放松平衡条件减少旋转次数，整体吞吐量更高。

实际应用：Java TreeMap/TreeSet/HashMap（链表转树）、Linux 内核进程调度（CFS）、C++ std::map。

堆

堆（Heap） 是满足堆性质的完全二叉树，用数组存储（利用完全二叉树的下标计算优势）：

大顶堆：每个节点的值 ≥ 子树中所有节点的值
小顶堆：每个节点的值 ≤ 子树中所有节点的值

为什么堆用数组而不用链表？ 完全二叉树的父子关系可以用下标直接计算，无需指针，内存连续，缓存友好，节省每个节点 2 个指针的空间。

核心操作

tree heap ops

插入（从下往上堆化）：将新元素放到数组末尾，与父节点比较，若不满足堆性质则交换，向上递归。

public void insert(int data) {
    if (count >= n) return;      // 堆已满
    a[++count] = data;           // 放到末尾
    int i = count;
    while (i / 2 > 0 && a[i] > a[i / 2]) { // 大顶堆：子 > 父则交换
        swap(a, i, i / 2);
        i = i / 2;               // 向上移动
    }
}

删除堆顶（从上往下堆化）：将最后一个元素移到堆顶，与较大子节点比较，向下递归。

为什么不直接删堆顶？ 直接删除会破坏完全二叉树结构（产生空洞），改用末尾元素填充再堆化，保持完全二叉树形态。

public void removeMax() {
    if (count == 0) return;
    a[1] = a[count--];          // 末尾元素移到堆顶
    heapify(a, count, 1);       // 从堆顶向下堆化
}

private void heapify(int[] a, int n, int i) {
    while (true) {
        int maxPos = i;
        if (i * 2 <= n && a[i] < a[i * 2]) maxPos = i * 2;
        if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) maxPos = i * 2 + 1;
        if (maxPos == i) break;  // 已满足堆性质
        swap(a, i, maxPos);
        i = maxPos;
    }
}

堆排序

分两步：

建堆：从 n/2 开始向前，对每个节点做从上往下堆化，时间复杂度 O(n)
排序：反复将堆顶（最大值）与末尾元素交换，堆大小减一，再堆化，时间复杂度 O(nlogn)

public static void sort(int[] a, int n) {
    buildHeap(a, n);        // O(n)：建大顶堆
    int k = n;
    while (k > 1) {
        swap(a, 1, k--);    // 将最大值放到末尾
        heapify(a, k, 1);   // O(logn)：重新堆化
    }
}

private static void buildHeap(int[] a, int n) {
    for (int i = n / 2; i >= 1; --i) { // 从最后一个非叶节点开始
        heapify(a, n, i);
    }
}

建堆为什么是 O(n) 而不是 O(nlogn)？ 从底部开始建堆，底层节点需要堆化的高度很小。数学上求和：∑(i=1 to logn) i × n/2ⁱ = O(n)。

堆排序 vs 快速排序

两者时间复杂度同为 O(nlogn)，但实际性能快排更好：

原因	说明
缓存不友好	堆排序访问数组时跳跃（1→2→4→8...），快排顺序访问，缓存命中率高
交换次数多	建堆阶段会打乱原有有序度，增加总交换次数

堆的应用

优先级队列：用大顶堆/小顶堆实现，O(logn) 插入，O(1) 查看最值，O(logn) 删除最值。Java PriorityQueue 即堆实现。

Top K 问题：维护一个大小为 K 的小顶堆，遍历数据，若比堆顶大则替换堆顶并堆化。时间复杂度 O(nlogK)，空间 O(K)。

为什么用小顶堆而不是大顶堆？小顶堆堆顶是 K 个数中最小的，方便判断新元素是否能进入 Top K。

求中位数：维护一个大顶堆（存较小的一半）和一个小顶堆（存较大的一半），保持两者大小相差不超过 1。中位数为大顶堆堆顶（或两堆顶的平均值）。

操作复杂度

操作	时间复杂度	说明
插入	O(logn)	向上堆化，最多 logn 次交换
删除堆顶	O(logn)	向下堆化，最多 logn 次交换
查看堆顶	O(1)	直接访问 a[1]
建堆	O(n)	数学证明，非直觉上的 O(nlogn)
堆排序	O(nlogn)	建堆 O(n) + n 次删除 O(logn)

Trie 树

Trie 树（前缀树） 是专门处理字符串匹配的树形数据结构，利用字符串的公共前缀减少存储和查询开销。

为什么不直接用散列表存字符串？ 散列表能做精确匹配，但不支持前缀查找（如"输入 hel，找所有以 hel 开头的词"）。Trie 天然支持前缀匹配，且多个字符串共享公共前缀，节省空间。

结构

tree trie

每个节点代表一个字符，从根节点到某个标记为"结尾"的节点的路径表示一个完整字符串。公共前缀只存储一次。

class TrieNode {
    char data;
    TrieNode[] children = new TrieNode[26]; // 英文字母
    boolean isEndingChar = false;           // 是否是某个词的结尾
}

class Trie {
    private TrieNode root = new TrieNode('/');

    // 插入：O(m)，m 为字符串长度
    public void insert(String text) {
        TrieNode p = root;
        for (int i = 0; i < text.length(); ++i) {
            int index = text.charAt(i) - 'a';
            if (p.children[index] == null) {
                p.children[index] = new TrieNode(text.charAt(i));
            }
            p = p.children[index];
        }
        p.isEndingChar = true; // 标记词尾
    }

    // 查找：O(m)
    public boolean find(String pattern) {
        TrieNode p = root;
        for (int i = 0; i < pattern.length(); ++i) {
            int index = pattern.charAt(i) - 'a';
            if (p.children[index] == null) return false;
            p = p.children[index];
        }
        return p.isEndingChar; // 必须是完整词，不能只是前缀
    }
}

操作复杂度

操作	时间复杂度	说明
插入	O(m)	m 为字符串长度，与词典大小无关
查找（精确）	O(m)	沿路径走 m 步
前缀匹配	O(m)	找到前缀节点后，DFS 收集所有词

空间消耗与优化

每个节点需存储子节点指针数组（26 个英文字母则需 26 个指针），内存消耗大，空间换时间。

优化方案	原理	适用场景
散列表代替数组	只存实际存在的子节点	字符集大、稀疏时
压缩 Trie（Radix Tree）	合并只有一个子节点的路径	词典较小时
Double Array Trie	用两个数组压缩存储	高性能场景（如分词器）

应用场景

搜索引擎关键词提示（输入前缀，返回候选词）
输入法联想词
路由器 IP 路由匹配（最长前缀匹配）
敏感词过滤（配合 AC 自动机实现多模式匹配）

参考资料

《数据结构与算法之美》— 23~29、35 章节

← 返回列表

(1 人打了分，平均分： 5.00)

暂无评论，来留下第一条吧。

登录或注册后才能发表评论

树与堆：二叉树、平衡树与优先队列

目录

二叉树基础

核心概念

满二叉树 vs 完全二叉树

存储方式

三种遍历

二叉搜索树（BST）

插入与删除

删除节点的三种情况

操作复杂度

BST vs 散列表

平衡二叉树

AVL 树

红黑树

为什么工程中用红黑树而不是 AVL 树？

堆

核心操作

堆排序

堆排序 vs 快速排序

堆的应用

操作复杂度

Trie 树

结构

操作复杂度

空间消耗与优化

应用场景

评论 (0)