经典算法专栏 #06：基础数据结构

五大基础数据结构的深度解析：不止于"会用"，而是理解为什么红黑树能保证 O(logn)、哈希表 α=0.75 从何而来、并查集的近 O(1) 靠什么支撑。对应《算法导论》第 6、10~13、21 章。

目录

堆与优先队列

为什么用数组存完全二叉树

二叉堆是一棵完全二叉树（每层从左往右填满），这个约束使得可以用数组紧凑存储，不需要指针：

数组下标（从 1 开始）：
        1
      /   \
     2     3
   /  \   /  \
  4    5 6    7

节点 i 的父：⌊i/2⌋
节点 i 的左子：2i
节点 i 的右子：2i+1

为什么不用 0 开始？若下标从 0 开始，父节点是 ⌊(i-1)/2⌋，子节点是 2i+1 和 2i+2，稍复杂。CLRS 使用 1-indexed，Java PriorityQueue 内部实际也是 0-indexed 做了等价变换。

最大堆性质：A[⌊i/2⌋] ≥ A[i]——父 ≥ 子，根是全局最大值。

HEAPIFY：为什么是 O(logn)

MAX-HEAPIFY(i) 让节点 i 下沉到正确位置：

void maxHeapify(int[] a, int i, int n) {
    int l = 2 * i, r = 2 * i + 1, largest = i;
    if (l <= n && a[l] > a[largest]) largest = l;
    if (r <= n && a[r] > a[largest]) largest = r;
    if (largest != i) {
        swap(a, i, largest);
        maxHeapify(a, largest, n);  // 继续下沉
    }
}

递推式：T(n) ≤ T(2n/3) + O(1)（最坏情况下子树规模为 2n/3）

由主定理：p = log_{3/2}(1) = 0，f(n) = O(1) = O(n^0)，情况 2，T(n) = O(logn)。

直觉更简单：节点最多下沉树高次，树高 = ⌊log₂n⌋ = O(logn)。

BUILD-MAX-HEAP：为什么是 O(n) 而非 O(nlogn)

直觉上 n 个节点各做一次 O(logn) 的 heapify，应该是 O(nlogn)——但实际只有 O(n)，原因是大多数节点在树的底层，下沉代价很小：

void buildMaxHeap(int[] a, int n) {
    // 从最后一个非叶节点（⌊n/2⌋）开始向上 heapify
    for (int i = n / 2; i >= 1; i--)
        maxHeapify(a, i, n);
}

精确推导：高度为 h 的节点最多有 ⌈n/2^(h+1)⌉ 个，heapify 代价 O(h)：

总代价 = ∑(h=0 到 ⌊logn⌋) ⌈n/2^(h+1)⌉ · O(h)
       ≤ n · ∑(h=0 到 ∞) h/2^h
       = n · 2          （∑h/2^h = 2，等比级数求导结论）
       = O(n)

工程意义：建堆比"逐个 insert"快一倍。堆排序整体 O(nlogn)，但建堆阶段只用 O(n)。

实战例题：数组变为最大堆

输入 [4, 10, 3, 5, 1]（1-indexed），从 i=2 开始 heapify：

初始：[_, 4, 10, 3, 5, 1]   (_ 占位，从 1 开始)

i=2: 节点 10，子节点 5,1 → 10 最大，不动
i=1: 节点 4，子节点 10,3 → 10 最大，swap(4,10)
     → [_, 10, 4, 3, 5, 1]
     继续 heapify(2): 节点 4，子节点 5,1 → swap(4,5)
     → [_, 10, 5, 3, 4, 1]

最终最大堆：根 10，左子树 5→4,1，右子树 3

二叉搜索树

BST 性质与中序遍历

BST 不变量：对任意节点 x，其左子树所有键 ≤ x.key，右子树所有键 ≥ x.key。

最重要的推论：BST 的中序遍历（左→根→右）输出有序序列。这是 BST 能用于排序（树排序）的根本原因。

