第一部分：线性结构#

数据元素之间是”一对一”的关系，就像排队。

为什么需要线性结构？

假设要存储一个班级 100 个学生的成绩：

❌ 方案 1：定义 100 个变量 score1, score2, ..., score100 → 不现实
✅ 方案 2：使用数组 int scores[100] → 一次性申请连续空间

线性结构解决的核心问题：批量存储、顺序访问

1.1 顺序表/向量/一维张量/数组#

存储原理#

1
内存地址：  100   104   108   112   116
2
数组元素：  [10]  [20]  [30]  [40]  [50]
3
下标：       0     1     2     3     4

连续的内存空间
通过下标直接计算地址：地址 = 起始地址 + 下标 × 元素大小

基本操作#

访问元素：

1
int x = arr[i];  // O(1)

直接计算地址，一步到位。 插入元素：

1
// 在位置i插入元素x，需要把i及之后元素后移
2
for (int j = n-1; j >= i; j--) {
3
    arr[j+1] = arr[j];
4
}
5
arr[i] = x;
6
n++;
7
// 时间：O(n)

删除元素：

1
// 删除位置i的元素，需要把i之后元素前移
2
for (int j = i; j < n-1; j++) {
3
    arr[j] = arr[j+1];
4
}
5
n--;
6
// 时间：O(n)

时间复杂度#

操作	时间复杂度
访问	O(1)
查找	O(n)
插入	O(n)
删除	O(n)

优缺点#

✅ 支持随机访问
✅ 内存连续，缓存友好
❌ 大小固定
❌ 插入删除效率低

1.2 动态数组#

核心思想#

当数组满了，创建一个更大的数组（通常 2 倍），把数据复制过去。

1
初始容量4：
2
[10][20][__][__]  size=2, capacity=4
3

4
插入30, 40后满了：
5
[10][20][30][40]  size=4, capacity=4
6

7
插入50，扩容：
8
[10][20][30][40][50][__][__][__]  size=5, capacity=8

手动实现#

为了理解扩容原理，下面给出完整的类实现。实际使用时直接用 vector<int> v; 即可。

1
class DynamicArray {
2
private:
3
    int* data;
4
    int size;
5
    int capacity;
6

7
    void resize(int newCapacity) {
8
        int* newData = new int[newCapacity];
9
        for (int i = 0; i < size; i++) {
10
            newData[i] = data[i];
11
        }
12
        delete[] data;
13
        data = newData;
14
        capacity = newCapacity;
15
    }
16

17
public:
18
    DynamicArray(int initialCapacity = 10) {
19
        data = new int[initialCapacity];
20
        size = 0;
21
        capacity = initialCapacity;
22
    }
23

24
    ~DynamicArray() {
25
        delete[] data;
26
    }
27

28
    void push_back(int value) {
29
        if (size == capacity) {
30
            resize(capacity * 2);  // 容量翻倍
31
        }
32
        data[size++] = value;
33
    }
34

35
    void pop_back() {
36
        if (size > 0) size--;
37
    }
38

39
    int& operator[](int index) {
40
        return data[index];
41
    }
42

43
    int getSize() const { return size; }
44
};

扩容策略分析#

为什么容量翻倍？

假设初始容量 1，插入 n 个元素：

扩容序列：1 → 2 → 4 → 8 → … → n
扩容次数：log₂(n) 次
复制元素总数：1 + 2 + 4 + … + n/2 = n-1

均摊分析：

1
总代价 = n次普通插入 + (n-1)次复制 = 2n-1
2
平均每次插入代价 = (2n-1)/n ≈ 2 = O(1)

虽然单次扩容是 O(n)，但均摊下来每次插入仍是 O(1)。

缩容策略#

当使用率很低时缩容：

1
if (size > 0 && size == capacity / 4) {
2
    resize(capacity / 2);
3
}

为什么是 1/4 而不是 1/2？ 避免”抖动”：

1
容量4，size在2附近波动：
2
- 删到size=1，缩容到2
3
- 加到size=2，扩容到4
4
- 删到size=1，缩容到2  ← 反复扩缩！
5

6
用1/4阈值：
7
size在1~2之间变化时，容量保持4不变

STL 实现：vector#

1
vector<int> v;
2

3
// 基本操作
4
v.push_back(10);           // 尾部添加
5
v.pop_back();              // 尾部删除
6
v[0] = 5;                  // 访问
7
v.at(1);                   // 带边界检查的访问
8

9
// 大小相关
10
v.size();                  // 元素个数
11
v.capacity();              // 容量
12
v.empty();                 // 是否为空
13
v.clear();                 // 清空
14

15
// 迭代器操作
16
v.insert(v.begin()+2, 20); // 在位置2插入
17
v.erase(v.begin()+1);      // 删除位置1
18
v.front();                 // 第一个元素
19
v.back();                  // 最后一个元素
20

21
// 遍历
22
for (int i = 0; i < v.size(); i++) {
23
    cout << v[i] << " ";
24
}
25

26
for (int x : v) {
27
    cout << x << " ";
28
}

1.3 链表#

存储原理#

数据分散存储，通过指针连接。

1
class ListNode {
2
public:
3
    int val;
4
    ListNode* next;
5

6
    ListNode(int x) : val(x), next(nullptr) {}
7
};

内存示意：

1
head → [10|next] → [20|next] → [30|nullptr]

节点在内存中是分散的，不连续。

基本操作#

遍历：

1
ListNode* p = head;
2
while (p != nullptr) {
3
    cout << p->val << " ";
4
    p = p->next;
5
}
6
// 时间：O(n)

插入（在 p 后）：

1
ListNode* newNode = new ListNode(x);
2
newNode->next = p->next;
3
p->next = newNode;
4
// 时间：O(1)，前提是已知位置p

示意：

1
插入前：[10] → [30] → [40]
2
              ↑ p
3
插入后：[10] → [20] → [30] → [40]
4
              ↑新节点

删除（删除 p 的下一个）：

1
if (p->next != nullptr) {
2
    ListNode* temp = p->next;
3
    p->next = temp->next;
4
    delete temp;
5
}
6
// 时间：O(1)

双向链表#

1
class ListNode {
2
public:
3
    int val;
4
    ListNode* prev;
5
    ListNode* next;
6

7
    ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
8
};

示意：

1
nullptr ← [10] ⇄ [20] ⇄ [30] → nullptr

优势： 可以双向遍历，删除节点不需要前驱。

循环链表#

尾节点指向头节点，形成环。

1
head → [10] → [20] → [30] → [40] ┐
2
       ↑                          │
3
       └──────────────────────────┘

用途：循环调度、约瑟夫问题

STL：list#

1
list<int> lst;
2

3
// 头尾操作
4
lst.push_front(10);        // 头部插入
5
lst.push_back(20);         // 尾部插入
6
lst.pop_front();           // 头部删除
7
lst.pop_back();            // 尾部删除
8

9
// 访问
10
lst.front();               // 第一个元素
11
lst.back();                // 最后一个元素
12

13
// 大小
14
lst.size();
15
lst.empty();
16
lst.clear();
17

18
// 迭代器操作
19
auto it = lst.begin();
20
advance(it, 2);            // 移动迭代器到位置2
21
lst.insert(it, 15);        // 在it位置插入
22
lst.erase(it);             // 删除it位置
23

24
// 遍历
25
for (int x : lst) {
26
    cout << x << " ";
27
}

时间复杂度#

操作	数组	链表
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	O(1)均摊	O(1)
中间插入	O(n)	O(1)*
空间	连续	分散+指针

*已知位置

1.4 受限的访问模式（栈、队列）#

栈（Stack）#

后进先出（LIFO：Last In First Out）

就像一摞盘子：

只能从顶部放入（push）
只能从顶部取出（pop）

1
    ← push/pop
2
    ┌────┐
3
    │ 30 │ ← top（栈顶）
4
    ├────┤
5
    │ 20 │
6
    ├────┤
7
    │ 10 │
8
    └────┘

手动实现#

1
class Stack {
2
private:
3
    vector<int> data;
4

5
public:
6
    void push(int x) {
7
        data.push_back(x);
8
    }
9

10
    void pop() {
11
        if (!data.empty()) {
12
            data.pop_back();
13
        }
14
    }
15

16
  int top() {
17
      if (!data.empty()) {  // 边界检查
18
          return data.back();
19
      }
20
      throw runtime_error("Stack is empty");
21
  }
22

23
    bool isEmpty() {
24
        return data.empty();
25
    }
26

27
    int size() {
28
        return data.size();
29
    }
30
};

时间复杂度#

操作	时间复杂度
push(x)	O(1)*
pop()	O(1)
top()	O(1)
isEmpty()	O(1)
size()	O(1)

说明：

push(x): 平均 O(1)，最坏情况 O(n)。vector 的 push_back() 在容量足够时是 O(1)，但当需要扩容时需要重新分配内存并复制所有元素,此时为 O(n)。不过由于扩容采用倍增策略,摊销时间复杂度为 O(1)。
pop(): O(1)。vector 的 pop_back() 只需移除末尾元素,不涉及元素移动。
top(): O(1)。直接访问 vector 末尾元素。
isEmpty(): O(1)。只需检查 vector 的 empty() 状态。
size(): O(1)。vector 内部维护了大小信息。

STL：stack#

1
stack<int> s;
2

3
s.push(10);      // 入栈
4
s.pop();         // 出栈
5
s.top();         // 栈顶元素
6
s.empty();       // 是否为空
7
s.size();        // 大小

队列（Queue）#

先进先出（FIFO：First In First Out）

就像排队：

从尾部进入（enqueue）
从头部离开（dequeue）

1
dequeue ←─────────────← enqueue
2
         ┌───┬───┬───┐
3
         │10 │20 │30 │
4
         └───┴───┴───┘
5
        front      rear

循环队列（数组实现）#

为什么需要循环？

相比普通队列，避免了”假溢出”问题
所有操作都是真正的 O(1) 时间复杂度
空间利用率高，固定使用 O(k) 空间

1
普通队列问题：
2
[_][_][20][30][40]  ← rear
3
        ↑ front
4
前面空着但无法使用
5

6
循环队列：
7
    rear ↓
8
[40][_][_][_][20]
9
              ↑ front
10
看成环形，rear绕回前面

1
class CircularQueue {
2
private:
3
    vector<int> data;
4
    int front, rear, size, capacity;
5

6
public:
7
    CircularQueue(int k) : capacity(k), front(0), rear(0), size(0) {
8
        data.resize(k);
9
    }
10

11
    bool enqueue(int value) {
12
        if (size == capacity) return false;
13
        data[rear] = value;
14
        rear = (rear + 1) % capacity;
15
        size++;
16
        return true;
17
    }
18

19
    bool dequeue() {
20
        if (size == 0) return false;
21
        front = (front + 1) % capacity;
22
        size--;
23
        return true;
24
    }
25

26
    int getFront() {
27
        return size == 0 ? -1 : data[front];
28
    }
29

30
    bool isEmpty() {
31
        return size == 0;
32
    }
33

34
    bool isFull() {
35
        return size == capacity;
36
    }
37
};

