树¶

基本概念¶

树是一种层次化的数据结构，在现实生活和计算机科学中都有广泛应用:

• 现实生活: 组织架构、家族谱系、生物分类等
• 计算机领域: 文件系统、DOM、抽象语法树（AST）、数据库索引（B/B+树）、路由表（前缀树/Trie）、决策树（机器学习）等

树的遍历是许多算法的基础，如动态规划（DFS 关注节点状态）、回溯（关注决策路径）等。掌握树的操作，对理解算法设计至关重要。

树的性质¶

• 第 i 层最多有 \(2^{i-1}\) 个结点
• 如果二叉树的深度为 k，那么此二叉树 最多有 \(2^k-1\) 个结点

二叉树分类¶

Perfect Binary Tree

Complete Binary Tree

Full Binary Tree

完美二叉树¶

所有层的节点都被完全填满。在完美二叉树中，若树的高度为 \(h\)，则节点总数为 \(2^{(h+1)}-1\)，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。

完全二叉树¶

仅允许最底层的节点不完全填满，且最底层的节点必须从左至右依次连续填充。二叉堆是完全二叉树的重要应用场景。

由于完全二叉树的性质，使其在数组中可以被连续存储（数组索引可按 1-based 或 0-based 约定）。

满二叉树¶

非叶节点都有 0 个或两个子节点。一个有趣的规律是：叶节点的数量=内部节点数量+1

树的遍历¶

二叉树的遍历分为 广度优先（BFS） 和 深度优先（DFS） 两种，其中 DFS 又分为前序、中序、后序遍历。

关于遍历算法的详细讲解（BFS vs DFS、递归/迭代实现、四种解题模式等），请参考 树的遍历算法。

特殊树结构¶

堆（Heap）¶

堆是一种满足堆性质的完全二叉树，常用来实现 优先队列。堆分为小顶堆和大顶堆两种类型。

视频：堆排序动画讲解

如图所示，两张图分别维护了前 12 个最大值和最小值。堆顶元素 1 和 9 扮演了 “门槛值”（Threshold） 的角色：

• 小顶堆（留大）：只有 > 1 的元素才有资格入堆。比如，若插入 0，因 0 < 1 被直接拦截；若插入 10，因 10 > 1 可以入堆，此时 1 被弹出，2（根节点的最小子节点）成为新的堆顶。
• 大顶堆（留小）：只有 < 9 的元素才有资格入堆。

常见操作的时间复杂度：

• push / pop（上浮或下沉）: \(O(log n)\)。建堆时，需要不断比较插入元素与插入位置元素的大小，插入后还要对子节点沉浮以保证堆的有序性。
• peek / top: \(O(1)\)
• size / isEmpty: \(O(1)\)

应用场景：

• 优先队列（任务调度、事件驱动、作业排队等）：按优先级快速取出最小/最大元素。
• 路径与图算法：Dijkstra、A* 等需要按最小代价取节点的算法（通常使用小顶堆）。
• Top‑k 问题：遍历元素并维护一个大小为 k 的小顶堆，堆顶即为第 k 大元素；时间复杂度 \(O(n log k)\)，空间 \(O(k)\)。
• 流式数据 / 实时排行榜：数据持续到达时，用小顶堆维护前 k 个最大值（当堆大小超过 k 时弹出堆顶）。
• 合并 k 个有序流 / 滑动窗口：合并 k 个有序数组/链表常用小顶堆；滑动窗口可以用堆维护窗口内的最大/最小值，但要注意堆不擅长做任意位置删除，常配合延迟删除或索引映射。
• 堆排序（Heap Sort）：先建堆（\(O(n)\)）再持续 pop 得到有序序列，总体 \(O(n log n)\)，可原地实现。

经典题目

• 215. Kth Largest Element in an Array — 数组中第 K 个最大元素（Top-k / 堆）
• 347. Top K Frequent Elements — 前 K 个高频元素（哈希 + 堆）

二叉搜索树（BST）¶

每个节点的数值比左子树上的节点大，比右子树上的节点小。排序二叉树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为 \(O(logn)\)。二叉搜索树相比于有序数组的二分搜索，在保证搜索效率不变的情况下，插入和删除不需要移动大量的元素，从而提升整体效率。

BST 有两种不同的写法，处理细节也不同：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

