03 · 树与堆

这一篇是 04 数据库的前置。不先搞懂"树高决定查找次数"，B+ 树就只是死记硬背。

一句话本质

• 树：用"分叉"把查找范围一层层砍半，把 O(n) 变成 O(log n)。
• 堆：只维护"局部有序"（父节点 ≥ 或 ≤ 子节点），用最小代价拿到最值。

生活类比

结构	场景
二叉树	家族族谱，每个人最多两个孩子
二叉搜索树	查字典：大了往后翻，小了往前翻
平衡树	一个强迫症管理员，每次放书后都要把书架调平
堆	急诊分诊：不要求全员排队有序，只要求"最严重的永远在最前面"
完全二叉树	剧院座位：一排排坐满，最后一排从左往右坐

核心机制

一、二叉树的四种遍历（必须能默写）

        1
       / \
      2   3
     / \   \
    4   5   6

前序（根左右）：1 2 4 5 3 6     < 复制一棵树
中序（左根右）：4 2 5 1 3 6     < 二叉搜索树的中序是升序！
后序（左右根）：4 5 2 6 3 1     < 释放内存、算表达式
层序（BFS）  ：1 2 3 4 5 6     < 用队列

中序遍历 BST 得到升序序列——这是 BST 最重要的性质，面试常考"验证 BST"就是用这个。

二、二叉搜索树（BST）

规则：左子树所有节点 < 根 < 右子树所有节点

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

查找 6：8 > 左 > 3 > 右 > 6     （3 次比较，而不是 7 次）

查找复杂度 = 树高。

致命问题：退化成链表

按 1,2,3,4,5 顺序插入：

1
 \
  2
   \
    3
     \
      4
       \
        5

查找 5 > 要比较 5 次，退化成 O(n)

为什么会退化：BST 的形态完全由插入顺序决定。有序插入是最坏情况。

三、平衡树：怎么"保持平衡"

AVL 树：严格要求"左右子树高度差 ≤ 1"，不平衡就旋转。

四种不平衡（以"失衡节点"为参照）：

LL（左左）：插入到左子树的左边 > 右旋
RR（右右）：插入到右子树的右边 > 左旋
LR（左右）：插入到左子树的右边 > 先左旋再右旋
RL（右左）：插入到右子树的左边 > 先右旋再左旋

右旋示意：
      y                x
     / \              / \
    x   C    >       A   y
   / \                  / \
  A   B                B   C

红黑树：不追求严格平衡，用"颜色 + 5 条规则"保证"最长路径 ≤ 最短路径的 2 倍"，树高仍是 O(log n)。

	AVL	红黑树
平衡程度	严格（高度差 ≤1）	宽松（最长 ≤ 2×最短）
查找	略快（树更矮）	略慢
插入删除	慢（旋转多）	快（旋转少）
用在哪	读多写少	通用（Java TreeMap、Linux 内核、C++ map）

为什么工程上多用红黑树：插入删除的旋转次数少，综合性能更好。AVL 更适合"读远多于写"的场景。

四、堆：用数组实现的完全二叉树

堆的两条性质：

1. 结构性：是完全二叉树（除最后一层外都满，最后一层靠左）。
2. 有序性：大顶堆中，每个父节点 ≥ 两个孩子（小顶堆反之）。

为什么用数组存（关键）：

        9
       / \
      7   8
     / \  /
    3  5 6

数组：[9, 7, 8, 3, 5, 6]
下标： 0  1  2  3  4  5

关系（0 起）：
  父 = (i - 1) / 2
  左孩子 = 2i + 1
  右孩子 = 2i + 2

完全二叉树用数组存，不浪费任何空间（普通二叉树用数组会浪费大量空位）。这是堆高效的根本原因——没有指针，缓存友好。

三个核心操作：

① 插入（上浮 sift-up）
   放到数组末尾 > 和父节点比较 > 比父大就交换 > 一直往上
   O(log n)

② 删除堆顶（下沉 sift-down）
   把最后一个元素放到堆顶 > 和较大的孩子比较 > 比孩子小就交换 > 一直往下
   O(log n)