时间复杂度#

操作	时间复杂度
CircularQueue(k)	O(k)
enqueue(value)	O(1)
dequeue()	O(1)
getFront()	O(1)
isEmpty()	O(1)
isFull()	O(1)

说明：

CircularQueue(k): O(k)。构造函数中 data.resize(k) 需要分配 k 个元素的空间。
enqueue(value): O(1)。直接通过索引访问并赋值，取模运算也是常数时间。
dequeue(): O(1)。只需移动 front 指针，不涉及元素移动。
getFront(): O(1)。直接通过索引访问队首元素。
isEmpty(): O(1)。只需检查 size 是否为 0。
isFull(): O(1)。只需比较 size 和 capacity。

STL：queue#

两端都可以插入和删除。

1
← push/pop          push/pop →
2
   ┌───┬───┬───┬───┐
3
   │10 │20 │30 │40 │
4
   └───┴───┴───┴───┘
5
  front          rear

1
queue<int> q;
2

3
q.push(10);      // 入队
4
q.pop();         // 出队
5
q.front();       // 队首
6
q.back();        // 队尾
7
q.empty();       // 是否为空
8
q.size();        // 大小

STL：deque（双端队列）#

1
deque<int> dq;
2

3
dq.push_front(10);     // 头部插入
4
dq.push_back(20);      // 尾部插入
5
dq.pop_front();        // 头部删除
6
dq.pop_back();         // 尾部删除
7
dq[i];                 // 随机访问！
8
dq.front();
9
dq.back();

第二部分：树形结构#

数据元素之间是”一对多”的层次关系。

为什么线性结构不够用？

问题场景： 在 100,000 条有序数据中查找某个值

数组顺序查找：O(n) = 100,000 次比较
数组二分查找：O(log n) ≈ 17 次比较 ✓

二分查找很快，但有个前提：数据必须有序

新问题： 如果频繁插入删除呢？

数组插入/删除：O(n) - 需要移动大量元素
链表插入/删除：O(1) - 但又不能二分查找了

矛盾：

想要快速查找 → 需要有序 + 随机访问
想要快速插入删除 → 需要链式结构

解决方案：树形结构

通过”层次关系”，既能快速查找 O(log n)
又能快速插入删除 O(log n)

2.0 树的基本概念#

1
        A          ← 根节点
2
       /│\
3
      B C D        ← A的子节点
4
     /│   │\
5
    E F   G H      ← 叶子节点(没有子节点)

术语#

节点(Node): 树中的基本单元，包含数据和指向子节点的指针
根节点(Root): 树的顶端节点，没有父节点(如 A)
父节点(Parent): 有子节点的节点(如 A 是 B、C、D 的父节点)
子节点(Child): 节点的直接后代(如 B、C、D 是 A 的子节点)
叶子节点(Leaf): 没有子节点的节点(如 E、F、G、H)
兄弟节点(Sibling): 拥有相同父节点的节点(如 B、C、D 互为兄弟)
祖先节点(Ancestor): 从根到该节点路径上的所有节点(如 E 的祖先: A、B)
后代节点(Descendant): 节点的子树中的所有节点(如 A 的后代: B、C、D、E、F、G、H)

度量指标#

节点的度(Degree): 节点的子节点个数(如 A 的度为 3，B 的度为 2)
树的度: 树中所有节点度的最大值(该树的度为 3)
深度(Depth): 从根节点到该节点的边数(如 E 的深度为 2)
高度(Height): 从该节点到叶子节点的最长路径的边数(如 A 的高度为 2)
层(Level): 节点的深度 + 1(根节点为第 1 层)

树的性质#

有 n 个节点的树有 n-1 条边
任意两个节点之间有且仅有一条路径
树是无环连通图

2.1 树的存储方式#

链式存储(常用)#

二叉树节点定义:

1
class TreeNode {
2
public:
3
    int val;
4
    TreeNode* left;   // 左子节点
5
    TreeNode* right;  // 右子节点
6
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
7
};

多叉树节点定义:

1
class TreeNode {
2
public:
3
    int val;
4
    vector<TreeNode*> children;  // 子节点列表
5
    TreeNode(int x) : val(x) {}
6
};
7

8
// 或者使用"左孩子右兄弟"表示法
9
class TreeNode {
10
public:
11
    int val;
12
    TreeNode* firstChild;   // 第一个子节点
13
    TreeNode* nextSibling;  // 下一个兄弟节点
14
    TreeNode(int x) : val(x), firstChild(nullptr), nextSibling(nullptr) {}
15
};

特点:

空间复杂度: O(n)
插入/删除灵活
适合动态变化的树

数组存储(适合完全二叉树)#

1
vector<int> tree;  // 从索引1开始存储
2

3
// 对于索引 i 的节点:
4
// 左子节点: 2*i
5
// 右子节点: 2*i + 1
6
// 父节点: i/2

示例:

1
        1
2
       / \
3
      2   3
4
     / \  /
5
    4  5 6
6

7
数组: [0, 1, 2, 3, 4, 5, 6]
8
索引:  0  1  2  3  4  5  6

特点:

空间复杂度:
- 完全二叉树: O(n)
- 稀疏树: O(2^h)，浪费空间
查找父子节点: O(1)
适合堆、完全二叉树

父节点数组#

1
vector<int> parent(n);  // parent[i] 存储节点 i 的父节点
2

3
// 示例:
4
//     0
5
//    /|\
6
//   1 2 3
7
//  /|
8
// 4 5
9

10
parent = [-1, 0, 0, 0, 1, 1];
11
//         0  1  2  3  4  5

特点:

空间复杂度: O(n)
向上查找快，向下查找慢
适合并查集、需要频繁查找祖先的场景

邻接表(通用树)#

1
vector<vector<int>> adj(n);  // adj[i] 存储节点 i 的所有子节点
2

3
// 示例(同上):
4
adj[0] = {1, 2, 3};
5
adj[1] = {4, 5};
6
adj[2] = {};
7
adj[3] = {};
8
adj[4] = {};
9
adj[5] = {};

特点:

空间复杂度: O(n)
灵活，适合任意结构的树
适合图转树、多叉树

三元组表示(较少用)#

1
class Edge {
2
public:
3
    int parent;
4
    int child;
5
    int weight;  // 可选
6
};
7
vector<Edge> edges;

存储方式对比#

存储方式	空间复杂度	适用场景	优点	缺点
链式存储	O(n)	通用	灵活、直观	指针开销
数组存储	O(n)~O(2^h)	完全二叉树、堆	访问快、无指针	稀疏树浪费空间
父节点数组	O(n)	并查集、祖先查询	简单、省空间	查找子节点慢
邻接表	O(n)	多叉树、图转树	灵活、省空间	需要额外结构

选择建议:

二叉树: 优先链式存储
堆/完全二叉树: 数组存储
多叉树: 链式存储(children 数组)或邻接表
需要快速查找祖先: 父节点数组
树的动态变化: 链式存储

2.2 二叉树#

每个节点最多有 2 个子节点（左子、右子）。

1
class TreeNode {
2
public:
3
    int val;
4
    TreeNode* left;
5
    TreeNode* right;
6

7
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8
};

二叉树的类型#

满二叉树#

每一层都是满的。

节点数：2^h - 1（h 是高度）

完全二叉树#

除了最后一层，其他层都是满的，最后一层从左到右连续。

完全二叉树可以用数组存储：

1
数组：[1, 2, 3, 4, 5, 6]
2

3
节点i的左子：2i + 1
4
节点i的右子：2i + 2
5
节点i的父节点：(i-1) / 2

树的遍历#

深度优先遍历 (DFS)#

遍历方式	访问顺序	示例结果
前序(Pre-order)	根 → 左 → 右	A B D E C F
中序(In-order)	左 → 根 → 右	D B E A C F
后序(Post-order)	左 → 右 → 根	D E B F C A

前序遍历(Pre-order Traversal)：根 → 左 → 右

1
void preOrder(TreeNode* root) {
2
    if (root == nullptr) return;
3
    cout << root->val << " ";
4
    preOrder(root->left);
5
    preOrder(root->right);
6
}

中序遍历：左 → 根 → 右

1
void inOrder(TreeNode* root) {
2
    if (root == nullptr) return;
3
    inOrder(root->left);
4
    cout << root->val << " ";
5
    inOrder(root->right);
6
}

后序遍历：左 → 右 → 根

1
void postOrder(TreeNode* root) {
2
    if (root == nullptr) return;
3
    postOrder(root->left);
4
    postOrder(root->right);
5
    cout << root->val << " ";
6
}

广度优先遍历 (BFS)#

遍历方式	访问顺序	示例结果
层序(Level-order)	逐层从左到右	A B C D E F

1
        A          ← 第1层
2
       / \
3
      B   C        ← 第2层
4
     / \   \
5
    D   E   F      ← 第3层

层序：用队列

1
void levelOrder(TreeNode* root) {
2
    if (root == nullptr) return;
3
    queue<TreeNode*> q;
4
    q.push(root);
5

6
    while (!q.empty()) {
7
        TreeNode* node = q.front();
8
        q.pop();
9
        cout << node->val << " ";
10

11
        if (node->left) q.push(node->left);
12
        if (node->right) q.push(node->right);
13
    }
14
}

2.3 二叉搜索树 (Binary Search Tree, BST)#

二叉搜索树是一种特殊的二叉树，满足以下性质：

左子树的所有节点值 < 根节点值
右子树的所有节点值 > 根节点值
左右子树也都是二叉搜索树

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

关键性质#

BST 的中序遍历结果是有序递增序列！

示例:

1
        8
2
       / \
3
      3   10
4
     / \    \
5
    1   6   14
6

7
中序遍历: 1, 3, 6, 8, 10, 14  ← 有序!

查找#

思路: 利用 BST 性质，比较目标值与当前节点

目标值 < 当前值 → 去左子树
目标值 > 当前值 → 去右子树
相等 → 找到

1
TreeNode* search(TreeNode* root, int target) {
2
    if (root == nullptr || root->val == target) {
3
        return root;
4
    }
5

6
    if (target < root->val) {
7
        return search(root->left, target);   // 去左子树
8
    } else {
9
        return search(root->right, target);  // 去右子树
10
    }
11
}
12

13
// 迭代版本
14
TreeNode* searchIterative(TreeNode* root, int target) {
15
    while (root != nullptr && root->val != target) {
16
        root = (target < root->val) ? root->left : root->right;
17
    }
18
    return root;
19
}

插入#

1
TreeNode* insert(TreeNode* root, int val) {
2
    if (root == nullptr) {
3
        return new TreeNode(val);  // 找到插入位置
4
    }
5

6
    if (val < root->val) {
7
        root->left = insert(root->left, val);   // 插入左子树
8
    } else if (val > root->val) {
9
        root->right = insert(root->right, val); // 插入右子树
10
    }
11
    // val == root->val 时不插入(避免重复)
12

13
    return root;
14
}

示例:

1
插入 5:
2
        8              8
3
       / \            / \
4
      3   10   →     3   10
5
     / \            / \