查找与插入

// 查找：每步排除一半，沿树向下，O(h)
TreeNode search(TreeNode root, int key) {
    if (root == null || root.val == key) return root;
    return key < root.val
        ? search(root.left, key)
        : search(root.right, key);
}

// 插入：找到合适的空位置放入，O(h)
TreeNode insert(TreeNode root, int key) {
    if (root == null) return new TreeNode(key);
    if (key < root.val)
        root.left  = insert(root.left, key);
    else if (key > root.val)
        root.right = insert(root.right, key);
    // key == root.val：重复键，视业务决定是否插入
    return root;
}

删除：三种情况完整推导

删除是 BST 中最复杂的操作，需要分三种情况保持 BST 不变量：

flowchart TD
    D["删除节点 z"] --> C1{"z 有几个子节点？"}
    C1 -->|0 个| A["直接删除 z<br/>父节点指向 null"]
    C1 -->|1 个| B["用 z 的唯一子节点<br/>替换 z 的位置"]
    C1 -->|2 个| E["找 z 的中序后继 y<br/>（右子树最小值）"]
    E --> F{"y 是 z 的右孩子？"}
    F -->|是| G["y 直接替换 z<br/>y 继承 z 的左子树"]
    F -->|否| H["y 的右孩子替换 y<br/>再用 y 替换 z"]

    style A fill:#d5e8d4,stroke:#82b366
    style B fill:#d5e8d4,stroke:#82b366
    style G fill:#fff2cc,stroke:#d6b656
    style H fill:#fff2cc,stroke:#d6b656

为什么用中序后继而非前驱？两者都行，CLRS 选后继是惯例。关键：中序后继是右子树中最小的节点，它没有左孩子（否则还有更小的），替换后 BST 不变量自然成立。

// 找右子树最小节点（中序后继）
TreeNode minimum(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}

TreeNode delete(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) {
        root.left = delete(root.left, key);
    } else if (key > root.val) {
        root.right = delete(root.right, key);
    } else {
        // 找到了，处理三种情况
        if (root.left == null)  return root.right; // 情况 1 & 2
        if (root.right == null) return root.left;  // 情况 2
        // 情况 3：找中序后继，用其值替换，再删后继
        TreeNode successor = minimum(root.right);
        root.val = successor.val;
        root.right = delete(root.right, successor.val);
    }
    return root;
}

退化与期望高度

最坏情况：按有序序列插入，BST 退化为链表，h = n - 1。

随机输入的期望高度：若 n 个互不相同的键以随机顺序插入，期望树高 E[h] = 2.5 logn（CLRS 定理 12.4 证明），操作期望 O(logn)。

工程启示：数据库索引不能用普通 BST——用户数据往往是有序的（ID 自增），必须用自平衡树（B树/红黑树）。

红黑树

五条性质

红黑树是每个节点带颜色标记的 BST：

1. 每个节点红色或黑色
2. 根节点黑色
3. NIL 叶节点黑色（所有真正的叶子都是哨兵 NIL，不存储数据）
4. 红节点的子节点必须是黑色（不存在相邻两个红节点）
5. 从任意节点到其后代 NIL 的所有路径，黑色节点数相同（黑高 bh 相同）

高度上界的完整证明

定理：含 n 个内部节点的红黑树，高度 h ≤ 2log₂(n+1)。

第一步：证明以 x 为根的子树，内部节点数 ≥ 2^bh(x) - 1

对黑高 bh(x) 做归纳：

基础：bh = 0 → x 是 NIL，内部节点数 = 0 = 2⁰ - 1 ✅

归纳：设黑高为 bh(x) 的节点，子树内部节点 ≥ 2^bh(x) - 1
     x 的每个子节点 c 的黑高：
       c 是黑色 → bh(c) = bh(x) - 1
       c 是红色 → bh(c) = bh(x)（红节点不计入黑高）
     由归纳假设，每个子树内部节点 ≥ 2^(bh(x)-1) - 1
     x 本身算 1 个节点：
     size(x) ≥ 1 + 2·(2^(bh(x)-1) - 1) = 2^bh(x) - 1 ✅