③ 建堆（heapify）
   从最后一个非叶子节点开始，依次下沉
   复杂度 O(n)，不是 O(n log n)！

"建堆是 O(n)"是高频考点：虽然每个节点下沉最多 O(log n)，但大部分节点在底层、下沉距离很短。数学求和后是 O(n)。直观理解：越往下节点越多，但下沉越少。

五、跳表（Redis 的选择）

有序链表查找 O(n)：
  1 > 3 > 5 > 7 > 9 > 11 > 13 > 15

加多级索引后：
  L2:  1 --------> 7 --------> 13
  L1:  1 --> 3 --> 7 --> 9 --> 13 --> 15
  L0:  1 > 3 > 5 > 7 > 9 > 11 > 13 > 15

查找 11：L2 到 7 > L1 到 9 > L0 到 11    （3 步而不是 6 步）

跳表 vs 红黑树：

• 跳表实现简单得多（不用旋转，只有指针操作）。
• 范围查询天然支持（底层是链表，顺序扫）。
• 并发友好（改局部指针即可，锁粒度小）。
• 代价：空间换时间（每层索引额外指针），最坏情况 O(n)（但概率极低）。

Redis 的 ZSet 用跳表，就是因为"范围查询 + 实现简单 + 并发友好"这三点。

为什么这么设计

反事实 1：如果 BST 不平衡

退化成链表，查找 O(n)。这就是为什么需要平衡树——不是为了"更快"，是为了保证最坏情况也是 O(log n)。

反事实 2：如果堆要求全局有序

那就得用排序数组：插入 O(n)（要挪动），取最值 O(1)。 堆只要求"局部有序"：插入 O(log n)，取最值 O(1)。用"放弃全局有序"换"插入快"。

这就是堆的价值：只在你需要的那个维度上保持有序。

反事实 3：如果树每个节点只存一个值（接数据库）

1000 万条数据，二叉树高 ≈ log₂(1000万) ≈ 24 层。 每层一次磁盘 IO > 24 次 IO，每次 10ms > 240ms。

如果每个节点能存 500 个值（多叉树），树高降到 log₅₀₀(1000万) ≈ 3 层 > 3 次 IO，30ms。

这就是 B 树 / B+ 树存在的理由（详见 索引与 B+ 树）。二叉树在内存里很好，但在磁盘上不行——因为磁盘 IO 的次数 = 树高。

面试怎么问

Q：二叉树的遍历方式？

四种：前序（根左右）、中序（左根右）、后序（左右根）、层序（BFS 用队列）。 必补一句：BST 的中序遍历是升序，所以"验证 BST"可以中序遍历看是否递增。

Q：为什么需要平衡树？

因为普通 BST 的形态由插入顺序决定，有序插入会退化成链表，查找从 O(log n) 变成 O(n)。平衡树通过旋转保证树高始终是 O(log n)，保证最坏情况。

Q：红黑树和 AVL 的区别？

AVL 严格平衡（高度差 ≤1），查找快但插入删除旋转多；红黑树宽松平衡（最长 ≤ 2×最短），插入删除更快。工程上多用红黑树，因为写操作更频繁。

Q：堆的插入和删除怎么做？复杂度？

插入：放末尾，上浮，O(log n)。 删除堆顶：末尾元素换到堆顶，下沉，O(log n)。 加分：建堆是 O(n)，不是 O(n log n)。

Q：为什么堆用数组存？

因为堆是完全二叉树，可以用下标直接算出父子关系（2i+1、2i+2），不需要指针。省空间、缓存友好、实现简单。

追问链：

二叉树有什么用？
  > BST 查找多快？（O(树高)）
    > 什么情况下变慢？（有序插入 > 退化成链表 > O(n)）
      > 怎么解决？（平衡树：AVL / 红黑树）
        > 为什么工程上用红黑树？（旋转少，写性能好）
          > 那数据库为什么不用红黑树？（树太高，磁盘 IO 次数多）
            > 用什么？（B+ 树，多叉，树高 3~4 层）

和其他知识的连接