6
    1   6          1   6
7
                      /
8
                     5

删除#

最复杂的操作，需要考虑三种情况：

情况 1: 删除叶子节点 → 直接删除

1
删除 1:
2
        8              8
3
       / \            / \
4
      3   10   →     3   10
5
     / \              \
6
    1   6              6

情况 2: 删除只有一个子节点的节点 → 用子节点替代

1
删除 10:
2
        8              8
3
       / \            / \
4
      3   10   →     3   14
5
         /  \             /
6
       12   14          12

情况 3: 删除有两个子节点的节点 → 找后继节点(右子树最小值)或前驱节点(左子树最大值)替代

1
删除 3:
2
        8              8
3
       / \            / \
4
      3   10   →     4   10      (用后继节点4替代3)
5
     / \            / \
6
    1   6          1   6
7
       / \              \
8
      4   7              7

1
TreeNode* deleteNode(TreeNode* root, int key) {
2
    if (root == nullptr) return nullptr;
3

4
    if (key < root->val) {
5
        root->left = deleteNode(root->left, key);
6
    } else if (key > root->val) {
7
        root->right = deleteNode(root->right, key);
8
    } else {
9
        // 找到要删除的节点
10

11
        // 情况1 & 2: 0个或1个子节点
12
        if (root->left == nullptr) {
13
            TreeNode* temp = root->right;
14
            delete root;
15
            return temp;
16
        } else if (root->right == nullptr) {
17
            TreeNode* temp = root->left;
18
            delete root;
19
            return temp;
20
        }
21

22
        // 情况3: 2个子节点 - 找右子树最小值(后继)
23
        TreeNode* successor = findMin(root->right);
24
        root->val = successor->val;  // 用后继值替代
25
        root->right = deleteNode(root->right, successor->val); // 删除后继
26
    }
27

28
    return root;
29
}
30

31
// 最小值: 一直向左
32
TreeNode* findMin(TreeNode* node) {
33
    while (node->left != nullptr) {
34
        node = node->left;
35
    }
36
    return node;
37
}

复杂度#

操作	平均	最坏
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

空间复杂度: O(n)

2.4 平衡二叉树 (Balanced Binary Tree)#

问题引入#

BST 为什么不够用？

回顾 BST 的最坏情况：

1
插入1,2,3,4,5:
2
1
3
 \
4
  2
5
   \
6
    3
7
     \
8
      4
9
       \
10
        5  ← 退化成链表！查找O(n)

根本原因： BST 不保证平衡性

解决思路： 在插入/删除时，通过旋转保持树的平衡

进化路径：

1
BST (无平衡保证)
2
  ↓ 严格平衡
3
AVL树 (任意节点左右子树高度差≤1, 查找最快)
4
  ↓ 放宽限制
5
红黑树 (弱平衡, 插入删除更快, C++ STL采用)
6
  ↓ 适应磁盘IO
7
B树/B+树 (多路平衡树, 数据库索引)

核心概念#

平衡二叉树：任意节点的左右子树高度差不超过 1 的二叉树

平衡因子 (Balance Factor) = 左子树高度 - 右子树高度

平衡二叉树的平衡因子只能是: -1, 0, 1

1
        平衡 ✓                    不平衡 ✗
2

3
          5                          5
4
         / \                        /
5
        3   8                      3
6
       / \   \                    /
7
      1   4   9                  2
8
                                /
9
平衡因子都是 -1,0,1              1        ← 节点5的平衡因子为2

1. AVL 树#

最严格的平衡树，由 Adelson-Velsky 和 Landis 发明

特点:

任意节点平衡因子 ∈ {-1, 0, 1}
插入/删除后通过旋转恢复平衡
查找效率最高，但维护成本较高

1
class AVLNode {
2
public:
3
    int val;
4
    int height;
5
    AVLNode* left;
6
    AVLNode* right;
7

8
    AVLNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {}
9
};

旋转操作#

AVL 树通过旋转保持平衡，有 4 种情况：

LL (左左): 在左子树的左边插入 → 右旋
RR (右右): 在右子树的右边插入 → 左旋
LR (左右): 在左子树的右边插入 → 先左旋后右旋
RL (右左): 在右子树的左边插入 → 先右旋后左旋

1. 右旋 (LL 情况)#

1
      y                    x
2
     / \    右旋          / \
3
    x   C   --->         A   y
4
   / \                      / \
5
  A   B                    B   C

1
TreeNode* rightRotate(TreeNode* y) {
2
    TreeNode* x = y->left;
3
    TreeNode* B = x->right;
4

5
    // 执行旋转
6
    x->right = y;
7
    y->left = B;
8

9
    // 更新高度
10
    y->height = max(height(y->left), height(y->right)) + 1;
11
    x->height = max(height(x->left), height(x->right)) + 1;
12

13
    return x;  // 新的根节点
14
}

2. 左旋 (RR 情况)#

1
    x                      y
2
   / \      左旋          / \
3
  A   y     --->         x   C
4
     / \                / \
5
    B   C              A   B

1
TreeNode* leftRotate(TreeNode* x) {
2
    TreeNode* y = x->right;
3
    TreeNode* B = y->left;
4

5
    // 执行旋转
6
    y->left = x;
7
    x->right = B;
8

9
    // 更新高度
10
    x->height = max(height(x->left), height(x->right)) + 1;
11
    y->height = max(height(y->left), height(y->right)) + 1;
12

13
    return y;  // 新的根节点
14
}

3. 先左旋后右旋 (LR 情况)#

1
      z              z                x
2
     / \            / \              / \
3
    y   D   -->    x   D    -->     y   z
4
   / \            / \              / \ / \
5
  A   x          y   C            A  B C  D
6
     / \        / \
7
    B   C      A   B
8

9
    步骤1:          步骤2:
10
    左旋y          右旋z

4. 先右旋后左旋 (RL 情况)#

1
    z                z              x
2
   / \              / \            / \
3
  A   y     -->    A   x    -->   z   y
4
     / \              / \        / \ / \
5
    x   D            B   y      A  B C  D
6
   / \                  / \
7
  B   C                C   D
8

9
  步骤1:               步骤2:
10
  右旋y               左旋z

插入操作#

1
AVLNode* insert(AVLNode* node, int key) {
2
    // 1. 正常BST插入
3
    if (node == nullptr)
4
        return new AVLNode(key);
5

6
    if (key < node->val)
7
        node->left = insert(node->left, key);
8
    else if (key > node->val)
9
        node->right = insert(node->right, key);
10
    else
11
        return node;
12

13
    // 2. 更新高度
14
    node->height = 1 + max(height(node->left), height(node->right));
15

16
    // 3. 计算平衡因子
17
    int balance = height(node->left) - height(node->right);
18

19
    // 4. 如果失衡，进行旋转
20

21
    // LL
22
    if (balance > 1 && key < node->left->val)
23
        return rightRotate(node);
24

25
    // RR
26
    if (balance < -1 && key > node->right->val)
27
        return leftRotate(node);
28

29
    // LR
30
    if (balance > 1 && key > node->left->val) {
31
        node->left = leftRotate(node->left);
32
        return rightRotate(node);
33
    }
34

35
    // RL
36
    if (balance < -1 && key < node->right->val) {
37
        node->right = rightRotate(node->right);
38
        return leftRotate(node);
39
    }
40

41
    return node;
42
}

时间复杂度#

操作	时间
查找	O(log n) - 保证
插入	O(log n)
删除	O(log n)

优点： 严格平衡，查找效率高 缺点： 插入删除时旋转次数多

2. 红黑树 (Red-Black Tree)#

应用最广的平衡树 (C++ STL map/set, Java TreeMap)

性质:

每个节点是红色或黑色
根节点是黑色
叶子节点是黑色
红色节点的子节点必须是黑色(不能有连续红节点)
从任一节点到其叶子的所有路径包含相同数目的黑色节点

1
         13(B)
2
        /     \
3
      8(R)    17(B)
4
     /   \       \
5
   1(B)  11(B)  25(R)
6
              /    \
7
            22(B)  27(B)

特点:

近似平衡(最长路径 ≤ 2× 最短路径)
插入/删除最多 3 次旋转
比 AVL 树插入删除快，查找稍慢

1
enum Color { RED, BLACK };
2

3
class RBNode {
4
public:
5
    int val;
6
    Color color;
7
    RBNode *left, *right, *parent;
8

9
    RBNode(int x) : val(x), color(RED),
10
                    left(nullptr), right(nullptr), parent(nullptr) {}
11
};

插入修复#

插入节点标记为红色，可能违反性质 4（连续红色）。

修复策略（3 种情况）：

情况 1：叔叔是红色 → 变色

1
        (B)G
2
       /    \
3
    (R)P    (R)U
4
   /
5
(R)N
6

7
解决：P和U变黑，G变红
8
        (R)G
9
       /    \
10
    (B)P    (B)U
11
   /
12
(R)N

情况 2：叔叔是黑色，N 在 P 右侧（LR 型） → 左旋

1
    (B)G
2
   /    \
3
(R)P    (B)U
4
   \
5
   (R)N
6

7
解决：左旋P，转化为情况3

情况 3：叔叔是黑色，N 在 P 左侧（LL 型） → 右旋+变色

1
    (B)G
2
   /    \
3
(R)P    (B)U
4
 /
5
(R)N
6

7
解决：右旋G，P变黑，G变红
8
      (B)P
9
     /    \
10
  (R)N    (R)G
11
              \
12
              (B)U

具体实现较复杂，实际工程中直接用 STL。

时间复杂度#

操作	时间
查找	O(log n)
插入	O(log n)
删除	O(log n)

STL set（有序集合，元素唯一）#

1
set<int> s;
2

3
// 插入
4
s.insert(30);
5
s.insert(10);
6
s.insert(20);
7

8
// 查找
9
if (s.find(20) != s.end()) {
10
    cout << "找到" << endl;
11
}
12

13
s.count(10);  // 返回0或1
14

15
// 删除
16
s.erase(10);
17

18
// 遍历（自动排序）
19
for (int x : s) {
20
    cout << x << " ";  // 10 20 30
21
}
22

23
// 其他操作
24
s.size();
25
s.empty();
26
s.clear();
27
s.begin();  // 最小元素
28
s.rbegin(); // 最大元素

STL map（有序键值对，key 唯一）#

1
map<string, int> m;
2

3
// 插入
4
m["Alice"] = 85;
5
m["Bob"] = 90;
6
m.insert({"Charlie", 78});
7

8
// 访问
9
cout << m["Alice"] << endl;
10

11
// 查找
12
if (m.find("Bob") != m.end()) {
13
    cout << "找到" << endl;
14
}
15

16
m.count("Alice");  // 返回0或1
17

18
// 删除
19
m.erase("Charlie");
20

21
// 遍历（按key排序）
22
for (auto& p : m) {
23
    cout << p.first << ": " << p.second << endl;
24
}
25

26
// 其他操作
27
m.size();
28
m.empty();
29
m.clear();

3. B 树 / B+ 树#

多路平衡查找树，主要用于数据库和文件系统

二叉树的问题：