第二步：用性质 4 约束黑高与总高的关系

由性质 4（红节点子节点必须是黑色），从根到叶的路径上，至少一半节点是黑色：

bh(根) ≥ h/2   （其中 h 是树的总高度）

第三步：合并得出结论

由第一步：n ≥ 2^bh(根) - 1 ≥ 2^(h/2) - 1
⟹  n + 1 ≥ 2^(h/2)
⟹  log₂(n+1) ≥ h/2
⟹  h ≤ 2·log₂(n+1)  = O(logn)  ✅

直觉：五条性质联合起来，本质上是保证树不会"一侧特别长"。最坏形态是黑红交替的路径，是纯黑路径的 2 倍，因此总高不超过 2logn。

插入修复：三种情况逐步演示

插入节点 z，初始着色为红色（着红色是为了不破坏黑高性质 5，只可能违反性质 4）。

设 z 的父节点为 p，祖父为 g，叔叔为 u（p 的兄弟节点）：

flowchart TD
    Start["插入红节点 z<br/>p 也是红色（违反性质4）"] --> CaseCheck{"叔叔 u 的颜色？"}

    CaseCheck -->|"u 是红色"| Case1["Case 1：重新染色<br/>p、u → 黑色<br/>g → 红色<br/>z = g，继续向上检查"]

    CaseCheck -->|"u 是黑色"| ZCheck{"z 是 p 的<br/>哪侧子节点？"}
    ZCheck -->|"z 是右孩子<br/>（p 是 g 的左孩子）"| Case2["Case 2：左旋 p<br/>转换为 Case 3<br/>（z 变成左孩子）"]
    ZCheck -->|"z 是左孩子<br/>（p 是 g 的左孩子）"| Case3["Case 3：<br/>p → 黑色，g → 红色<br/>右旋 g<br/>完成！"]
    Case2 --> Case3

    style Case1 fill:#fff2cc,stroke:#d6b656
    style Case2 fill:#dae8fc,stroke:#6c8ebf
    style Case3 fill:#d5e8d4,stroke:#82b366

具体示例：向红黑树插入节点 4

插入前：
         7(黑)
        /     \
      3(红)    18(黑)
      /  \
   2(黑)  5(黑)

插入 4（红色），作为 5 的左孩子：
         7(黑)
        /     \
      3(红)    18(黑)
      /  \
   2(黑)  5(黑)
           /
          4(红)  ← 插入，父 5 是黑色，无冲突，直接完成！

换个例子，插入 1：
  1 作为 2 的左孩子，父 2 是黑色 → 直接完成

插入 0（假设 1 已在树中，0 作为 1 的左孩子）：
  父 1 是红色，叔叔 5 是黑色，0 是左孩子 → Case 3
  1 → 黑，2 → 红，右旋 2：
         7(黑)
        /     \
      3(红)    18(黑)
      /  \
   1(黑)  5(黑)
   / \
 0(红) 2(红)

工程中的红黑树

// Java TreeMap 内部：红黑树节点
static final class Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left, right, parent;
    boolean color = BLACK;  // 默认黑色
}

// 常见使用模式
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "c"); map.put(1, "a"); map.put(2, "b");
// 中序有序：1→a, 2→b, 3→c
map.firstKey();           // O(logn)，最小键
map.floorKey(2);          // O(logn)，≤2 的最大键
map.subMap(1, true, 3, false); // O(logn+k)，范围查询

⚠️ 工程坑：

• TreeMap 不是线程安全的，并发场景用 ConcurrentSkipListMap（跳表实现，并发友好）
• Comparator 必须与 equals 一致：若 compare(a,b)==0 但 a.equals(b)==false，会导致 TreeSet 中"存不进去"的问题