• < 来自 复杂度与数组、链表：堆用数组存，完全二叉树的下标关系是数组特性的应用
• < 来自 栈、队列与哈希表：优先队列的实现是堆；HashMap 冲突严重转红黑树
• > 影响 图与并查集：Dijkstra 用优先队列（堆）优化；并查集用"按秩合并"控制树高
• > 影响 索引与 B+ 树：这是最重要的一条连接——B+ 树是"多叉平衡树 + 叶子链表"，解决了二叉树在磁盘上树高过大的问题
• > 影响 排序与二分：堆排序、Top K 问题
• > 影响 工程实践：Java TreeMap（红黑树）、PriorityQueue（堆）、Redis ZSet（跳表）、Linux 内核的 CFS 调度器（红黑树）

自测 3 问

Q1：为什么建堆是 O(n)，而"插入 n 次"是 O(n log n)？

点开看答案

因为下沉的节点数和下沉深度成反比。

完全二叉树中：

• 约 一半的节点是叶子，下沉 0 层。
• 约 1/4 的节点在倒数第二层，最多下沉 1 层。
• 约 1/8 的节点最多下沉 2 层。
• ...

总代价 ≈ n/2×0 + n/4×1 + n/8×2 + ...，这个级数收敛到 O(n)。

而"插入 n 次"是每个元素都从底部开始上浮，平均上浮 log n 层，所以是 O(n log n)。

直觉：建堆是从下往上，大部分节点在底部、几乎不用动；插入是从上往下，每个都要走完全程。

Q2：为什么数据库不用红黑树做索引？

点开看答案

因为树太高，磁盘 IO 次数太多。

红黑树是二叉树，1000 万条数据树高约 24 层。数据库索引存在磁盘上，每访问一个节点就是一次磁盘 IO（即使有缓存，未命中时也要 10ms 级）。24 次 IO = 240ms，无法接受。

B+ 树是多叉树，一个节点就是一个磁盘页（16KB），能存几百个键。树高降到 3~4 层，只需 3~4 次 IO。

根本区别：内存里访问节点几乎免费，所以二叉树够用；磁盘上访问节点极贵，必须减少访问次数，也就是降低树高，也就是增加分叉数。

这也是"数据结构的选择依赖于存储介质"的经典例子。

Q3：堆能不能做范围查询？

点开看答案

不能（高效地）。

堆只保证"父节点 ≥ 子节点"，兄弟之间、父子之外的节点之间没有任何顺序关系。

所以查"所有大于 50 的元素"：

• 堆顶是最大值，但第二大在哪？不知道，可能在第二层任意位置。
• 只能全遍历 O(n)。

堆适合的场景只有：反复取最值（优先队列、Top K、任务调度）。一旦需要"有序遍历"或"范围查询"，就得用平衡树或排序数组。

类比失效处 / 易错点

• "族谱"类比会让人以为树一定是二叉的。实际有多叉树（B 树、字典树 Trie）。
• "平衡树查找更快"不严谨。平衡树不是"比 BST 快"，是"保证最坏情况不退化"。数据随机时，普通 BST 平均也是 O(log n)。
• 堆不等于有序。堆只能保证堆顶是极值，中间元素无序。堆排序之所以能排序，是因为反复"取堆顶 + 下沉"。
• 红黑树不是"完全平衡"。它允许最长路径是最短路径的 2 倍，所以查找最坏是 2log n，不是严格 log n。
• "完全二叉树"和"满二叉树"不是一回事。满二叉树是每层都满；完全二叉树只要求"最后一层靠左连续"。

✅ 验收清单

• 能默写二叉树四种遍历的序列，并说出各自的典型用途
• 能解释"BST 为什么会退化成链表"，并画出退化后的样子
• 能说出 AVL 和红黑树的区别，以及工程上为什么多用红黑树
• 能写出堆的数组下标关系（父、左孩子、右孩子），并解释"为什么堆用数组存"
• 能说清堆的插入（上浮）和删除（下沉）步骤，复杂度各是多少
• 能解释"建堆为什么是 O(n) 而不是 O(n log n)"
• 能说出"数据库为什么不用红黑树"（要提到树高与磁盘 IO 次数的关系）
• 能说出堆不能做范围查询的原因
• 合上书，用自己的话讲 3 分钟，中途不卡壳