left, right := 0, len(nums)-1
for left <= right {  // ← 闭区间必须用 <=，以确保所有元素都被搜索
    mid := left + (right-left)/2 // ← 避免 int 溢出
    if nums[mid] < target {
        left = mid + 1   // 排除 mid 并查找右侧区间
    } else if nums[mid] > target {
        right = mid - 1  // 排除 mid 并查找左侧区间
    } else {
        return mid
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

left, right := 0, len(nums)  // ← right 初始化为 len(nums)
for left < right {  // ← 用 <
    mid := left + (right-left)/2
    if nums[mid] < target {
        left = mid + 1
    } else if nums[mid] > target {
        right = mid  // ← 不减1，因为 right 本身不包含
    } else {
        return mid
    }
}

以上是基础的二分查找，当找到目标值后立即返回。但在实际应用中，数组可能包含重复元素，此时我们需要找到目标值的 左边界（第一次出现的位置）或 右边界（最后一次出现的位置）。这两种变体只需在找到目标后，继续向左或向右收缩搜索区间即可实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

left, right := 0, len(nums)-1
for left <= right {
    mid := left + (right-left)/2
    if nums[mid] < target {
        left = mid + 1
    } else if nums[mid] > target {
        right = mid - 1
    } else {
        right = mid - 1  // ← 关键：找到后继续向左收缩
    }
}

// 检查越界和是否找到
if left >= len(nums) || nums[left] != target {
    return -1
}

return left

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

left, right := 0, len(nums)-1
for left <= right {
    mid := left + (right-left)/2
    if nums[mid] < target {
        left = mid + 1
    } else if nums[mid] > target {
        right = mid - 1
    } else {
        left = mid + 1  // ← 关键：找到后继续向右收缩
    }
}

// 检查越界和是否找到
if right < 0 || nums[right] != target {
    return -1
}

return right

左右边界的应用场景：

• 在有序数组中查找元素的第一次和最后一次出现位置
• 统计某个元素在有序数组中出现的次数：count = rightBound - leftBound + 1
• 经典题目：34. Find First and Last Position of Element in Sorted Array

平衡二叉树¶

AVL树¶

AVL 得名于两位苏联犹太人发明者：Adelson-Velsky and Landis

由于任何二叉树都可能退化为链表，所有操作的时间复杂度将从 \(O(log n)\) 劣化为 \(O(n)\) 。而 AVL 树则解决了二叉树退化为链表的问题，可以确保在持续添加和删除节点后，AVL 树不会退化，从而使得各种操作的时间复杂度保持在 \(O(log n)\) 级别。

每个节点的左右两子树高度差都不超过 1 的二叉树。它能在 \(O(log n)\) 内完成插入、查找和删除操作。

• 如果二叉树不做维护，会退化为链表，从而导致查找效率的急剧下降，因此需要不断维护二叉树尽可能的左右平衡，从而保证查找效率。
• 在 AVL 树中，任一节点左右子树高差只会有-1、0、1 三个值
• 四种旋转情况的选择条件：

Balanced Binary Tree

Imbalanced Binary Tree

AVL 树的应用场景：

组织和存储大型数据，适用于 高频查找、低频增删 的场景，如用于构建数据库中的索引系统。

红黑树相比于 AVL 树来说，平衡条件更宽松，插入与删除节点所需的旋转操作更少，节点增删操作的平均效率更高。

红黑树¶

红黑树在保留 AVL 树高效查找特性的同时，对 AVL 树的再平衡性能做了优化。

一种自平衡二叉搜索树，常用于关联数组、字典。红黑树相对于 AVL 树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于 AVL 树，因此标准库大都采用红黑树。

红黑树的规则如下：

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是 NIL 节点）。
4. 每个红色节点必须有两个黑色的子节点。（或者说不存在两个相邻的红色节点）（或者说红色节点的父节点和子节点均是黑色的）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（保证平衡的关键）

推论：

• 最长路径 \(<=\) 最短路径*2
• 红色的目的是触发平衡机制
• RBT 中，空节点是有效节点，因此叶节点是空节点
• AVL 对比 RBT 来看，只在搜索方面有微弱优势：由于 AVL 的平均高度比 RBT 更矮，因此理论查找速度更快，但在实际工程里，这点差距往往可以忽略（比如缓存命中、磁盘 I/O 延迟远远大于树的查找开销）

B/B+树¶

B 树¶

B 树和红黑树都是由德国计算机科学家 Rudolf Bayer 在 1972 年发明

由于内存对随机访问友好，磁盘对顺序访问友好，因此红黑树可以在内存环境中高效运行，但随着数据规模的增大，磁盘管理数据的效率就大幅下降，因此出现了针对磁盘优化的 B 树。

B 树是一个一般化的二叉搜索树，每个节点可以拥有两个以上的子节点。该树是自平衡树，能保持数据有序，让数据的查找、顺序访问、插入、删除都在 \(O(log n)\) 时间内完成。

一个Ｂ树通过约束所有叶子节点在相同深度来保持平衡。深度在元素添加至树的过程中缓慢增长，而整体深度极少地增长，并导致所有叶子节点与根节点距离加 1。

B 树的生长方式：向上生长。B 树的所有叶子节点必须在同一层，因此 B 树永远不会在一个叶子节点下挂载新的节点来增加数据，这会破坏平衡。 B 树插入数据时，会发生分裂和提升，真正的修改发生在父节点，它接受了被提升上来的键，并更新了其子节点指针。

B+ 树¶

B+ 树通过将数据存储在叶子节点、叶子节点间通过链表相连解决了 B 树的以下问题：

• 在内部节点也存储数据，这导致 B 树的查询性能不稳定。查询性能的稳定性和可预测对于数据库的性能估算和优化至关重要
• 顺序访问和范围访问效率极低
• B+树仅在叶子节点存储数据，内部节点仅存储指针，相比 B 树能存储更多索引键，这使得 树的阶数更高，树更矮胖，最终减少了磁盘的 I/O 次数 。一个拥有千万级数据的 B+树，其高度通常只有 3 到 4 层。这意味着任何一次查询，最多只需要 3 到 4 次磁盘 I/O，性能极高。

基于 B+树的以上优点，是数据库索引（MySQL 的 InnoDB）、文件系统的常用结构。

前缀树（Trie）¶

Trie 是一种专门用于高效处理字符串集合的多叉树结构，在搜索引擎的自动补全、拼写检查、IP 路由等场景中有广泛应用。 核心特性：

• 前缀搜索时间复杂度：\(O(m)\)（m 为字符串长度）
• 适用于字符串集合的快速查找和前缀匹配

详细内容请参考：Trie 数据结构详解

平衡树进化之路¶

经典题目¶

评论