哈希表

理想哈希函数的两个目标

1. 均匀分布：n 个键均匀落在 m 个槽，每槽约 n/m 个
2. 快速计算：O(1) 时间计算 h(k)

除法散列：h(k) = k mod m，m 取素数且远离 2 的幂次。

为什么 m 不能是 2 的幂次？若 m = 2^p，h(k) 只取决于 k 的低 p 位，高位信息浪费：

m = 8（2³），h(k) = k mod 8
k=1001000（二进制）→ 低 3 位 000 → 槽 0
k=1010000 → 低 3 位 000 → 也是槽 0
高位不同的键全部碰撞！

Java HashMap 的扰动函数正是为此：

// 让高 16 位参与低 16 位的计算，充分利用全部位信息
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 然后 index = (capacity - 1) & hash
// capacity 是 2 的幂次，& 等价于 mod，但更快

链地址法的性能推导

简单均匀哈希假设（SUHA）：每个键等概率落入任意一个槽。

设 n 个键，m 个槽，装载因子 α = n/m：

失败查找（键不存在）：
  需要遍历对应链表到末尾
  期望链表长度 = α
  期望查找步骤 = Θ(1 + α)

成功查找（键存在）：
  期望在链表第 i 个位置找到
  期望步骤 = 1 + α/2 - α/(2n) ≈ Θ(1 + α)

结论：若 α = O(1)（元素数与槽数同阶），所有操作期望 O(1)。

α = 0.75 的理论依据

Java HashMap 默认装载因子是 0.75，这是时间与空间的经验最优权衡：

α 越小（如 0.5）：
  ✅ 冲突少，查找快
  ❌ 空间浪费（一半槽为空）

α 越大（如 1.0）：
  ✅ 空间利用高
  ❌ 冲突多，链表变长，查找退化

α = 0.75 的数学依据（泊松分布）：
  若哈希完全均匀，槽中有 k 个键的概率：P(k) = e^(-α) · α^k / k!
  当 α = 0.75 时：
    P(0) ≈ 0.472  （约 47% 的槽为空）
    P(1) ≈ 0.354  （约 35% 的槽有 1 个键）
    P(≥8) ≈ 0.000006  （几乎没有链表超过 8）

这就是 Java HashMap 选择"链表长度 > 8 时转红黑树"的依据——正常情况下链表极少超过 8，转树只是极端情况的保底。

开放寻址：一次聚集问题

线性探测：h(k,i) = (h(k) + i) mod m

一次聚集现象：

槽 4、5、6 已满，插入新键 k，h(k)=4
→ 探测 4（满）→ 5（满）→ 6（满）→ 7（空，插入）
下次插入 h(k')=5：
→ 探测 5（满）→ 6（满）→ 7（满）→ 8...
连续满槽越来越长，形成"聚集块"，查找退化为 O(聚集块长度)

双重哈希消除聚集：h(k,i) = (h₁(k) + i·h₂(k)) mod m

两个独立哈希函数，探测步长因键而异，无法形成固定聚集块。

并查集

路径压缩：为什么有效

不加优化：树可能退化为链表（按序 union 1→2→3→...），find(n) 需要 O(n)。

路径压缩：find 时把路径上所有节点直接连到根：

压缩前：1 → 2 → 3 → 4 → 5（根）
find(1) 经过 2,3,4 才到 5

压缩后：
  1 → 5（直连根）
  2 → 5
  3 → 5
  4 → 5
下次 find(1) 只需 1 步！

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);  // 递归时顺手把所有祖先都指向根
    return parent[x];
}

按秩合并：为什么不能单独依赖路径压缩

只有路径压缩，没有按秩合并：

union(1,2): 1→2（根）
union(3,2): 3→2
union(4,2): 4→2
...
union(n,2): n→2