1
       10
2
      /  \
3
     5    15
4
    / \   / \
5
   3   7 12  20
6

7
查找20需要3次磁盘IO（访问10, 15, 20）
8
树越高，IO越多

B 树的思路：

每个节点存多个 key，减少树高
一个节点正好一页，减少 IO 次数

B 树特点:

每个节点可以有多个子节点(不只是 2 个)
所有叶子节点在同一层
适合磁盘存储(减少 I/O 次数)

B 树#

一棵m 阶 B 树满足：

每个节点最多 m 个子节点
除根外，每个节点至少⌈m/2⌉个子节点
根节点至少 2 个子节点（除非是叶子）
所有叶子在同一层
节点有 k 个 key，就有 k+1 个子节点

1
3阶B树（每个节点最多2个key，3个子节点）：
2

3
        [10, 20]
4
       /    |    \
5
    [5]   [15]   [25, 30]

性质：

key 按升序排列
key[i]的左子树所有 key < key[i]
key[i]的右子树所有 key > key[i]

1
class BTreeNode {
2
public:
3
    vector<int> keys;           // key数组
4
    vector<BTreeNode*> children; // 子节点指针
5
    bool isLeaf;
6
    int n;                      // 当前key个数
7

8
    BTreeNode(bool leaf) : isLeaf(leaf), n(0) {}
9
};

插入操作#

情况 1：节点未满 → 直接插入

1
插入12到节点[10, 20]：
2
[10, 12, 20]

情况 2：节点已满 → 分裂

1
插入25到已满节点[10, 20, 30]（3阶B树，最多2个key）：
2

3
步骤1：临时插入
4
[10, 20, 25, 30]
5

6
步骤2：找中间key（20和25之间，取20），分裂
7
       [20]        ← 提升到父节点
8
      /    \
9
   [10]    [25, 30]

如果父节点也满了，继续向上分裂，直到根。

查找操作#

1
BTreeNode* search(BTreeNode* node, int key) {
2
    int i = 0;
3
    // 找第一个 ≥ key的位置
4
    while (i < node->n && key > node->keys[i])
5
        i++;
6

7
    if (i < node->n && key == node->keys[i])
8
        return node;  // 找到
9

10
    if (node->isLeaf)
11
        return nullptr;  // 未找到
12

13
    return search(node->children[i], key);  // 递归查找子树
14
}

时间复杂度#

m 阶 B 树，n 个 key：

树高：O(log_m n)
查找：O(log_m n)次磁盘 IO
插入/删除：O(log_m n)次磁盘 IO

例如： m=1000 的 B 树，存 1 亿条记录，树高只有 3-4 层！

B+树#

B+树是 B 树的变种，更适合数据库。

与 B 树的区别：

所有数据都存在叶子节点，内部节点只存索引
叶子节点形成链表，便于范围查询

1
B+树：
2
        [10, 20]         ← 内部节点，只有索引
3
       /    |    \
4
    [5]   [15]   [25]    ← 叶子节点，存数据
5
     ↓     ↓      ↓
6
    数据   数据    数据
7
     ↔     ↔      ↔      ← 叶子节点连成链表

B+树的优点：

内部节点不存数据，可以存更多 key，树更矮
叶子节点链表，范围查询快（如：查找 10-30 之间的数据）
所有查询都到达叶子，性能稳定

平衡树对比#

特性	AVL 树	红黑树	B 树/B+树
平衡程度	严格（高度差 ≤1）	近似（最长路径 ≤2× 最短路径）	完全平衡
查找速度	最快	较快	快(磁盘)
插入/删除	较慢(多次旋转)	快(最多 3 次旋转)	适中
适用场景	查找密集	插入删除频繁	数据库索引
实际应用	Windows 内核	C++ STL, Linux 内核	MySQL, 文件系统

2.5 堆（Heap）#

用于维护最值。

堆是一种特殊的完全二叉树，满足堆性质：

最大堆 (Max Heap): 父节点 ≥ 子节点
最小堆 (Min Heap): 父节点 ≤ 子节点

1
最大堆示例:                最小堆示例:
2
        100                      1
3
       /   \                   /   \
4
      19    36                2     3
5
     / \   / \               / \   / \
6
    17  3 25  1             17 19 36 7
7
   / \                     /
8
  2   7                   25
9

10
特点: 根节点最大         特点: 根节点最小

注意： 堆不是 BST！兄弟节点间无大小关系。

数组存储#

完全二叉树用数组存储很高效：

1
数组：[90, 80, 70, 50, 40, 30]
2
下标： 0   1   2   3   4   5
3

4
        90(0)
5
       /      \
6
    80(1)     70(2)
7
    / \       /
8
 50(3) 40(4) 30(5)
9

10
规律：
11
节点i的左子：2i + 1
12
节点i的右子：2i + 2
13
节点i的父节点：(i - 1) / 2

基本操作#

上浮#

用于插入后维护堆性质。

1
插入 50 到最大堆:
2

3
步骤1: 放到末尾           步骤2: 与父节点比较
4
        100                      100
5
       /   \                    /   \
6
      19    36                 19    36
7
     / \   / \                / \   / \
8
    17  3 25  1              17 50 25  1  ← 50 > 3, 交换
9
   / \  /                   / \  /
10
  2   7 50                 2   7 3
11

12
步骤3: 继续上浮            步骤4: 完成
13
        100                      100
14
       /   \                    /   \
15
      50    36                 50    36
16
     / \   / \                / \   / \
17
    17 19 25  1              17 19 25  1
18
   / \  /                   / \  /
19
  2   7 3                  2   7 3

1
void up(vector<int>& heap, int index) {
2
    while (index > 0) {
3
        int parent = (index - 1) / 2;
4

5
        // 最大堆: 如果子节点 > 父节点，交换
6
        if (heap[index] > heap[parent]) {
7
            swap(heap[index], heap[parent]);
8
            index = parent;
9
        } else {
10
            break;
11
        }
12
    }
13
}
14

15
void push(vector<int>& heap, int val) {
16
    heap.push_back(val);
17
    ip(heap, heap.size() - 1);
18
}
19
// 时间：O(log n)

下沉#

用于删除堆顶后维护堆性质。

1
删除堆顶 100:
2

3
步骤1: 用末尾元素替换     步骤2: 与较大子节点比较
4
        3                        50
5
       /   \                    /   \
6
      19    36       →         19    36
7
     / \   / \                / \   / \
8
    17 50 25  1              17  3 25  1
9
   / \                      / \
10
  2   7                    2   7
11

12
步骤3: 继续下沉            步骤4: 完成
13
        50                       50
14
       /   \                    /   \
15
      19    36                 19    36
16
     / \   / \                / \   / \
17
    17  3 25  1              17  7 25  1
18
   / \                      / \
19
  2   7                    2   3

1
void down(vector<int>& heap, int i) {
2
    int n = heap.size();
3
    while (2 * i + 1 < n) {
4
        int left = 2 * i + 1;
5
        int right = 2 * i + 2;
6
        int largest = i;
7

8
        if (heap[left] > heap[largest])
9
            largest = left;
10
        if (right < n && heap[right] > heap[largest])
11
            largest = right;
12

13
        if (largest != i) {
14
            swap(heap[i], heap[largest]);
15
            i = largest;
16
        } else {
17
            break;
18
        }
19
    }
20
}
21

22
int pop(vector<int>& heap) {
23
    int maxVal = heap[0];
24
    heap[0] = heap.back();
25
    heap.pop_back();
26
    if (!heap.empty()) {
27
        down(heap, 0);
28
    }
29
    return maxVal;
30
}
31
// 时间：O(log n)

建堆（Heapify）#

给定无序数组，如何建堆？

逐个插入 - O(n log n)#

1
void buildHeapByInsert(vector<int>& arr) {
2
    MaxHeap heap;
3
    for (int num : arr) {
4
        heap.push(num);  // 每次 O(log n)
5
    }
6
}

自底向上 - O(n) ⭐ 推荐#

从最后一个非叶子节点开始，逐个下沉

1
void heapify(vector<int>& arr) {
2
    // 从最后一个非叶子节点开始，往前sift down
3
    for (int i = arr.size() / 2 - 1; i >= 0; i--) {
4
        siftDown(arr, i);
5
    }
6
}

为什么是 O(n)？

数学分析：

叶子节点（约 n/2 个）不需要调整
倒数第二层（约 n/4 个）最多下沉 1 次
倒数第三层（约 n/8 个）最多下沉 2 次
总操作数: n/4×1 + n/8×2 + n/16×3 + … = O(n)

示例：

1
数组：[3, 5, 1, 10, 2, 7]
2

3
初始树：
4
        3
5
       / \
6
      5   1
7
     /|\  /
8
    10 2 7
9

10
从i=2开始（最后非叶节点）：
11
i=2: 1下沉（与7交换）
12
i=1: 5下沉（与10交换）
13
i=0: 3下沉（与10交换，再与7交换）
14

15
最终最大堆：
16
        10
17
       /  \
18
      5    7
19
     / \   /
20
    3  2  1

时间复杂度#

操作	时间复杂度
插入 (push)	O(log n)
删除堆顶 (pop)	O(log n)
查看堆顶 (top)	O(1)
建堆 (heapify)	O(n)

空间复杂度: O(n)

STL：优先队列 priority_queue#

1
// 最大堆（默认）
2
priority_queue<int> maxHeap;
3

4
maxHeap.push(30);
5
maxHeap.push(10);
6
maxHeap.push(50);
7

8
cout << maxHeap.top() << endl;  // 50
9
maxHeap.pop();
10
cout << maxHeap.top() << endl;  // 30
11

12
maxHeap.size();
13
maxHeap.empty();

最小堆：

1
priority_queue<int, vector<int>, greater<int>> minHeap;
2

3
minHeap.push(30);
4
minHeap.push(10);
5
minHeap.push(50);
6

7
cout << minHeap.top() << endl;  // 10

自定义比较：

1
class Compare {
2
public:
3
    bool operator()(int a, int b) {
4
        return a > b;  // 最小堆
5
    }
6
};
7
priority_queue<int, vector<int>, Compare> customHeap;

2.6 Huffman 树#

哈夫曼树是一种一次性编码结构构造的数据结构，不支持动态插入与删除。

核心思想#

为了解码无歧义，要求：任何字符的编码都不是另一个字符编码的前缀

1
❌ 错误的编码：
2
A → 0
3
B → 01   ← B的编码是A的前缀！
4

5
解码"01"时无法确定是"AB"还是"B"
6

7
✅ 正确的编码（前缀编码）：
8
A → 0
9
B → 10

前缀编码可以用二叉树表示：

左分支：0
右分支：1
叶子节点：字符
从根到叶的路径：编码

带权路径长度（WPL）#

定义：

1
WPL = Σ(叶子节点的权值 × 路径长度)
2

3
权值 = 字符出现频率
4
路径长度 = 根到叶子的边数

示例：

1
字符频率：
2
A: 5
3
B: 2
4
R: 2
5
C: 1
6
D: 1
7

