二叉树是最重要的基本数据结构，没有之一。
1、二叉树本身是比较简单的基础数据结构，但是很多复杂的数据结构都是基于二叉树的，比如 红黑树（二叉搜索树）、多叉树、二叉堆、图、字典树、并查集、线段树 等等。
2、二叉树不单纯是一种数据结构，更是一种常用的算法思维。一切暴力穷举算法，比如 回溯算法、BFS 算法、动态规划 本质上也是把具体问题抽象成树结构，你只要抽象出来了，这些问题最终都回归二叉树的问题。
满二叉树
满二叉树就是每一层节点都是满的
满二叉树有个优势，就是它的节点个数很好算。假设深度为 h，那么总节点数就是 2^h - 1
完全二叉树
二叉树的每一层的节点都紧凑靠左排列，且除了最后一层，其他每层都必须是满的
完全二叉树的左右子树也是完全二叉树。
或者更准确地说应该是：完全二叉树的左右子树中，至少有一棵是满二叉树。
二叉搜索树
对于树中的每个节点，其左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。
BST 是非常常用的数据结构。因为左小右大的特性，可以让我们在 BST 中快速找到某个节点，或者找到某个范围内的所有节点，这是 BST 的优势所在。
高度平衡二叉树
它的「每个节点」的左右子树的高度差不超过 1。
假设高度平衡二叉树中共有 N 个节点，那么高度平衡二叉树的高度是 O(logN)
自平衡二叉树
在增删二叉树节点时对树的结构进行一些调整，那么就可以让树的高度始终是平衡的，这就是自平衡二叉树
最经典的就是红黑树，一种自平衡的二叉搜索树。
二叉树的遍历模板
二叉树只有递归遍历和层序遍历这两种
递归遍历：前序，中序，后序
递归遍历（DFS）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| // 基本的二叉树节点
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 二叉树的递归遍历框架
void traverse(TreeNode* root) {
if (root == nullptr) {
return;
}
traverse(root->left);
traverse(root->right);
}
|
递归遍历节点的顺序仅取决于左右子节点的递归调用顺序，与其他代码无关
前中后序遍历
1
2
3
4
5
6
7
8
9
10
11
| // 二叉树的遍历框架
void traverse(TreeNode* root) {
if (root == nullptr) {
return;
}
// 前序位置
traverse(root->left);
// 中序位置
traverse(root->right);
// 后序位置
}
|
在 traverse 函数中不同位置写代码，效果是可以不一样的。前中后序遍历的结果不同，原因是因为你把代码写在了不同位置，所以产生了不同的效果。
前序位置的代码会在进入节点时立即执行；中序位置的代码会在左子树遍历完成后，遍历右子树之前执行；后序位置的代码会在左右子树遍历完成后执行
二叉搜索树（BST） 的中序遍历结果是有序的，这是 BST 的一个重要性质。
层序遍历（BFS）
层序遍历需要借助队列来实现，而且根据不同的需求，可以有三种不同的写法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void levelOrderTraverse(TreeNode* root) {
if (root == nullptr) {
return;
}
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
// 访问 cur 节点
std::cout << cur->val << std::endl;
// 把 cur 的左右子节点加入队列
if (cur->left != nullptr) {
q.push(cur->left);
}
if (cur->right != nullptr) {
q.push(cur->right);
}
}
}
|
这种写法的缺点是，无法知道当前节点在第几层。
方法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| void levelOrderTraverse(TreeNode* root) {
if (root == nullptr) {
return;
}
queue<TreeNode*> q;
q.push(root);
// 记录当前遍历到的层数（根节点视为第 1 层）
int depth = 1;
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode* cur = q.front();
q.pop();
// 访问 cur 节点，同时知道它所在的层数
cout << "depth = " << depth << ", val = " << cur->val << endl;
// 把 cur 的左右子节点加入队列
if (cur->left != nullptr) {
q.push(cur->left);
}
if (cur->right != nullptr) {
q.push(cur->right);
}
}
depth++;
}
}
|
最常见，可计算深度
方法三
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class State {
public:
TreeNode* node;
int depth; //维护权重
State(TreeNode* node, int depth) : node(node), depth(depth) {}
};
void levelOrderTraverse(TreeNode* root) {
if (root == nullptr) {
return;
}
queue<State> q;
// 根节点的路径权重和是 1
q.push(State(root, 1));
while (!q.empty()) {
State cur = q.front();
q.pop();
// 访问 cur 节点，同时知道它的路径权重和
cout << "depth = " << cur.depth << ", val = " << cur.node->val << endl;
// 把 cur 的左右子节点加入队列
if (cur.node->left != nullptr) {
q.push(State(cur.node->left, cur.depth + 1));
}
if (cur.node->right != nullptr) {
q.push(State(cur.node->right, cur.depth + 1));
}
}
}
|
二叉树遍历实现
中序遍历
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
void inorder(TreeNode* root, vector<int>& vec) {
if (root == nullptr) {
return;
}
inorder(root->left, vec);
vec.push_back(root->val);
inorder(root->right, vec);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> vec;
inorder(root, vec);
return vec;
}
};
|
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> vec;
stack<TreeNode*> stk;
while(root != nullptr || !stk.empty()) {
while(root != nullptr) {
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
vec.push_back(root->val);
root = root->right;
}
return vec;
}
};
|
Morris 中序遍历
后序遍历
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
void traversal(TreeNode* root, vector<int>& vec) {
if (root == nullptr) {
return;
}
traversal(root->left, vec);
traversal(root->right, vec);
vec.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> vec;
traversal(root, vec);
return vec;
}
};
|
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> vec;
stack<TreeNode*> stk;
TreeNode* prev = nullptr;
while(root != nullptr || !stk.empty()) {
while(root != nullptr) {
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
if (root->right == nullptr || root->right == prev) {
vec.push_back(root->val);
prev = root;
root = nullptr;
} else {
stk.push(root);
root = root->right;
}
}
return vec;
}
};
|
Morris 后序遍历
前序遍历
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
void traversal(TreeNode* root, vector<int>& vec) {
if (root == nullptr) {
return;
}
vec.push_back(root->val);
traversal(root->left, vec);
traversal(root->right, vec);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vec;
traversal(root, vec);
return vec;
}
};
|
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vec;
stack<TreeNode*> stk;
while(root != nullptr || !stk.empty()) {
while(root != nullptr) {
vec.push_back(root->val);
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
root = root->right;
}
return vec;
}
};
|
Morris 前序遍历
层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) {
return res;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
vector<int> vec;
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode* cur = q.front();
q.pop();
vec.push_back(cur->val);
if (cur->left != nullptr) {
q.push(cur->left);
}
if (cur->right != nullptr) {
q.push(cur->right);
}
}
res.push_back(vec);
}
return res;
}
};
|
多叉树的递归/层序遍历
二叉树的节点长这样，每个节点有两个子节点：
1
2
3
4
5
6
7
8
| class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
|
多叉树的节点长这样，每个节点有任意个子节点：
1
2
3
4
5
6
7
8
9
10
11
12
| class Node {
public:
int val;
vector<Node*> children; // 多叉树节点：多个子节点，而非左右子树
Node() {}
Node(int _val) { val = _val; }
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
|
森林就是多个多叉树的集合（单独一棵多叉树也是一个特殊的森林），用代码表示就是多个多叉树的根节点列表
只需对每个根节点分别进行 DFS/BFS 遍历，即可遍历森林的所有节点。
多叉树递归遍历（DFS）
多叉树无中序遍历（无左右子树之分，只有子节点列表），递归遍历核心是 “遍历当前节点 → 递归遍历所有子节点”。
前序遍历（写法：基础递归）
逻辑：先访问当前节点，再递归遍历每个子节点（子节点顺序按列表顺序）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<int> preorder(Node* root) {
vector<int> res;
dfs_pre(root, res);
return res;
}
// 辅助递归函数
void dfs_pre(Node* root, vector<int>& res) {
if (root == nullptr) return; // 空指针判断，避免运行时错误
res.push_back(root->val); // 先访问当前节点
// 递归遍历所有子节点
for (Node* child : root->children) {
dfs_pre(child, res);
}
}
|
后序遍历（写法：基础递归）
逻辑：先递归遍历所有子节点，最后访问当前节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<int> postorder(Node* root) {
vector<int> res;
dfs_post(root, res);
return res;
}
// 辅助递归函数
void dfs_post(Node* root, vector<int>& res) {
if (root == nullptr) return;
// 先递归遍历所有子节点
for (Node* child : root->children) {
dfs_post(child, res);
}
res.push_back(root->val); // 后访问当前节点
}
|
多叉树层序遍历（BFS）
层序遍历核心是 “按层级访问节点”，用队列实现，三种写法侧重不同场景。
基础层序遍历（不区分层级，仅收集所有节点值）
逻辑：队列存储节点，出队时访问当前节点，再将所有子节点入队。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| vector<int> levelOrder_basic(Node* root) {
vector<int> res;
if (root == nullptr) return res;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* curr = q.front();
q.pop();
res.push_back(curr->val); // 访问当前节点
// 所有子节点入队（按列表顺序）
for (Node* child : curr->children) {
if (child != nullptr) q.push(child);
}
}
return res;
}
|
层层序遍历（区分每一层，返回二维数组）
逻辑：每次遍历队列中当前层级的所有节点，收集该层值，再入队下一层节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| vector<vector<int>> levelOrder_level(Node* root) {
vector<vector<int>> res;
if (root == nullptr) return res;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size(); // 当前层级的节点数
vector<int> levelVal; // 存储当前层级的所有值
// 遍历当前层级的所有节点
for (int i = 0; i < levelSize; ++i) {
Node* curr = q.front();
q.pop();
levelVal.push_back(curr->val);
// 子节点入队（下一层）
for (Node* child : curr->children) {
if (child != nullptr) q.push(child);
}
}
res.push_back(levelVal); // 加入当前层级结果
}
return res;
}
|
简化版层序遍历（用队列 + 循环简化代码）
逻辑：与写法一一致，简化变量命名和循环结构，更简洁。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<int> levelOrder_simple(Node* root) {
vector<int> res;
queue<Node*> q;
if (root) q.push(root); // 空节点直接返回
while (!q.empty()) {
auto curr = q.front();
q.pop();
res.emplace_back(curr->val); // 简化插入方式
// 子节点入队（省略空判断，假设输入节点的 children 无空指针）
for (auto& child : curr->children) q.push(child);
}
return res;
}
|
多叉树遍历实现
多叉树前序遍历
多叉树递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
void order(Node* root, vector<int>& vec) {
if (root == nullptr) {
return;
}
vec.push_back(root->val);
for (auto child : root->children) {
order(child, vec);
}
}
vector<int> preorder(Node* root) {
vector<int> vec;
order(root, vec);
return vec;
}
};
|
多叉树迭代
栈模拟递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> vec;
if (root == nullptr)
return vec;
stack<Node*> stk;
unordered_map<Node*, int> cnt;
Node* node = root;
while(node != nullptr || !stk.empty()) {
while(node != nullptr) {
vec.push_back(node->val);
stk.push(node);
if (node->children.size() > 0) {
cnt[node] = 0;
node = node->children[0];
} else {
node = nullptr;
}
}
node = stk.top();
int index = (cnt.count(node) ? cnt[node] : -1) + 1;
if (index < node->children.size()) {
cnt[node] = index;
node = node->children[index];
} else {
stk.pop();
cnt.erase(node);
node = nullptr;
}
}
return vec;
}
};
|
迭代优化，利用栈先进后出原理。先 push 右节点，再 push 左节点，这样出栈顺序就是先左后右了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> vec;
if (root == nullptr)
return vec;
stack<Node*> stk;
stk.push(root);
while(!stk.empty()) {
Node* node = stk.top();
stk.pop();
vec.push_back(node->val);
for (auto it = node->children.rbegin(); it != node->children.rend(); it++) {
stk.push(*it);
}
}
return vec;
}
};
|
多叉树后序遍历
多叉树递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
void order(Node* root, vector<int>& vec) {
if (root == nullptr) {
return;
}
for (Node* child : root->children) {
order(child, vec);
}
vec.push_back(root->val);
}
vector<int> postorder(Node* root) {
vector<int> vec;
order(root, vec);
return vec;
}
};
|
多叉树迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> vec;
if (root == nullptr) {
return vec;
}
stack<Node*> stk;
unordered_map<Node*, int> cnt;
Node* node = root;
while(!stk.empty() || node != nullptr) {
while(node != nullptr) {
stk.push(node);
if (node->children.size() > 0) {
cnt[node] = 0;
node = node->children[0];
} else {
node = nullptr;
}
}
node = stk.top();
int index = cnt.count(node) ? cnt[node] + 1 : 0;
if (index < node->children.size()) {
cnt[node] = index;
node = node->children[index];
} else {
vec.push_back(node->val);
stk.pop();
cnt.erase(node);
node = nullptr;
}
}
return vec;
}
};
|
利用栈先进后出思想，不过这里需要使用一个辅助集合来记录已经访问过的节点，否则会重复访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> vec;
if (root == nullptr) {
return vec;
}
stack<Node*> stk;
unordered_set<Node *> visited;
stk.push(root);
while(!stk.empty()) {
Node* node = stk.top();
if (node->children.size() == 0 || visited.count(node)) {
vec.push_back(node->val);
stk.pop();
continue;
}
for (auto it = node->children.rbegin(); it != node->children.rend(); it++) {
stk.push(*it);
}
visited.emplace(node);
}
return vec;
}
};
|
多叉树层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
if (root == nullptr)
return res;
queue<Node*> q;
q.push(root);
while(!q.empty()) {
vector<int> vec;
int sz = q.size();
for (int i = 0; i < sz; i++) {
Node* node = q.front();
q.pop();
vec.push_back(node->val);
for (Node* child : node->children) {
q.push(child);
}
}
res.push_back(vec);
}
return res;
}
};
|
DFS 与 BFS 的适用场景
核心原因：DFS 是“深度优先遍历”，通过“深度探索+回溯”实现“一条路走到头再回溯”，天然适合穷举所有可能路径，且便于记录路径轨迹。
- DFS 的遍历本质：DFS 遵循“先进后出”（LIFO）规则，沿一个分支遍历到叶子节点（无路可走）后，回溯到上一节点继续探索其他分支，能完整覆盖所有可能路径。
- 路径记录的便捷性：DFS 递归过程中，可通过“入栈（记录当前节点）→ 递归子节点 → 出栈（回溯）”的流程，天然维护完整路径。递归到叶子节点即得到一条路径，回溯后移除当前节点再探索其他分支，可收集所有路径。
- BFS 不适合的原因：BFS 按层遍历，节点分散，记录所有路径需为每个节点单独维护路径轨迹，产生大量冗余存储（同一前缀路径重复存储），逻辑复杂；而 DFS 通过回溯复用路径容器，存储开销更小、代码更简洁。
- 典型场景：常用于遍历所有路径。
核心原因：BFS 是“按层遍历”，天然具备“第一次到达目标节点时，路径长度最短”的特性。
- BFS 的遍历本质：BFS 用队列实现，遵循“先进先出”（FIFO）规则。遍历过程中会先访问完“当前层级所有节点”，再进入下一层级，层级顺序严格对应“路径长度”（如根节点为层级 0，直接子节点为层级 1，以此类推）。
- 最短路径的必然性：当 BFS 第一次遍历到目标节点时，该节点所在的“层级”就是从起点到目标的最短路径长度。BFS 不会跳过更短路径提前进入深层级，若存在更短路径，目标节点会在更早层级被访问。
- 与 DFS 的对比：DFS 可能先深入深层级（长路径）找到目标，无法直接确定是否存在更短路径，需遍历所有可能路径后对比，效率极低；而 BFS 找到目标后可直接返回，无需后续遍历。
- 典型场景：常用来寻找最短路径。
二叉搜索树的应用
二叉搜索树是特殊的二叉树结构，其主要的实际应用是 TreeMap 和 TreeSet
特点，即左小右大：
对于树中的每个节点，其左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。
增删改查的时间复杂度也是 O(logN)
TreeMap/TreeSet 实现原理
1
2
3
4
5
6
7
8
9
10
| // 大写 K 为键的类型，大写 V 为值的类型
template <typename K, typename V>
class TreeNode {
public:
K key;
V value;
TreeNode<K, V>* left;
TreeNode<K, V>* right;
TreeNode(K key, V value) : key(key), value(value), left(nullptr), right(nullptr) {}
};
|
核心方法实现逻辑
- 基本增删查改（O (logN) 复杂度）
（1）put (K key, V value)：增 / 改
逻辑：根据 BST 特性遍历树，找到 key 对应的位置（或插入位置）。
若 key 已存在：更新对应节点的 value；
若 key 不存在：创建新节点，作为叶子节点插入（左子树放更小的 key，右子树放更大的 key）。
（2）get (K key)：查
逻辑：从根节点开始遍历，根据 key 大小对比递归 / 迭代查找。
若当前节点 key == 目标 key：返回节点 value；
若目标 key < 当前节点 key：向左子树查找；
若目标 key > 当前节点 key：向右子树查找；
遍历到空节点：返回 null（key 不存在）。
（3）remove (K key)：删
逻辑：先通过 get 逻辑找到目标节点，再根据节点的子树情况处理：
叶子节点（无左右子树）：直接删除（父节点指针置空）；
单子树节点（仅左或仅右子树）：用子节点替代当前节点；
双子树节点：找到当前节点的 “后继节点”（右子树最小节点）或 “前驱节点”（左子树最大节点），替换当前节点后删除原后继 / 前驱节点。
（4）containsKey (K key)：判断键是否存在
逻辑：复用 get 方法的查找逻辑，若找到节点则返回 true，否则返回 false。
- firstKey () /lastKey () 方法（O (logN) 复杂度）
（1）firstKey ()：查找最小键
逻辑：利用 BST “左小右大” 特性，从根节点一直向左子树遍历，直到左子树为空，当前节点的 key 即为最小键。
（2）lastKey ()：查找最大键
逻辑：从根节点一直向右子树遍历，直到右子树为空，当前节点的 key 即为最大键。
- keys () 方法（O (N) 复杂度）
逻辑：对 BST 执行 中序遍历（左子树 → 当前节点 → 右子树），收集所有节点的 key，结果天然按 key 升序排列。
作用：返回有序的键集合，这是 TreeMap 区别于 HashMap 的核心优势（HashMap 键无序）。
- selectKey (int k) /rank (K key) 方法（O (logN) 复杂度）
（1）selectKey (int k)：查找排名为 k 的键（k 从 0 开始，即第 k+1 小的键）
逻辑：需给每个节点维护 “以当前节点为根的子树节点总数”（size），通过 size 递归判断排名：
若左子树 size > k：排名 k 的键在左子树中，递归左子树；
若左子树 size == k：当前节点的 key 即为目标键；
若左子树 size < k：排名 k 的键在右子树中，递归右子树（k 调整为 k - 左子树 size - 1）。
（2）rank (K key)：查找键 key 的排名（即小于 key 的键的个数）
逻辑：遍历树对比 key 大小，统计小于目标 key 的节点数：
若目标 key > 当前节点 key：排名 = 左子树 size + 1 + 右子树中目标 key 的排名；
若目标 key == 当前节点 key：排名 = 左子树 size；
若目标 key < 当前节点 key：排名 = 左子树中目标 key 的排名。
- 性能问题
（1）理想性能
增删查改及 firstKey ()、selectKey () 等方法的时间复杂度均为 O (logN)（N 为节点总数），依赖 BST 是 “平衡树”（左右子树高度差不大），遍历深度为树的高度 logN。
（2）最坏情况性能
若插入的 key 是有序的（如递增或递减），BST 会退化为 “链表”（所有节点只有右子树或左子树），此时树的高度为 O (N)，所有操作的时间复杂度退化为 O (N)，性能极差。
（3）解决方案
实际工程中，TreeMap/TreeSet 的底层并非普通 BST，而是 红黑树（一种自平衡二叉搜索树）。
红黑树通过一系列旋转和着色操作，保证树的高度始终维持在 O (logN)，避免退化为链表，确保最坏情况下仍有 O (logN) 的时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
| #include <iostream>
#include <vector>
#include <algorithm> // 用于 std::max（维护节点高度，可选）
using namespace std;
// 二叉搜索树模板类（K：键类型，需支持比较；V：值类型）
template <typename K, typename V>
class BST {
private:
// 节点结构（包含键值对、左右子树指针、子树节点数）
struct TreeNode {
K key;
V value;
TreeNode* left;
TreeNode* right;
int size; // 以当前节点为根的子树节点总数（用于 select/rank）
// 节点构造函数
TreeNode(K k, V v)
: key(k), value(v), left(nullptr), right(nullptr), size(1) {}
};
TreeNode* root; // BST 根节点
// 辅助函数：获取子树节点数（空节点返回 0）
int getSize(TreeNode* node) {
return node == nullptr ? 0 : node->size;
}
// 辅助函数：更新节点的 size（左子树 size + 右子树 size + 1）
void updateSize(TreeNode* node) {
if (node != nullptr) {
node->size = getSize(node->left) + getSize(node->right) + 1;
}
}
// 【核心】增/改：递归插入节点，已存在则更新值
TreeNode* put(TreeNode* node, K key, V value) {
if (node == nullptr) {
return new TreeNode(key, value); // 新节点插入到叶子位置
}
// 按 BST 特性查找插入位置
if (key < node->key) {
node->left = put(node->left, key, value);
} else if (key > node->key) {
node->right = put(node->right, key, value);
} else {
node->value = value; // key 已存在，更新 value
}
updateSize(node); // 回溯时更新节点 size
return node;
}
// 【核心】查：递归查找 key 对应的节点值
V* get(TreeNode* node, K key) {
if (node == nullptr) {
return nullptr; // key 不存在，返回空指针
}
if (key < node->key) {
return get(node->left, key); // 向左子树查找
} else if (key > node->key) {
return get(node->right, key); // 向右子树查找
} else {
return &(node->value); // 找到 key，返回 value 地址
}
}
// 辅助函数：查找以 node 为根的最小节点（最左子节点）
TreeNode* findMin(TreeNode* node) {
if (node->left == nullptr) {
return node;
}
return findMin(node->left);
}
// 辅助函数：删除以 node 为根的最小节点，返回新的根节点
TreeNode* removeMin(TreeNode* node) {
if (node->left == nullptr) {
TreeNode* rightChild = node->right;
delete node; // 释放当前节点内存
return rightChild;
}
node->left = removeMin(node->left);
updateSize(node); // 回溯时更新 size
return node;
}
// 【核心】删：递归删除节点（处理叶子、单子树、双子树三种情况）
TreeNode* remove(TreeNode* node, K key) {
if (node == nullptr) {
return nullptr; // key 不存在，无需删除
}
// 第一步：找到目标节点
if (key < node->key) {
node->left = remove(node->left, key);
} else if (key > node->key) {
node->right = remove(node->right, key);
} else {
// 第二步：处理目标节点的删除
if (node->left == nullptr) { // 左子树为空，用右子树替代
TreeNode* rightChild = node->right;
delete node;
return rightChild;
}
if (node->right == nullptr) { // 右子树为空，用左子树替代
TreeNode* leftChild = node->left;
delete node;
return leftChild;
}
// 双子树节点：用「后继节点」（右子树最小节点）替代当前节点
TreeNode* successor = findMin(node->right);
// 复制后继节点的键值到当前节点
node->key = successor->key;
node->value = successor->value;
// 删除原后继节点
node->right = removeMin(node->right);
}
updateSize(node); // 回溯时更新 size
return node;
}
// 【核心】keys()：中序遍历收集所有键（天然升序）
void inorder(TreeNode* node, vector<K>& keyList) {
if (node == nullptr) {
return;
}
inorder(node->left, keyList); // 遍历左子树
keyList.push_back(node->key); // 访问当前节点
inorder(node->right, keyList); // 遍历右子树
}
// 【核心】selectKey：查找排名为 k 的键（k 从 0 开始，即第 k+1 小）
TreeNode* select(TreeNode* node, int k) {
if (node == nullptr) {
return nullptr; // 排名超出范围
}
int leftSize = getSize(node->left); // 左子树节点数（小于当前节点的键数）
if (leftSize > k) {
return select(node->left, k); // 排名在左子树
} else if (leftSize == k) {
return node; // 当前节点即为排名 k 的键
} else {
// 排名在右子树，k 调整为 k - 左子树大小 - 1
return select(node->right, k - leftSize - 1);
}
}
// 【核心】rank：查找 key 的排名（小于 key 的键的个数）
int rank(TreeNode* node, K key) {
if (node == nullptr) {
return 0; // key 不存在，返回 0
}
if (key < node->key) {
return rank(node->left, key); // key 在左子树，排名为左子树中的排名
} else if (key > node->key) {
// key 在右子树，排名 = 左子树大小 + 1（当前节点） + 右子树中的排名
return getSize(node->left) + 1 + rank(node->right, key);
} else {
return getSize(node->left); // key 存在，排名 = 左子树大小
}
}
// 辅助函数：递归释放所有节点内存（避免内存泄漏）
void destroy(TreeNode* node) {
if (node == nullptr) {
return;
}
destroy(node->left);
destroy(node->right);
delete node;
}
public:
// BST 构造函数（初始化空树）
BST() : root(nullptr) {}
// BST 析构函数（释放所有节点内存）
~BST() {
destroy(root);
}
// 对外接口：增/改
void put(K key, V value) {
root = put(root, key, value);
}
// 对外接口：查（返回 value 引用，不存在则抛出异常）
V& get(K key) {
V* valPtr = get(root, key);
if (valPtr == nullptr) {
throw runtime_error("Key not found");
}
return *valPtr;
}
// 对外接口：删
void remove(K key) {
root = remove(root, key);
}
// 对外接口：判断 key 是否存在
bool containsKey(K key) {
return get(root, key) != nullptr;
}
// 对外接口：firstKey（最小键）
K firstKey() {
if (root == nullptr) {
throw runtime_error("BST is empty");
}
return findMin(root)->key;
}
// 对外接口：lastKey（最大键）
K lastKey() {
if (root == nullptr) {
throw runtime_error("BST is empty");
}
TreeNode* curr = root;
// 一直向右子树遍历，直到右子树为空
while (curr->right != nullptr) {
curr = curr->right;
}
return curr->key;
}
// 对外接口：keys（返回升序键集合）
vector<K> keys() {
vector<K> keyList;
inorder(root, keyList);
return keyList;
}
// 对外接口：selectKey（查找排名为 k 的键）
K selectKey(int k) {
TreeNode* target = select(root, k);
if (target == nullptr) {
throw runtime_error("Rank out of range");
}
return target->key;
}
// 对外接口：rank（查找 key 的排名）
int rank(K key) {
return rank(root, key);
}
// 对外接口：获取树的总节点数
int size() {
return getSize(root);
}
};
// 测试代码（验证核心功能）
int main() {
BST<int, string> bst;
// 1. 增/改
bst.put(3, "A");
bst.put(1, "B");
bst.put(4, "C");
bst.put(2, "D");
bst.put(3, "A+"); // 更新 key=3 的值
// 2. 查
cout << "get(3): " << bst.get(3) << endl; // 输出 A+
cout << "containsKey(2): " << (bst.containsKey(2) ? "true" : "false") << endl; // true
// 3. firstKey/lastKey
cout << "firstKey: " << bst.firstKey() << endl; // 1
cout << "lastKey: " << bst.lastKey() << endl; // 4
// 4. keys（升序输出）
vector<int> keyList = bst.keys();
cout << "keys: ";
for (int key : keyList) cout << key << " "; // 输出 1 2 3 4
cout << endl;
// 5. selectKey/rank
cout << "selectKey(2): " << bst.selectKey(2) << endl; // 排名 2（第 3 小）的键是 3
cout << "rank(4): " << bst.rank(4) << endl; // 小于 4 的键有 3 个，排名为 3
// 6. 删
bst.remove(2);
cout << "after remove(2), keys: ";
keyList = bst.keys();
for (int key : keyList) cout << key << " "; // 输出 1 3 4
cout << endl;
return 0;
}
|
- BST的优势：操作效率取决于树高。树越平衡，树高就越接近 log N，效率就越高。
- BST的致命缺陷：它不会自动对树进行平衡。在特殊情况下（例如插入有序序列），BST会退化成一个链表。
- 后果：增删查改的时间复杂度从 O(log N) 退化为 O(N)。
红黑树
红黑树是一种自平衡的二叉搜索树，它的每个节点都有一个颜色属性，颜色只能是红色或黑色。
红黑树的高度是 O(logN)，这使得它在增删节点时的时间复杂度也是 O(logN)
红黑树的解决方案：引入“颜色”属性
为了解决BST不平衡的问题，我们需要一种能在插入和删除后自动调整结构以维持平衡的BST。红黑树就是其中最著名、应用最广泛的实现之一（例如 Java 的 TreeMap 和 C++ 的 std::map 底层都使用了红黑树）。
红黑树通过给每个节点增加一个存储颜色（红色或黑色）的属性，并强制遵守一套严格的规则（红黑性质），来确保树的近似平衡。
红黑树的红黑性质
- 每个节点要么是红，要么是黑
- 根节点是黑
- 每个叶子节点（NIL）是黑
- 如果一个节点是红的，则它的两个子节点都是黑的（即不能有两个连续的红色节点）
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（即黑色完美平衡）
第4条和第5条，从根本上限制了树的最大高度，使其不可能退化成链表。
为什么能保证 O(log N) 的高度？
性质5（黑色完美平衡）保证了从根到任何叶子的路径上，黑色节点的数量是固定的，设为 B。
性质4（无连续红节点）保证了任何路径上的红色节点数量不会超过黑色节点数量。
因此，任何路径的总长度（树高）最多为 2B。
同时，一棵只有黑色节点的完美二叉树（高度为 B）至少包含 2^B - 1 个内部节点。
设总节点数为 N，则有 N >= 2^B - 1，推导出 B <= log(N+1)。
最终，树高 h <= 2B <= 2 * log(N+1) = O(log N)。
核心操作：旋转与变色
为了在插入和删除后依然能维持上述五条性质，红黑树定义了一系列复杂的调整操作，主要包括两种基本操作：
Trie 树
Trie 树（前缀树）是一种用于高效存储和检索字符串数据的数据结构。一种针对字符串有特殊优化的数据结构。
主要应用场景
- Trie 树就能节约大量的内存空间。（Trie 树底层并不会重复存储公共前缀）
- 方便处理前缀操作（最长、最短前缀，判断前缀是否存在等操作，这些操作的时间复杂度通常为 O(L)，其中 L 是前缀或查询字符串的长度，与总键的数量无关。这使得 Trie 树非常适合用于自动补全（Auto-completion）和输入提示功能。）
- 可以使用通配符（这种能力源于 Trie 树可以沿着多条路径同时进行深度优先搜索（DFS））
- 可以按照字典序遍历键
Trie 树的基本结构
Trie 树本质上是一棵多叉树（N-ary Tree），其设计完全围绕字符串的字符序列展开。
- 节点 (Node):
- 每个节点代表一个字符。
- 节点本身不直接存储完整的字符串，字符串是由从根节点到该节点的路径所隐含定义的。
- 节点通常包含两个关键属性：
- val: 如果该节点是一个完整单词的结尾，则在此处存储对应的值（对于 TrieSet，这个值可能只是一个标记）。
- children: 一个大小为 R 的数组（R 是字符集的大小，如 ASCII 为 128，小写字母为 26），用于指向下一个可能出现的字符所对应的子节点。
- 根节点 (Root):
- 根节点是空的，不代表任何字符。
- 它是所有字符串的起点。
- 路径即键:
- 一个键（字符串）的存在与否，取决于从根节点出发，能否沿着该字符串的每个字符找到一条连续的路径，并且路径的终点节点的 val 字段不为空。
TrieMap
TrieMap 是基于 Trie 树实现的映射（Map）数据结构，其键（Key）类型固定为 String，值（Value）类型是泛型。
线段树
线段树是二叉树结构的衍生，用于高效解决数组的区间查询和区间动态修改问题。
线段树可以在 O(logN) 的时间复杂度查询任意长度的区间元素聚合值，在 O(logN) 的时间复杂度对任意长度的区间元素进行动态修改，其中 N 为数组中的元素个数。
使用场景
线段树主要用于高效解决数组的区间查询和区间动态修改问题，特别适用于以下场景：
- 区间求和/最值查询：快速计算数组任意区间
[i, j] 的元素和、最大值、最小值等 - 动态数组更新：在频繁修改数组元素的同时，仍能保持高效的区间查询性能
- 大数据量处理：当数组规模很大（如
N = 10^5 或更大）且查询/更新操作频繁时 - 离线算法优化：作为其他复杂算法（如扫描线算法）的基础数据结构
典型例子：股票价格分析系统需要频繁查询某段时间内的最高价、最低价、平均价，同时价格数据会实时更新。
线段树的核心 API
线段树通常提供以下核心接口：
query(int l, int r)：查询区间 [l, r] 的聚合值（如和、最值等）update(int index, int val)：将数组中索引 index 处的值更新为 valbuild(vector<int>& nums)：根据初始数组构建线段树
线段树的核心原理
线段树本质上是一棵二叉树，其设计思想是分治 + 预处理：
- 叶子节点：对应原数组中的每个元素
- 非叶子节点：存储其对应区间的聚合信息（如区间和、区间最值等）
- 区间划分：每个非叶子节点将其管理的区间平均分成两半，分别由左右子节点管理
- 信息聚合：父节点的信息由左右子节点的信息聚合而成
关键洞察：线段树通过预处理将区间查询的时间复杂度从 O(N) 降低到 O(log N)，代价是 O(N) 的额外空间和 O(N) 的预处理时间。
树高为什么是 O(log N)
线段树是基于完全二叉树构建的：
- 叶子节点数量：等于原数组长度 N
- 完全二叉树性质：高度为 h 的完全二叉树最多有
2^h - 1 个节点 - 推导过程：
- 叶子节点数 N ≤
2^h - 两边取对数：
log₂N ≤ h - 因此树高 h = O(log N)
实际上，为了保证完全二叉树结构，线段树通常会将数组长度扩展到大于等于 N 的最小 2 的幂次。
query 为什么是 O(log N)
区间查询操作的时间复杂度分析：
- 递归深度：最多遍历树的高度，即 O(log N)
- 每层访问节点数：在任何一层，最多访问 2 个节点
- 这是因为查询区间要么完全包含某个节点的区间，要么与其部分重叠
- 部分重叠的情况最多在左右边界各出现一次
- 总时间复杂度：O(2 × log N) = O(log N)
update 为什么是 O(log N)
单点更新操作的时间复杂度分析：
- 定位叶子节点：从根节点到对应叶子节点的路径长度为 O(log N)
- 更新路径：只需要更新从叶子节点到根节点路径上的所有祖先节点
- 每个节点更新：O(1) 时间（直接聚合左右子节点信息）
- 总时间复杂度：O(log N)
C++ 代码实现
基础线段树实现（区间求和）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| #include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
class SegmentTree {
private:
std::vector<int> tree; // 线段树数组
int n; // 原数组长度
// 构建线段树
void build(const std::vector<int>& nums, int node, int start, int end) {
if (start == end) {
// 叶子节点
tree[node] = nums[start];
} else {
int mid = (start + end) / 2;
// 递归构建左右子树
build(nums, 2 * node + 1, start, mid);
build(nums, 2 * node + 2, mid + 1, end);
// 聚合子节点信息
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
// 更新操作
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
// 找到要更新的叶子节点
tree[node] = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
// 在左子树中更新
update(2 * node + 1, start, mid, idx, val);
} else {
// 在右子树中更新
update(2 * node + 2, mid + 1, end, idx, val);
}
// 更新当前节点的值
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
// 查询操作
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
// 区间完全不重叠，返回0（求和的单位元）
return 0;
}
if (l <= start && end <= r) {
// 区间完全包含，直接返回节点值
return tree[node];
}
// 区间部分重叠，递归查询左右子树
int mid = (start + end) / 2;
int left_sum = query(2 * node + 1, start, mid, l, r);
int right_sum = query(2 * node + 2, mid + 1, end, l, r);
return left_sum + right_sum;
}
public:
// 构造函数
SegmentTree(const std::vector<int>& nums) {
n = nums.size();
if (n == 0) return;
// 线段树数组大小：4 * n 是安全的上界
tree.resize(4 * n);
build(nums, 0, 0, n - 1);
}
// 更新接口
void update(int index, int val) {
update(0, 0, n - 1, index, val);
}
// 查询接口
int query(int l, int r) {
return query(0, 0, n - 1, l, r);
}
};
int main() {
std::vector<int> nums = {1, 3, 5, 7, 9, 11};
SegmentTree st(nums);
// 查询区间 [1, 3] 的和：3 + 5 + 7 = 15
std::cout << "Query [1,3]: " << st.query(1, 3) << std::endl;
// 更新索引 1 的值为 10
st.update(1, 10);
// 再次查询区间 [1, 3] 的和：10 + 5 + 7 = 22
std::cout << "Query [1,3] after update: " << st.query(1, 3) << std::endl;
// 查询整个数组的和
std::cout << "Total sum: " << st.query(0, nums.size() - 1) << std::endl;
return 0;
}
|
扩展：支持区间最值查询的线段树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
#include <cassert>
class MaxSegmentTree {
private:
std::vector<int> tree;
int n;
void build(const std::vector<int>& nums, int node, int start, int end) {
if (start == end) {
tree[node] = nums[start];
} else {
int mid = (start + end) / 2;
build(nums, 2 * node + 1, start, mid);
build(nums, 2 * node + 2, mid + 1, end);
tree[node] = std::max(tree[2 * node + 1], tree[2 * node + 2]);
}
}
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
update(2 * node + 1, start, mid, idx, val);
} else {
update(2 * node + 2, mid + 1, end, idx, val);
}
tree[node] = std::max(tree[2 * node + 1], tree[2 * node + 2]);
}
}
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
return INT_MIN; // 最大值查询的单位元
}
if (l <= start && end <= r) {
return tree[node];
}
int mid = (start + end) / 2;
int left_max = query(2 * node + 1, start, mid, l, r);
int right_max = query(2 * node + 2, mid + 1, end, l, r);
return std::max(left_max, right_max);
}
public:
MaxSegmentTree(const std::vector<int>& nums) {
n = nums.size();
if (n == 0) return;
tree.resize(4 * n, INT_MIN);
build(nums, 0, 0, n - 1);
}
void update(int index, int val) {
update(0, 0, n - 1, index, val);
}
int query(int l, int r) {
return query(0, 0, n - 1, l, r);
}
};
int main() {
std::cout << "Testing MaxSegmentTree..." << std::endl;
std::vector<int> nums = {1, 3, 5, 7, 9, 11};
MaxSegmentTree st(nums);
// Test 1: Initial range query
// Range [1, 3] corresponds to {3, 5, 7}, max is 7
int max_val = st.query(1, 3);
std::cout << "Query [1, 3] (expected 7): " << max_val << std::endl;
assert(max_val == 7);
// Test 2: Update and query
// Update index 1 to 10. Array: {1, 10, 5, 7, 9, 11}
st.update(1, 10);
// Range [1, 3] corresponds to {10, 5, 7}, max is 10
max_val = st.query(1, 3);
std::cout << "Query [1, 3] after update (expected 10): " << max_val << std::endl;
assert(max_val == 10);
// Test 3: Full range query
// Range [0, 5] corresponds to {1, 10, 5, 7, 9, 11}, max is 11
max_val = st.query(0, 5);
std::cout << "Query [0, 5] (expected 11): " << max_val << std::endl;
assert(max_val == 11);
// Test 4: Update to new max
// Update index 4 to 20. Array: {1, 10, 5, 7, 20, 11}
st.update(4, 20);
max_val = st.query(0, 5);
std::cout << "Query [0, 5] after update (expected 20): " << max_val << std::endl;
assert(max_val == 20);
// Test 5: Single element query
max_val = st.query(2, 2);
std::cout << "Query [2, 2] (expected 5): " << max_val << std::endl;
assert(max_val == 5);
std::cout << "All tests passed!" << std::endl;
return 0;
}
|
关键特性总结
时间复杂度：
- 构建：O(N)
- 查询：O(log N)
- 更新：O(log N)
空间复杂度：O(N)
适用性：适用于满足结合律的聚合操作（如求和、最值、按位与/或等）
局限性：
- 基础版本只支持单点更新
- 对于区间更新操作，需要使用懒标记（Lazy Propagation）技术优化
线段树是处理区间查询问题的强大工具。
霍夫曼树与霍夫曼编码
使用场景
霍夫曼编码是一种通用无损数据压缩算法，主要应用于：
- 文件压缩：ZIP、GZIP 等压缩格式的核心算法之一
- 网络传输：减少数据传输量，提高传输效率
- 存储优化：在磁盘或内存中更高效地存储重复性高的数据
- 多媒体编码：作为 JPEG、MP3 等有损压缩算法的组成部分（用于无损部分）
核心价值：通过利用数据中字符出现频率的不均匀性，用更短的编码表示高频字符，用较长的编码表示低频字符，从而实现整体压缩。
浅谈数据压缩
数据压缩算法分为两大类：
无损压缩
- 特点：压缩后的数据可以完全还原，不会丢失任何信息
- 原理：本质是编码和解码，通过挖掘数据中的冗余信息进行压缩
- 例子：ZIP 压缩包、霍夫曼编码
- 关键：压缩效果取决于算法挖掘冗余信息的能力
有损压缩
- 特点：压缩后会丢失部分信息，但压缩率更高
- 原理：利用人类感知的局限性（如人眼对亮度敏感、对色度不敏感）
- 例子：JPEG 图片压缩、MP3 音频压缩
- 权衡：在可接受的质量损失范围内换取更高的压缩率
重要结论：没有全能的压缩算法，需要在通用性、压缩率和性能之间进行权衡。
定长编码 vs 变长编码
定长编码（Fixed-length Encoding）
- 原理：每个字符使用相同长度的二进制编码
- 例子：ASCII 编码（8位/字符）、简化版（如3种字符用2位编码）
- 优点：实现简单，支持随机访问
- 缺点：压缩效果差，未利用字符频率信息
示例：字符串 "aaabacc"（7个字符）
- ASCII 编码：7 × 8 = 56 bit
- 自定义定长编码（a=00, b=01, c=10）：7 × 2 = 14 bit
变长编码（Variable-length Encoding）
- 原理：高频字符用短编码，低频字符用长编码
- 例子：UTF-8 编码、霍夫曼编码
- 优点：压缩效率高，充分利用频率信息
- 缺点：不支持随机访问，解码复杂度高
示例：字符串 "aaabacc"
- 变长编码（a=0, b=10, c=11）：编码为
0001001111，共 11 bit - 比定长编码（14 bit）更节省空间
变长编码的难点
核心挑战
- 解码唯一性：如何确保编码方案能够被唯一解码？
- 压缩率优化：如何设计编码使总长度最短？
- 解码效率：如何保证高效的解码速度？
关键洞察：前缀码（Prefix Code）
- 问题根源：如果一个编码是另一个编码的前缀，就会产生歧义
- 错误示例：a=1, b=10, c=11 → “11” 可解码为 “c” 或 “aa”
- 解决方案：确保任意编码都不是其他编码的前缀
- 正确示例：a=0, b=10, c=11 → 无前缀冲突
前缀码的优势
- 唯一可解码：从左到右扫描即可唯一确定每个字符
- 高效解码：时间复杂度 O(N)，无需回溯或试探
- 天然对应二叉树：前缀码可以用二叉树表示，叶子节点对应字符编码
霍夫曼编码原理
霍夫曼编码是一种贪心算法，用于构建最优前缀码：
构建过程
- 统计频率：计算每个字符在数据中出现的频率
- 初始化：将每个字符视为一个独立的树（节点），权重为频率
- 合并操作：重复以下步骤直到只剩一棵树：
- 选择两个权重最小的树
- 创建新节点作为它们的父节点，权重为两者之和
- 将新树放回集合中
- 生成编码：从根节点到每个叶子节点的路径即为该字符的编码（左0右1或相反）
最优性证明
- 贪心选择性质：频率最低的两个字符在最优编码中必定具有相同的最大长度，且仅最后一位不同
- 最优子结构：合并后的子问题仍保持最优性
霍夫曼树特性
- 带权路径长度最小：∑(字符频率 × 编码长度) 最小
- 完全二叉树：只有度为0（叶子）和度为2（内部节点）的节点
- 前缀码保证：叶子节点对应字符，自然满足前缀码条件
C++ 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
| #include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>
#include <functional>
struct HuffmanNode {
char ch; // 字符
int freq; // 频率
HuffmanNode* left; // 左子节点
HuffmanNode* right; // 右子节点
HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
// 用于优先队列的比较（最小堆）
bool operator>(const HuffmanNode& other) const {
return freq > other.freq;
}
};
class HuffmanCoding {
private:
HuffmanNode* root;
std::unordered_map<char, std::string> codes;
std::unordered_map<char, int> freqMap;
// 统计字符频率
void buildFrequencyMap(const std::string& text) {
freqMap.clear();
for (char c : text) {
freqMap[c]++;
}
}
// 构建霍夫曼树
HuffmanNode* buildHuffmanTree() {
if (freqMap.empty()) return nullptr;
// 最小堆（优先队列）
std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>,
std::function<bool(HuffmanNode*, HuffmanNode*)>> pq(
[](HuffmanNode* a, HuffmanNode* b) { return a->freq > b->freq; }
);
// 将所有字符加入优先队列
for (const auto& pair : freqMap) {
pq.push(new HuffmanNode(pair.first, pair.second));
}
// 合并节点直到只剩一个根节点
while (pq.size() > 1) {
HuffmanNode* left = pq.top(); pq.pop();
HuffmanNode* right = pq.top(); pq.pop();
HuffmanNode* merged = new HuffmanNode('\0', left->freq + right->freq);
merged->left = left;
merged->right = right;
pq.push(merged);
}
return pq.top();
}
// 生成霍夫曼编码
void generateCodes(HuffmanNode* node, const std::string& code) {
if (!node) return;
if (node->ch != '\0') {
// 叶子节点，存储编码
codes[node->ch] = code;
} else {
// 内部节点，递归生成左右子树编码
generateCodes(node->left, code + "0");
generateCodes(node->right, code + "1");
}
}
// 释放霍夫曼树内存
void deleteTree(HuffmanNode* node) {
if (!node) return;
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
public:
HuffmanCoding() : root(nullptr) {}
~HuffmanCoding() {
deleteTree(root);
}
// 构建霍夫曼编码表
void build(const std::string& text) {
if (text.empty()) return;
buildFrequencyMap(text);
root = buildHuffmanTree();
codes.clear();
generateCodes(root, "");
}
// 编码文本
std::string encode(const std::string& text) {
std::string encoded;
for (char c : text) {
encoded += codes[c];
}
return encoded;
}
// 解码二进制字符串
std::string decode(const std::string& encoded) {
if (!root) return "";
std::string decoded;
HuffmanNode* current = root;
for (char bit : encoded) {
if (bit == '0') {
current = current->left;
} else {
current = current->right;
}
// 到达叶子节点
if (current->ch != '\0') {
decoded += current->ch;
current = root; // 重置到根节点
}
}
return decoded;
}
// 打印编码表
void printCodes() const {
for (const auto& pair : codes) {
std::cout << "'" << pair.first << "': " << pair.second << std::endl;
}
}
// 获取压缩率信息
void printCompressionInfo(const std::string& original) const {
if (original.empty()) return;
size_t originalBits = original.length() * 8;
size_t compressedBits = 0;
for (char c : original) {
compressedBits += codes.at(c).length();
}
double compressionRatio = (double)compressedBits / originalBits;
std::cout << "Original size: " << originalBits << " bits" << std::endl;
std::cout << "Compressed size: " << compressedBits << " bits" << std::endl;
std::cout << "Compression ratio: " << compressionRatio * 100 << "%" << std::endl;
}
};
int main() {
std::string text = "aaabacc";
std::cout << "Original text: " << text << std::endl;
HuffmanCoding huffman;
huffman.build(text);
std::cout << "\nHuffman codes:" << std::endl;
huffman.printCodes();
std::string encoded = huffman.encode(text);
std::cout << "\nEncoded: " << encoded << std::endl;
std::string decoded = huffman.decode(encoded);
std::cout << "Decoded: " << decoded << std::endl;
std::cout << "\nCompression info:" << std::endl;
huffman.printCompressionInfo(text);
return 0;
}
|
关键特性总结
- 最优性：霍夫曼编码产生的前缀码具有最小的期望编码长度
- 无损压缩：可以完全还原原始数据
- 自适应性：编码表基于输入数据的字符频率动态生成
- 时间复杂度：
- 构建：O(n log n)，其中 n 是不同字符的数量
- 编码/解码：O(m)，其中 m 是文本长度
- 空间复杂度：O(n) 存储霍夫曼树和编码表
霍夫曼编码是数据压缩领域的经典算法，完美体现了贪心策略在实际问题中的应用价值。
Reference
https://labuladong.online/algo/data-structure-basic/binary-tree-basic/
https://labuladong.online/algo/data-structure-basic/binary-tree-traverse-basic/
https://labuladong.online/algo/data-structure-basic/n-ary-tree-traverse-basic
https://leetcode.cn/problems/n-ary-tree-preorder-traversal/
https://labuladong.online/algo/data-structure-basic/tree-map-basic/