树是星形，find 每次 O(1)
但如果 union 操作全部发生在 find 之前，树可能是链表：
union(1,2)→union(2,3)→union(3,4)→...
1→2→3→...→n，find(1) 仍然 O(n)，压缩前无法利用

按秩合并（小树挂到大树下）：始终保证树高 ≤ logn，哪怕没有路径压缩：

void union(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    // rank 是树高的上界
    if (rank[rx] < rank[ry]) { int t = rx; rx = ry; ry = t; }
    parent[ry] = rx;                  // 小树挂到大树
    if (rank[rx] == rank[ry]) rank[rx]++;  // 等高时新树高加 1
}

两者结合的效果：

α(n) 是什么：直觉理解

α(n) 是反 Ackermann 函数，增长极其缓慢：

Ackermann 函数 A(m,n) 增长极快（比任何原始递归函数都快）：
  A(1,1) = 2
  A(2,2) = 7
  A(3,3) = 61
  A(4,4) = 2^65536（比宇宙中原子数还大得多）

反 Ackermann 函数 α(n) = 最小的 m 使得 A(m,m) ≥ n
  α(n) ≤ 4   对所有 n ≤ A(4,4) ≈ 2^65536（远超宇宙原子数）

直觉：在宇宙时间尺度上的任何实际计算中，α(n) ≤ 4。所以 O(α(n)) 在工程中就等于 O(1)，但数学上并非常数，不能写成 O(1)。

实战例题：Kruskal 最小生成树中的并查集

图：5 个节点，边权如下：
  (0,1,10), (0,2,6), (0,3,5), (1,3,15), (2,3,4)

按边权排序：(2,3,4), (0,3,5), (0,2,6), (0,1,10), (1,3,15)

并查集初始：parent = [0,1,2,3,4]

加入 (2,3,4)：find(2)=2, find(3)=3，不同根，union → parent=[0,1,2,2,4]
加入 (0,3,5)：find(0)=0, find(3)=find(2)=2，不同根，union → parent=[2,1,2,2,4]
加入 (0,2,6)：find(0)=find(2)=2, find(2)=2，相同根，跳过（会成环）
加入 (0,1,10)：find(0)=2, find(1)=1，不同根，union → parent=[2,2,2,2,4]

MST 边：(2,3), (0,3), (0,1)，总权重 = 4+5+10 = 19

选型速查

flowchart TD
    Q["需要什么操作？"] --> Q1{"需要有序性？"}
    Q1 -->|是| Q2{"频繁写还是读？"}
    Q2 -->|写多读少| A["红黑树<br/>TreeMap/TreeSet<br/>插删查 O(logn)"]
    Q2 -->|读多写少| B["AVL 树<br/>（Java 无内置，<br/>或用 TreeMap 也可）"]
    Q1 -->|否| Q3{"需要 O(1) 查找？"}
    Q3 -->|是| C["哈希表<br/>HashMap/HashSet<br/>均摊 O(1)"]
    Q3 -->|否| Q4{"需要最值？"}
    Q4 -->|是| D["堆<br/>PriorityQueue<br/>取最值 O(1)"]
    Q4 -->|否| Q5{"需要连通性/合并？"}
    Q5 -->|是| E["并查集<br/>O(α(n)) ≈ O(1)"]
    Q5 -->|否| F["数组/链表<br/>按访问模式选"]

    style A fill:#d5e8d4,stroke:#82b366
    style C fill:#d5e8d4,stroke:#82b366
    style D fill:#d5e8d4,stroke:#82b366
    style E fill:#d5e8d4,stroke:#82b366

参考资料

• 《算法导论》（CLRS）第 3 版 — 第 6、10~13、21 章
• 《Java 源码分析》HashMap 扩容、TreeMap 红黑树实现
• 算法复杂度分析（堆化 O(n) 的级数推导、并查集 α(n) 的 Ackermann 函数背景）
• 分治与贪心（堆排序完整流程、Kruskal 中并查集的完整应用）