8
上面的树：
9
WPL = 5×1 + 2×2 + 2×3 + 1×4 + 1×4
10
    = 5 + 4 + 6 + 4 + 4
11
    = 23

目标：构造 WPL 最小的二叉树 → 编码总长度最短

构造#

每次选择频率最小的两个节点合并。

输入： n 个字符及其频率

步骤：

将 n 个字符作为 n 棵树（每棵树只有一个节点）
用优先队列（最小堆）存储这些树，按权值排序
重复以下步骤直到只剩一棵树：
- 取出权值最小的两棵树
- 创建新节点作为它们的父节点，权值 = 两子树权值之和
- 将新树放回优先队列

示例：构造 ABRACADABRA 的哈夫曼树

1
初始频率：
2
A:5  B:2  R:2  C:1  D:1
3

4
步骤1：合并C(1)和D(1)
5
    2
6
   / \
7
  C:1 D:1
8

9
剩余：A:5  B:2  R:2  [C+D:2]
10

11
步骤2：合并B(2)和[C+D](2)
12
      4
13
     / \
14
    B:2  2
15
        / \
16
       C:1 D:1
17

18
剩余：A:5  R:2  [B+C+D:4]
19

20
步骤3：合并R(2)和[B+C+D](4)
21
        6
22
       / \
23
      R:2  4
24
          / \
25
         B:2  2
26
             / \
27
            C:1 D:1
28

29
剩余：A:5  [R+B+C+D:6]
30

31
步骤4：合并A(5)和[R+B+C+D](6)
32
           11
33
          /  \
34
        A:5   6
35
             / \
36
            R:2  4
37
                / \
38
               B:2  2
39
                   / \
40
                  C:1 D:1
41

42
最终哈夫曼树构造完成！

读取编码：

1
从根到叶的路径，左=0，右=1
2

3
A: 左 → 0
4
R: 右→左 → 10
5
B: 右→右→左 → 110
6
C: 右→右→右→左 → 1110
7
D: 右→右→右→右 → 1111

WPL 计算：

1
WPL = 5×1 + 2×2 + 2×3 + 1×4 + 1×4
2
    = 5 + 4 + 6 + 4 + 4
3
    = 23

代码实现#

1
class HuffmanNode {
2
public:
3
    char ch;
4
    int freq;
5
    HuffmanNode *left, *right;
6

7
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
8
    HuffmanNode(int f, HuffmanNode* l, HuffmanNode* r)
9
        : ch('\0'), freq(f), left(l), right(r) {}
10
};
11

12
// 比较器：按频率排序（最小堆）
13
class Compare {
14
public:
15
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
16
        return a->freq > b->freq;
17
    }
18
};
19

20
// 构造哈夫曼树
21
HuffmanNode* buildHuffmanTree(vector<pair<char, int>>& charFreq) {
22
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
23

24
    // 步骤1：初始化，每个字符作为一棵树
25
    for (auto& p : charFreq) {
26
        pq.push(new HuffmanNode(p.first, p.second));
27
    }
28

29
    // 步骤2：不断合并最小的两棵树
30
    while (pq.size() > 1) {
31
        HuffmanNode* left = pq.top(); pq.pop();
32
        HuffmanNode* right = pq.top(); pq.pop();
33

34
        // 创建父节点
35
        int sumFreq = left->freq + right->freq;
36
        HuffmanNode* parent = new HuffmanNode(sumFreq, left, right);
37

38
        pq.push(parent);
39
    }
40

41
    return pq.top();  // 返回根节点
42
}
43

44
// 生成编码表
45
void generateCodes(HuffmanNode* root, string code,
46
                   unordered_map<char, string>& codes) {
47
    if (root == nullptr) return;
48

49
    // 叶子节点：存储编码
50
    if (root->left == nullptr && root->right == nullptr) {
51
        codes[root->ch] = code;
52
        return;
53
    }
54

55
    // 递归处理左右子树
56
    generateCodes(root->left, code + "0", codes);
57
    generateCodes(root->right, code + "1", codes);
58
}
59

60
// 编码
61
string encode(string text, unordered_map<char, string>& codes) {
62
    string result = "";
63
    for (char c : text) {
64
        result += codes[c];
65
    }
66
    return result;
67
}
68

69
// 解码
70
string decode(string encoded, HuffmanNode* root) {
71
    string result = "";
72
    HuffmanNode* curr = root;
73

74
    for (char bit : encoded) {
75
        if (bit == '0') {
76
            curr = curr->left;
77
        } else {
78
            curr = curr->right;
79
        }
80

81
        // 到达叶子节点
82
        if (curr->left == nullptr && curr->right == nullptr) {
83
            result += curr->ch;
84
            curr = root;  // 回到根节点
85
        }
86
    }
87

88
    return result;
89
}

时间复杂度#

操作	时间
构造哈夫曼树	O(n log n)
生成编码表	O(n)
编码	O(m)，m 是文本长度
解码	O(k)，k 是编码长度

构造过程：

n 个字符，需要合并 n-1 次
每次合并涉及堆操作：O(log n)
总时间：O(n log n)

最优性证明#

定理： 哈夫曼算法构造的树具有最小的 WPL。

证明思路（贪心选择性质）：

最优树的性质： 频率最小的两个字符一定是兄弟节点，且在最深层
贪心选择： 哈夫曼算法每次选择频率最小的两个节点合并
归纳证明：
- 假设 n-1 个节点时算法最优
- 对于 n 个节点，合并最小的两个后，问题规模变为 n-1
- 由归纳假设，剩余部分最优
- 因此 n 个节点时也最优

2.7 树状数组 (Binary Indexed Tree / Fenwick Tree)#

区间和查询的高效方案

问题场景#

假设有一个数组，需要频繁进行以下操作：

修改某个位置的值
查询某个区间的和

朴素方法：

方法	单点修改	区间查询	问题
直接遍历	O(1)	O(n)	查询太慢
前缀和	O(n)	O(1)	修改需要重算整个前缀和

能否做到修改和查询都快？ → 树状数组：O(log n)

核心思想#

利用二进制特性，每个位置存储一段区间的和：

1
arr = [1, 3, 5, 7, 9, 11, 13, 15]
2
下标   1  2  3  4  5  6   7   8
3

4
BIT:
5
bit[1] = arr[1]                    = 1        (管辖1个元素)
6
bit[2] = arr[1] + arr[2]           = 4        (管辖2个元素)
7
bit[3] = arr[3]                    = 5        (管辖1个元素)
8
bit[4] = arr[1]~arr[4]的和         = 16       (管辖4个元素)
9
bit[5] = arr[5]                    = 9        (管辖1个元素)
10
bit[6] = arr[5] + arr[6]           = 20       (管辖2个元素)
11
bit[7] = arr[7]                    = 13       (管辖1个元素)
12
bit[8] = arr[1]~arr[8]的和         = 64       (管辖8个元素)
13

14
规律: bit[i] 管辖 lowbit(i) 个元素
15
lowbit(i) = i & (-i)  // 提取最低位的1

lowbit 原理：

1
i = 6 (二进制 0110)
2
-i 的补码:
3
  ~6 = ...11111001  (按位取反)
4
  +1 = ...11111010  (加1)
5

6
i & (-i):
7
  0110
8
& 1010
9
------
10
  0010 = 2
11

12
所以 bit[6] 管辖 2 个元素: arr[5], arr[6]

可视化：

1
数组下标的二进制表示决定了管辖范围:
2

3
下标  二进制  lowbit  管辖范围
4
1     001     1       [1, 1]
5
2     010     2       [1, 2]
6
3     011     1       [3, 3]
7
4     100     4       [1, 4]
8
5     101     1       [5, 5]
9
6     110     2       [5, 6]
10
7     111     1       [7, 7]
11
8     1000    8       [1, 8]

实现#

1
class BIT {
2
private:
3
    vector<int> tree;
4
    int n;
5

6
    int lowbit(int x) {
7
        return x & (-x);
8
    }
9

10
public:
11
    BIT(int size) : n(size) {
12
        tree.resize(n + 1, 0);  // 下标从1开始
13
    }
14

15
    // 单点修改: arr[index] += val
16
    void update(int index, int val) {
17
        index++;  // 转换为1-based索引
18
        while (index <= n) {
19
            tree[index] += val;
20
            index += lowbit(index);  // 跳到父节点
21
        }
22
    }
23

24
    // 前缀和: sum(arr[0]...arr[index])
25
    int query(int index) {
26
        index++;  // 转换为1-based索引
27
        int sum = 0;
28
        while (index > 0) {
29
            sum += tree[index];
30
            index -= lowbit(index);  // 跳到下一个需要的区间
31
        }
32
        return sum;
33
    }
34

35
    // 区间和: sum(arr[L]...arr[R])
36
    int rangeQuery(int L, int R) {
37
        return query(R) - (L > 0 ? query(L - 1) : 0);
38
    }
39
};

操作详解#

单点修改 update(2, 5)#

修改 arr[2] += 5，需要更新所有包含 arr[2] 的 bit 节点：

1
更新路径: 3 → 4 → 8
2

3
index = 3 (二进制 011, lowbit=1)
4
  tree[3] += 5
5
  index = 3 + 1 = 4
6

7
index = 4 (二进制 100, lowbit=4)
8
  tree[4] += 5
9
  index = 4 + 4 = 8
10

11
index = 8 (二进制 1000, lowbit=8)
12
  tree[8] += 5
13
  index = 8 + 8 = 16 > n，结束

为什么是这条路径？

bit[3] 管辖 [3, 3]，包含 arr[2]
bit[4] 管辖 [1, 4]，包含 arr[2]
bit[8] 管辖 [1, 8]，包含 arr[2]

前缀和查询 query(6)#

查询 sum(arr[0]~arr[6])，需要累加多个 bit 节点：

1
查询路径: 7 → 6 → 4
2

3
index = 7 (二进制 111, lowbit=1)
4
  sum += tree[7]  // arr[7]
5
  index = 7 - 1 = 6
6

7
index = 6 (二进制 110, lowbit=2)
8
  sum += tree[6]  // arr[5] + arr[6]
9
  index = 6 - 2 = 4
10

11
index = 4 (二进制 100, lowbit=4)
12
  sum += tree[4]  // arr[1]~arr[4]
13
  index = 4 - 4 = 0，结束
14

15
结果: sum = arr[1]~arr[7]

拼图原理：

1
[1, 7] = [1, 4] + [5, 6] + [7, 7]
2
         ↑       ↑        ↑
3
       tree[4] tree[6]  tree[7]

建树（初始化）#

如果需要根据初始数组建树：

1
BIT(vector<int>& arr) : n(arr.size()) {
2
    tree.resize(n + 1, 0);
3
    for (int i = 0; i < n; i++) {
4
        update(i, arr[i]);  // O(n log n)
5
    }
6
}
7

8
// 更快的建树方法 O(n)
9
BIT(vector<int>& arr) : n(arr.size()) {
10
    tree.resize(n + 1, 0);
11
    for (int i = 1; i <= n; i++) {
12
        tree[i] += arr[i - 1];
13
        int j = i + lowbit(i);
14
        if (j <= n) {
15
            tree[j] += tree[i];
16
        }
17
    }
18
}

时间复杂度#

操作	时间复杂度
建树	O(n)
单点修改	O(log n)
前缀和查询	O(log n)
区间和查询	O(log n)
空间	O(n)

优缺点#

优点：

代码简洁（核心代码约 20 行）
常数因子小，实际运行快
空间占用少 O(n)

缺点：

只能处理”可逆”操作（加法可以用减法撤销）
无法处理区间最值（max/min）、区间 GCD 等
区间修改需要差分数组技巧

2.8 线段树（Segment Tree）#

功能更强大的区间操作结构

为什么需要线段树？#

树状数组虽然简洁，但有局限：

树状数组的问题：

1
只能处理"可加"操作:
2
✅ 区间和 - 可以
3
❌ 区间最大值 - 不行（没有"减法"来撤销）
4
❌ 区间GCD - 不行
5
❌ 区间修改 - 需要额外技巧

线段树的优势：

支持任意可结合的操作（和、最值、GCD、乘积等）
原生支持区间修改（懒惰标记）
更通用，代价是代码更复杂

核心思想#

线段树是一棵完全二叉树，每个节点代表一个区间：

根节点：代表整个数组区间[0, n-1]
左子节点：代表左半段
右子节点：代表右半段
叶子节点：代表单个元素

1
数组：arr = [1, 3, 5, 7, 9, 11]
2
下标：      0  1  2  3  4  5
3

4
线段树（存储区间和）：
5

6
                [0-5]:36
7
               /        \
8
          [0-2]:9        [3-5]:27
9
          /    \         /      \
10
      [0-1]:4  [2]:5  [3-4]:16  [5]:11
11
      /    \           /    \
12
   [0]:1  [1]:3     [3]:7  [4]:9
13

14
节点含义：
15
- [0-5]:36 → 区间[0,5]的和是36
16
- [0-2]:9  → 区间[0,2]的和是9
17
- [0]:1    → 单个元素arr[0]=1

树的性质：

叶子节点：单个元素
内部节点：左右子树的合并结果
树高：O(log n)

实现#

节点定义#

1
class SegmentTreeNode {
2
public:
3
    int start, end;      // 区间范围[start, end]
4
    int sum;             // 区间和（可改为max/min/gcd等）
5
    SegmentTreeNode *left, *right;
6

7
    SegmentTreeNode(int s, int e) : start(s), end(e), sum(0),
8
                                     left(nullptr), right(nullptr) {}
9
};
10

11
class SegmentTree {
12
private:
13
    SegmentTreeNode* root;
14
    vector<int> arr;
15

16
    SegmentTreeNode* build(int start, int end);
17
    int queryHelper(SegmentTreeNode* node, int L, int R);
18
    void updateHelper(SegmentTreeNode* node, int index, int val);
19

20
public:
21
    SegmentTree(vector<int>& nums);
22
    int query(int L, int R);
23
    void update(int index, int val);
24
};

建树（Build）#

1
SegmentTreeNode* build(int start, int end) {
2
    SegmentTreeNode* node = new SegmentTreeNode(start, end);
3

4
    // 叶子节点
5
    if (start == end) {
6
        node->sum = arr[start];
7
        return node;
8
    }
9

10
    // 递归构造左右子树
11
    int mid = start + (end - start) / 2;
12
    node->left = build(start, mid);
13
    node->right = build(mid + 1, end);
14

15
    // 合并左右子树
16
    node->sum = node->left->sum + node->right->sum;
17

18
    return node;
19
}
20

21
// 时间：O(n)

建树过程示例：

1
arr = [1, 3, 5, 7]
2

3
build(0, 3):
4
  mid = 1
5

6
  build(0, 1):
7
    mid = 0
8
    build(0, 0): 返回[0]:1
9
    build(1, 1): 返回[1]:3
10
    返回[0-1]:4
11

12
  build(2, 3):
13
    mid = 2
14
    build(2, 2): 返回[2]:5
15
    build(3, 3): 返回[3]:7
16
    返回[2-3]:12
17

18
  返回[0-3]:16

区间查询（Query）#

1
int queryHelper(SegmentTreeNode* node, int L, int R) {
2
    // 情况1：当前区间完全在[L, R]内
3
    if (node->start >= L && node->end <= R) {
4
        return node->sum;
5
    }
6

7
    // 情况2：当前区间与[L, R]无交集
8
    if (node->start > R || node->end < L) {
9
        return 0;
10
    }
11

12
    // 情况3：部分重叠，递归查询左右子树
13
    return queryHelper(node->left, L, R) +
14
           queryHelper(node->right, L, R);
15
}
16

17
int query(int L, int R) {
18
    return queryHelper(root, L, R);
19
}
20

21
// 时间：O(log n)

查询示例： 查询 [1, 3] 的和

1
arr = [1, 3, 5, 7]
2

3
query(1, 3):
4
  当前节点[0-3]，部分重叠
5

6
  query左子[0-1]，查询[1, 3]:
7
    部分重叠
8
    query左子[0]，查询[1, 3]: 无交集，返回0
9
    query右子[1]，查询[1, 3]: 完全包含，返回3
10
    返回 0 + 3 = 3
11

12
  query右子[2-3]，查询[1, 3]:
13
    完全包含，返回12
14

15
  返回 3 + 12 = 15  ✓

单点修改（Update）#

1
void updateHelper(SegmentTreeNode* node, int index, int val) {
2
    // 找到叶子节点
3
    if (node->start == node->end) {
4
        node->sum = val;
5
        return;
6
    }
7

8
    // 递归更新子树
9
    int mid = node->start + (node->end - node->start) / 2;
10
    if (index <= mid) {
11
        updateHelper(node->left, index, val);
12
    } else {
13
        updateHelper(node->right, index, val);
14
    }
15

16
    // 更新当前节点
17
    node->sum = node->left->sum + node->right->sum;
18
}
19

20
void update(int index, int val) {
21
    updateHelper(root, index, val);
22
}
23

24
// 时间：O(log n)

更新示例： 修改 arr[1] = 10

1
原数组：[1, 3, 5, 7]
2
修改后：[1, 10, 5, 7]
3

4
update(1, 10):
5
  当前节点[0-3]
6
    mid = 1，index=1 <= mid，递归左子
7

8
    update左子[0-1]:
9
      mid = 0，index=1 > mid，递归右子
10

11
      update右子[1]:
12
        叶子节点，sum = 10
13

14
      更新[0-1]: sum = 1 + 10 = 11
15

16
    更新[0-3]: sum = 11 + 12 = 23
17

18
树的变化：
19
        [0-3]:16              [0-3]:23
20
       /        \            /        \
21
   [0-1]:4    [2-3]:12 → [0-1]:11   [2-3]:12
22
   /    \      /    \    /    \      /    \
23
[0]:1 [1]:3 [2]:5 [3]:7 [0]:1 [1]:10 [2]:5 [3]:7

区间修改（懒惰标记）#

如果需要区间修改，如：updateRange(L, R, val) - 将区间 [L, R] 所有元素加上 val

朴素做法： 遍历 [L, R] 逐个修改 → O(n log n)

优化思路：延迟更新

修改时只更新涉及的节点，打上”懒惰标记”
查询时再向下传递标记

1
class SegmentTreeNode {
2
public:
3
    int start, end;
4
    int sum;
5
    int lazy;  // 懒惰标记
6
    SegmentTreeNode *left, *right;
7

8
    SegmentTreeNode(int s, int e) : start(s), end(e), sum(0), lazy(0),
9
                                     left(nullptr), right(nullptr) {}
10
};
11

12
// 下推懒惰标记
13
void pushDown(SegmentTreeNode* node) {
14
    if (node->lazy == 0) return;
15

16
    int len = node->end - node->start + 1;
17
    int leftLen = len - len / 2;
18
    int rightLen = len / 2;
19

20
    // 更新左子树
21
    node->left->sum += node->lazy * leftLen;
22
    node->left->lazy += node->lazy;
23

24
    // 更新右子树
25
    node->right->sum += node->lazy * rightLen;
26
    node->right->lazy += node->lazy;
27

28
    // 清除当前标记
29
    node->lazy = 0;
30
}
31

32
// 区间修改：[L, R] 所有元素加 val
33
void updateRange(SegmentTreeNode* node, int L, int R, int val) {
34
    // 完全包含
35
    if (node->start >= L && node->end <= R) {
36
        int len = node->end - node->start + 1;
37
        node->sum += val * len;
38
        node->lazy += val;
39
        return;
40
    }
41

42
    // 无交集
43
    if (node->start > R || node->end < L) {
44
        return;
45
    }
46

47
    // 部分重叠：先下推标记，再递归
48
    pushDown(node);
49
    updateRange(node->left, L, R, val);
50
    updateRange(node->right, L, R, val);
51

52
    // 更新当前节点
53
    node->sum = node->left->sum + node->right->sum;
54
}
55

56
// 区间查询需要先下推标记
57
int query(SegmentTreeNode* node, int L, int R) {
58
    if (node->start >= L && node->end <= R) {
59
        return node->sum;
60
    }
61

62
    if (node->start > R || node->end < L) {
63
        return 0;
64
    }
65

66
    pushDown(node);  // 先下推标记
67
    return query(node->left, L, R) + query(node->right, L, R);
68
}

时间复杂度： 区间修改和查询都是 O(log n)

扩展：其他类型的线段树#

区间最大值/最小值#

1
// 只需修改合并逻辑
2
node->maxVal = max(node->left->maxVal, node->right->maxVal);

区间 GCD#

1
int gcd(int a, int b) {
2
    return b ? gcd(b, a % b) : a;
3
}
4

5
node->gcdVal = gcd(node->left->gcdVal, node->right->gcdVal);

时间复杂度#

操作	时间	空间
建树	O(n)	O(4n)
单点修改	O(log n)	-
区间修改（懒惰标记）	O(log n)	-
区间查询	O(log n)	-

空间分析：

完全二叉树最多有 2n-1 个节点
但用指针实现，实际约 4n 空间（预留满二叉树空间）

对比总结#

特性	树状数组	线段树
代码复杂度	简单（20 行）	复杂（100 行）
空间	O(n)	O(4n)
常数因子	小	较大
适用操作	可逆操作（加法）	任意可结合操作
区间修改	需要差分技巧	原生支持（懒惰标记）
应用场景	区间和、竞赛	复杂区间操作

选择建议：

只需要区间和 + 单点修改 → 树状数组（代码短、常数小）
需要区间最值 / 区间修改 / 复杂操作 → 线段树

STL 替代： C++ 标准库没有直接的线段树/树状数组实现，需要手写或使用第三方库。

第三部分：图#

数据元素之间是”多对多”的关系。

3.0 图的基本概念#

图 G = (V, E)

V：顶点集合
E：边集合

1
无向图：
2
    A --- B
3
    |     |
4
    C --- D
5

6
有向图：
7
    A → B
8
    ↓   ↓
9
    C → D
10

11
带权图：
12
    A --5-- B
13
    |       |
14
    3       2
15
    |       |
16
    C --1-- D

术语#

顶点/节点(Vertex/Node): 图中的基本单元(如 A、B、C、D)
边(Edge): 连接两个顶点的线
- 无向边: 双向连接，如 A---B
- 有向边: 单向连接，如 A→B
邻接(Adjacent): 两个顶点之间有边直接相连
度(Degree):
- 无向图: 与该顶点相连的边数
- 有向图:
  - 入度(In-degree): 指向该顶点的边数
  - 出度(Out-degree): 从该顶点发出的边数
权重(Weight): 边上的数值，表示代价、距离等
路径(Path): 顶点序列，相邻顶点间有边连接
简单路径: 路径中顶点不重复
环/回路(Cycle): 起点和终点相同的路径

分类#

无向图(Undirected Graph): 边没有方向
有向图(Directed Graph/Digraph): 边有方向
加权图(Weighted Graph): 边带有权重
完全图: 任意两个顶点之间都有边
- n 个顶点的无向完全图有 n(n-1)/2 条边
- n 个顶点的有向完全图有 n(n-1) 条边
连通图: 任意两个顶点之间都有路径可达
稀疏图: 边数远小于完全图(|E| << |V|²)
稠密图: 边数接近完全图

3.1 图的存储#

邻接矩阵(Adjacency Matrix)#

n×n 矩阵

1
    A --- B
2
    |     |
3
    C --- D
4

5
     A B C D
6
   A[0 1 1 0]
7
   B[1 0 1 1]
8
   C[1 1 0 1]
9
   D[0 1 1 0]

复杂度：

操作	时间	空间
判断有无边	O(1)	O(V²)
获取邻居	O(V)
添加边	O(1)

适用： 稠密图

邻接表(Adjacency List)#

每个顶点维护一个表，存储相邻顶点

1
    A --- B
2
    |     |
3
    C --- D
4

5
邻接表：
6
A(0) → [B, C]
7
B(1) → [A, D]
8
C(2) → [A, D]
9
D(3) → [B, C]

复杂度：

操作	时间	空间
判断有无边	O(degree)	O(V+E)
获取邻居	O(degree)
添加边	O(1)

复杂度对比#

特性	邻接矩阵	邻接表
空间	O(V²)	O(V+E)
判断有无边	O(1)	O(degree)
遍历邻居	O(V)	O(degree)
适合	稠密图	稀疏图

实际选择： 大多数图是稀疏的，用邻接表。

3.3 图的遍历#

这里只讨论遍历机制，不讨论基于遍历的具体算法问题（如最短路径、连通性判定等）。 DFS / BFS 本质上描述的是在给定存储结构下，节点被访问的基本顺序规则，属于“如何访问数据”的范畴。

深度优先搜索（DFS）#

思想： 一条路走到底，走不通再回头。

1
    A --- B
2
    |     |
3
    C --- D
4

5
从A开始DFS：
6
访问A → 访问B → 访问D → 回溯到A → 访问C
7
顺序：A → B → D → C

递归实现：

1
class Graph {
2
private:
3
    int numVertices;
4
    vector<vector<int>> adjList;
5

6
    void DFSHelper(int v, vector<bool>& visited) {
7
        visited[v] = true;
8
        cout << v << " ";
9

10
        for (int neighbor : adjList[v]) {
11
            if (!visited[neighbor]) {
12
                DFSHelper(neighbor, visited);
13
            }
14
        }
15
    }
16

17
public:
18
    Graph(int n) : numVertices(n) {
19
        adjList.resize(n);
20
    }
21

22
    void addEdge(int u, int v) {
23
        adjList[u].push_back(v);
24
        adjList[v].push_back(u);
25
    }
26

27
    void DFS(int start) {
28
        vector<bool> visited(numVertices, false);
29
        DFSHelper(start, visited);
30
    }
31
};

迭代实现（用栈）：

1
void DFS_iterative(int start) {
2
    vector<bool> visited(numVertices, false);
3
    stack<int> s;
4

5
    s.push(start);
6

7
    while (!s.empty()) {
8
        int v = s.top();
9
        s.pop();
10

11
        if (visited[v]) continue;
12

13
        visited[v] = true;
14
        cout << v << " ";
15

16
        // 反向压栈保持顺序一致
17
        for (int i = adjList[v].size() - 1; i >= 0; i--) {
18
            if (!visited[adjList[v][i]]) {
19
                s.push(adjList[v][i]);
20
            }
21
        }
22
    }
23
}

时间复杂度：

邻接表：O(V + E)
邻接矩阵：O(V²)

广度优先搜索（BFS）#

思想： 一层一层访问，先访问离起点近的。

1
    A --- B
2
    |     |
3
    C --- D
4

5
从A开始BFS：
6
第0层：A
7
第1层：B, C（A的邻居）
8
第2层：D（B和C的邻居）
9

10
顺序：A → B → C → D

实现（用队列）：

1
void BFS(int start) {
2
    vector<bool> visited(numVertices, false);
3
    queue<int> q;
4

5
    visited[start] = true;
6
    q.push(start);
7

8
    while (!q.empty()) {
9
        int v = q.front();
10
        q.pop();
11
        cout << v << " ";
12

13
        for (int neighbor : adjList[v]) {
14
            if (!visited[neighbor]) {
15
                visited[neighbor] = true;
16
                q.push(neighbor);
17
            }
18
        }
19
    }
20
}

BFS 求最短距离：

1
vector<int> BFS_distance(int start) {
2
    vector<int> dist(numVertices, -1);
3
    vector<bool> visited(numVertices, false);
4
    queue<int> q;
5

6
    visited[start] = true;
7
    dist[start] = 0;
8
    q.push(start);
9

10
    while (!q.empty()) {
11
        int v = q.front();
12
        q.pop();
13

14
        for (int neighbor : adjList[v]) {
15
            if (!visited[neighbor]) {
16
                visited[neighbor] = true;
17
                dist[neighbor] = dist[v] + 1;
18
                q.push(neighbor);
19
            }
20
        }
21
    }
22

23
    return dist;
24
}

时间复杂度：

邻接表：O(V + E)
邻接矩阵：O(V²)

对比#

特性	DFS	BFS
数据结构	栈（递归）	队列
搜索方式	深度优先	广度优先
空间	O(h)	O(w)
最短路径	不保证	保证（无权图）
应用	连通性、环检测	最短路径、层次

h=深度，w=宽度

第四部分：特殊数据结构#

4.1 哈希表#

通过哈希函数将 key 映射到数组下标，实现 O(1)查找。

1
想存储学号 → 成绩：
2
20210001 → 85
3
20210002 → 90
4

5
hash(20210001) = 1 → 存在arr[1]
6
hash(20210002) = 2 → 存在arr[2]

哈希函数#

**1) 除留余数法（最常用）**禁止

1
int hash(int key, int size) {
2
    return key % size;
3
}

2) 字符串哈希

1
int hash(string str, int size) {
2
    unsigned long hash = 0;
3
    for (char c : str) {
4
        hash = hash * 31 + c;
5
    }
6
    return hash % size;
7
}

好的哈希函数：

计算快
分布均匀
确定性

哈希冲突#

不同 key 可能映射到同一位置。

1
hash(20210001) = 1
2
hash(20210011) = 1  ← 冲突！

解决方法：

链地址法（Chaining）#

数组每个位置存一个链表。

1
哈希表：
2
[0] → nullptr
3
[1] → [20210001, 85] → [20210011, 92] → nullptr
4
[2] → [20210002, 90] → nullptr

1
class HashTable {
2
private:
3
    class Node {
4
    public:
5
        int key;
6
        int value;
7
        Node* next;
8
        Node(int k, int v) : key(k), value(v), next(nullptr) {}
9
    };
10

11
    vector<Node*> table;
12
    int size;
13

14
public:
15
    HashTable(int s) : size(s) {
16
        table.resize(s, nullptr);
17
    }
18

19
    void insert(int key, int value) {
20
        int index = key % size;
21

22
        // 检查key是否已存在
23
        Node* curr = table[index];
24
        while (curr) {
25
            if (curr->key == key) {
26
                curr->value = value;  // 更新
27
                return;
28
            }
29
            curr = curr->next;
30
        }
31

32
        // 头插法插入新节点
33
        Node* newNode = new Node(key, value);
34
        newNode->next = table[index];
35
        table[index] = newNode;
36
    }
37

38
    int search(int key) {
39
        int index = key % size;
40
        Node* curr = table[index];
41

42
        while (curr) {
43
            if (curr->key == key)
44
                return curr->value;
45
            curr = curr->next;
46
        }
47
        return -1;  // 未找到
48
    }
49

50
    void remove(int key) {
51
        int index = key % size;
52
        Node* curr = table[index];
53
        Node* prev = nullptr;
54

55
        while (curr) {
56
            if (curr->key == key) {
57
                if (prev == nullptr) {
58
                    table[index] = curr->next;
59
                } else {
60
                    prev->next = curr->next;
61
                }
62
                delete curr;
63
                return;
64
            }
65
            prev = curr;
66
            curr = curr->next;
67
        }
68
    }
69
};

性能：

平均：O(1 + α)，α = n/size（装填因子）
最坏：O(n)，所有 key 都冲突

优点：

实现简单
删除方便
不会满

缺点：

额外指针空间
缓存不友好

开放地址法（Open Addressing）#

所有元素都存在数组里，冲突时找下一个空位。

线性探测：

1
hash(key) 有人了，试 hash(key)+1
2
hash(key)+1 也有人，试 hash(key)+2
3
...

1
class HashTableOpen {
2
private:
3
    vector<int> keys;
4
    vector<int> values;
5
    vector<bool> occupied;
6
    int size;
7

8
public:
9
    HashTableOpen(int s) : size(s) {
10
        keys.resize(s);
11
        values.resize(s);
12
        occupied.resize(s, false);
13
    }
14

15
    void insert(int key, int value) {
16
        int index = key % size;
17
        int i = 0;
18

19
        while (occupied[index]) {
20
            if (keys[index] == key) {
21
                values[index] = value;  // 更新
22
                return;
23
            }
24
            index = (index + 1) % size;  // 线性探测
25
            i++;
26
            if (i == size) {
27
                throw runtime_error("哈希表已满");
28
            }
29
        }
30

31
        keys[index] = key;
32
        values[index] = value;
33
        occupied[index] = true;
34
    }
35

36
    int search(int key) {
37
        int index = key % size;
38
        int i = 0;
39

40
        while (occupied[index]) {
41
            if (keys[index] == key)
42
                return values[index];
43
            index = (index + 1) % size;
44
            i++;
45
            if (i == size) break;
46
        }
47
        return -1;
48
    }
49
};

删除的问题： 不能直接删除，要用”墓碑”标记。

1
[1] key1
2
[2] key2  ← 删除key2
3
[3] key3
4

5
如果直接删除，查找key3会在[2]停止！
6
需要标记[2]为"已删除但仍占位"

其他探测方法：

二次探测：

1
试探序列：hash(key), hash(key)+1², hash(key)+2², ...

双重哈希：

1
step = hash2(key)
2
试探序列：hash(key), hash(key)+step, hash(key)+2*step, ...

优点：

无额外指针
缓存友好

缺点：

删除复杂
可能满
冲突多时性能下降快

装填因子（Load Factor）#

1
α = n / size
2
n: 元素个数
3
size: 哈希表大小

影响：

α 越大，冲突越多
链地址法：α 可以>1
开放地址法：α 必须<1（通常<0.7）

扩容策略：

1
void resize() {
2
    int oldSize = size;
3
    int newSize = oldSize * 2;
4

5
    vector<Node*> newTable(newSize, nullptr);
6

7
    // 重新哈希所有元素
8
    for (int i = 0; i < oldSize; i++) {
9
        Node* curr = table[i];
10
        while (curr) {
11
            Node* next = curr->next;
12
            int newIndex = curr->key % newSize;
13
            curr->next = newTable[newIndex];
14
            newTable[newIndex] = curr;
15
            curr = next;
16
        }
17
    }
18

19
    table = newTable;
20
    size = newSize;
21
}

扩容时机： 通常当 α > 0.75 时扩容

STL：unordered_set 和 unordered_map#

unordered_set（无序集合）：

1
unordered_set<int> s;
2

3
// 插入
4
s.insert(30);
5
s.insert(10);
6
s.insert(20);
7

8
// 查找
9
if (s.find(20) != s.end()) {
10
    cout << "找到" << endl;
11
}
12

13
s.count(10);  // 返回0或1
14

15
// 删除
16
s.erase(10);
17

18
// 遍历（无序）
19
for (int x : s) {
20
    cout << x << " ";
21
}
22

23
// 其他
24
s.size();
25
s.empty();
26
s.clear();

unordered_map（无序键值对）：

1
unordered_map<string, int> m;
2

3
// 插入
4
m["Alice"] = 85;
5
m["Bob"] = 90;
6

7
// 访问
8
cout << m["Alice"] << endl;
9

10
// 查找
11
if (m.find("Bob") != m.end()) {
12
    cout << "找到" << endl;
13
}
14

15
m.count("Alice");  // 返回0或1
16

17
// 删除
18
m.erase("Charlie");
19

20
// 遍历（无序）
21
for (auto& p : m) {
22
    cout << p.first << ": " << p.second << endl;
23
}
24

25
// 其他
26
m.size();
27
m.empty();
28
m.clear();

set/map vs unordered_set/map#

特性	set/map	unordered_set/map
底层	红黑树	哈希表
有序性	有序	无序
查找	O(log n)	O(1)平均
插入	O(log n)	O(1)平均
删除	O(log n)	O(1)平均
最坏	O(log n)	O(n)

选择原则：

需要有序 → set/map
只需要快速查找 → unordered_set/map
大多数情况用 unordered 更快

复杂度#

操作	平均	最坏
查找	O(1)	O(n)
插入	O(1)	O(n)
删除	O(1)	O(n)

4.2 并查集（Union-Find）#

维护元素的集合归属关系。

操作：

find(x)：x 属于哪个集合？
union(x, y)：合并 x 和 y 所在集合

应用：

判断图的连通性
检测环
朋友圈问题

用树表示集合，根节点代表集合 ID。

1
三个集合：{1,2,3}, {4,5}, {6}
2

3
树表示：
4
    1        4      6
5
   / \       |
6
  2   3      5
7

8
find(2) → 1（2的根是1）
9
find(5) → 4

问题场景#

假设有以下朋友关系：

Alice 和 Bob 是朋友
Bob 和 Charlie 是朋友
David 和 Eve 是朋友

问题 1： Alice 和 Charlie 是朋友吗？（间接朋友也算） 问题 2： 一共有几个朋友圈？

朴素方法：

用图存储，DFS/BFS 判断连通性 → O(V+E)
如果有 n 次查询，总复杂度 O(n(V+E))

能否优化？ → 并查集: 每次查询接近 O(1)

基础实现#

1
class UnionFind {
2
private:
3
    vector<int> parent;
4

5
public:
6
    UnionFind(int n) {
7
        parent.resize(n);
8
        for (int i = 0; i < n; i++) {
9
            parent[i] = i;  // 初始时，每个元素自成集合
10
        }
11
    }
12

13
    // 查找根节点
14
    int find(int x) {
15
        if (parent[x] == x)
16
            return x;
17
        return find(parent[x]);
18
    }
19

20
    // 合并两个集合
21
    void unite(int x, int y) {
22
        int rootX = find(x);
23
        int rootY = find(y);
24
        if (rootX != rootY) {
25
            parent[rootX] = rootY;
26
        }
27
    }
28

29
    // 判断是否连通
30
    bool connected(int x, int y) {
31
        return find(x) == find(y);
32
    }
33
};

问题： 树可能变得很高，find 变慢。

1
最坏情况：链状
2
  4
3
  |
4
  3
5
  |
6
  2
7
  |
8
  1
9
  |
10
  0
11

12
find(0)需要O(n)时间

路径压缩#

在 find 时，把路径上所有节点直接连到根。

1
int find(int x) {
2
    if (parent[x] != x) {
3
        parent[x] = find(parent[x]);  // 路径压缩
4
    }
5
    return parent[x];
6
}

效果：

按秩合并#

合并时，把矮的树接到高的树下。

1
class UnionFind {
2
private:
3
    vector<int> parent;
4
    vector<int> rank;  // 树的高度
5

6
public:
7
    UnionFind(int n) {
8
        parent.resize(n);
9
        rank.resize(n, 0);
10
        for (int i = 0; i < n; i++) {
11
            parent[i] = i;
12
        }
13
    }
14

15
    int find(int x) {
16
        if (parent[x] != x) {
17
            parent[x] = find(parent[x]);  // 路径压缩
18
        }
19
        return parent[x];
20
    }
21

22
    void unite(int x, int y) {
23
        int rootX = find(x);
24
        int rootY = find(y);
25

26
        if (rootX == rootY) return;
27

28
        // 按秩合并
29
        if (rank[rootX] < rank[rootY]) {
30
            parent[rootX] = rootY;
31
        } else if (rank[rootX] > rank[rootY]) {
32
            parent[rootY] = rootX;
33
        } else {
34
            parent[rootY] = rootX;
35
            rank[rootX]++;
36
        }
37
    }
38

39
    bool connected(int x, int y) {
40
        return find(x) == find(y);
41
    }
42
};

复杂度#

两个优化一起用：

操作	时间
find	O(α(n))
union	O(α(n))

α(n)是反阿克曼函数，增长极慢：

α(10^80) ≈ 4
实际中可认为是 O(1)

附录#

时间复杂度总表#

线性结构#

数据结构	访问	查找	插入	删除	空间
数组	O(1)	O(n)	O(n)	O(n)	O(n)
动态数组	O(1)	O(n)	O(1)均摊	O(n)	O(n)
链表	O(n)	O(n)	O(1)*	O(1)*	O(n)
栈	-	-	O(1)	O(1)	O(n)
队列	-	-	O(1)	O(1)	O(n)

*已知位置

树形结构#

数据结构	查找	插入	删除	空间	备注
BST	O(log n)	O(log n)	O(log n)	O(n)	最坏 O(n)
AVL 树	O(log n)	O(log n)	O(log n)	O(n)	严格平衡
红黑树	O(log n)	O(log n)	O(log n)	O(n)	弱平衡
B/B+树	O(log n)	O(log n)	O(log n)	O(n)	磁盘友好
堆	O(n)	O(log n)	O(log n)	O(n)	查看堆顶 O(1)
哈夫曼树	-	-	-	O(n)	编码用
线段树	O(log n)	O(log n)	-	O(4n)	区间操作
树状数组	O(log n)	O(log n)	-	O(n)	区间和

图#

存储方式	空间	判断边	获取邻居
邻接矩阵	O(V²)	O(1)	O(V)
邻接表	O(V+E)	O(度)	O(度)

遍历方式	时间(邻接表)	时间(邻接矩阵)	空间
DFS	O(V+E)	O(V²)	O(V)
BFS	O(V+E)	O(V²)	O(V)

特殊结构#

数据结构	查找	插入	删除	空间
哈希表	O(1)平均	O(1)平均	O(1)平均	O(n)
并查集	O(α(n))≈O(1)	O(α(n))≈O(1)	-	O(n)

本讲义的范围#

聚焦数据结构，不涉及算法：

✅ 包含的内容（数据结构课）#

数据的存储方式
基本的增删改查操作
遍历方法（DFS/BFS）

本讲义中的“遍历、构造、维护”等过程，均用于说明数据结构本身的组织方式与基本操作。不将其作为“解决具体问题的算法”来讨论。

❌ 不包含的内容（算法课）#

基于数据结构解决具体问题的算法设计
最短路径、最优解、判定类问题
图算法：Dijkstra、Floyd、最短路径、最小生成树、拓扑排序
字符串算法：KMP、AC 自动机
高级数据结构：跳表、布隆过滤器、伸展树

边界示例#

✅ 图的邻接表存储 → 数据结构
✅ 图的 DFS/BFS 遍历 → 数据结构（基本访问）
❌ Dijkstra 最短路径 → 算法课

Stella forward

数据结构讲义

第一部分：线性结构#

1.1 顺序表/向量/一维张量/数组#

存储原理#

基本操作#

时间复杂度#

优缺点#

1.2 动态数组#

核心思想#

手动实现#

扩容策略分析#

缩容策略#

STL 实现：vector#

1.3 链表#

存储原理#

基本操作#

双向链表#

循环链表#

STL：list#

时间复杂度#

1.4 受限的访问模式（栈、队列）#

栈（Stack）#

手动实现#

时间复杂度#

STL：stack#

队列（Queue）#

循环队列（数组实现）#

时间复杂度#

STL：queue#

STL：deque（双端队列）#

第二部分：树形结构#

2.0 树的基本概念#

术语#

度量指标#

树的性质#

2.1 树的存储方式#

链式存储(常用)#

数组存储(适合完全二叉树)#

父节点数组#

邻接表(通用树)#

三元组表示(较少用)#

存储方式对比#

2.2 二叉树#

二叉树的类型#

满二叉树#

完全二叉树#

树的遍历#

深度优先遍历 (DFS)#

广度优先遍历 (BFS)#

2.3 二叉搜索树 (Binary Search Tree, BST)#

关键性质#

查找#

插入#

删除#

复杂度#

2.4 平衡二叉树 (Balanced Binary Tree)#

问题引入#

核心概念#

1. AVL 树#

旋转操作#

1. 右旋 (LL 情况)#

2. 左旋 (RR 情况)#

3. 先左旋后右旋 (LR 情况)#

4. 先右旋后左旋 (RL 情况)#

插入操作#

时间复杂度#

2. 红黑树 (Red-Black Tree)#

插入修复#

时间复杂度#

STL set（有序集合，元素唯一）#

STL map（有序键值对，key 唯一）#

3. B 树 / B+ 树#

B 树#

插入操作#

查找操作#

时间复杂度#

B+树#

平衡树对比#

2.5 堆（Heap）#