C++ 常用数据结构详解 —— 表、树与图

数据结构是算法的基础。本文浅析 C++ 中常用的线性表、树形结构和图结构，涵盖原理、实现要点、复杂度分析与 STL 使用技巧。

---

目录

章节	内容
一	数据结构总览
二	线性表
三	哈希表
四	二叉搜索树 (BST)
五	平衡二叉树 (AVL)
六	红黑树 (Red-Black Tree)
七	B 树 / B+ 树
八	堆 (Heap)
九	字典树 (Trie)
十	线段树 (Segment Tree)
十一	树状数组 (Fenwick Tree)
十二	并查集 (Union-Find)
十三	哈夫曼树 (Huffman Tree)
十四	图的基础与遍历
十五	对比速查表
十六	如何选择合适的数据结构

---

一、数据结构总览

---

二、线性表

2.1 数组 vs 链表

特性	vector (动态数组)	list (双向链表)
内存布局	连续内存	分散节点
随机访问	O(1)	O(n)
头插/头删	O(n)	O(1)
尾插/尾删	O(1) 均摊	O(1)
中间插入/删除	O(n)	O(1)（已有迭代器）
缓存友好度	高	低
迭代器失效	扩容时全部失效	永不失效（除被删节点）

2.2 栈与队列

#include <stack>
#include <queue>

// 栈：后进先出 LIFO
stack<int> st;
st.push(1); st.push(2); st.push(3);
int top = st.top();  // 3
st.pop();            // 删除 3

// 队列：先进先出 FIFO
queue<int> q;
q.push(1); q.push(2); q.push(3);
int front = q.front();  // 1
q.pop();                // 删除 1

// 双端队列：两端都可操作
deque<int> dq;
dq.push_front(0); dq.push_back(1);
dq.pop_front();  dq.pop_back();

2.3 优先队列（堆实现）

// 大顶堆（默认）：最大值在队首
priority_queue<int> maxHeap;
maxHeap.push(3); maxHeap.push(1); maxHeap.push(5);
int top = maxHeap.top();  // 5

// 小顶堆：最小值在队首
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(3); minHeap.push(1); minHeap.push(5);
top = minHeap.top();  // 1

// 自定义比较器
auto cmp = [](pair<int,int> a, pair<int,int> b) { return a.second > b.second; };
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);

操作	时间复杂度
push()	O(log n)
pop()	O(log n)
top()	O(1)

---

三、哈希表

3.1 原理

哈希表通过哈希函数将键映射到数组索引，实现近似 O(1) 的查找。

3.2 冲突解决方法

方法	描述	优点	缺点
链地址法	每个桶存一个链表	实现简单	极端情况退化为链表 O(n)
开放寻址法	冲突时找下一个空位	缓存友好	删除操作复杂（需要逻辑删除标记，否则会中断探测链）以及容易产生聚集（Clustering）现象

C++ STL 的 unordered_map 使用链地址法。

3.3 C++ 中的使用

#include <unordered_map>
#include <unordered_set>

unordered_map<string, int> umap;
umap["apple"] = 5;
umap["banana"] = 3;

// 查找
if (umap.find("apple") != umap.end()) {
    cout << umap["apple"] << endl;
}

// 遍历
for (auto& [key, value] : umap) {  // C++17 结构化绑定
    cout << key << ": " << value << endl;
}

unordered_set<int> uset;
uset.insert(1); uset.insert(2); uset.insert(3);
if (uset.count(2)) { /* 存在 */ }

容器	底层实现	时间复杂度
unordered_map	哈希表	O(1) 平均，O(n) 最坏
unordered_set	哈希表	O(1) 平均，O(n) 最坏
map	红黑树	O(log n)
set	红黑树	O(log n)

---

四、二叉搜索树（BST）

4.1 定义

二叉搜索树满足：对于任意节点，左子树所有节点值 < 根节点值 < 右子树所有节点值。

4.2 C++ 实现

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BST {
public:
    // 查找：O(h)，h 为树高
    TreeNode* search(TreeNode* root, int key) {
        if (!root || root->val == key) return root;
        if (key < root->val)
            return search(root->left, key);
        else
            return search(root->right, key);
    }

    // 插入：O(h)
    TreeNode* insert(TreeNode* root, int key) {
        if (!root) return new TreeNode(key);
        if (key < root->val)
            root->left = insert(root->left, key);
        else if (key > root->val)
            root->right = insert(root->right, key);
        return root;
    }

    // 删除：O(h)，三种情况
    TreeNode* remove(TreeNode* root, int key) {
        if (!root) return nullptr;
        if (key < root->val) {
            root->left = remove(root->left, key);
        } else if (key > root->val) {
            root->right = remove(root->right, key);
        } else {
            // 情况 1：叶子节点
            if (!root->left && !root->right) {
                delete root;
                return nullptr;
            }
            // 情况 2：只有一个子节点
            if (!root->left) {
                TreeNode* tmp = root->right;
                delete root;
                return tmp;
            }
            if (!root->right) {
                TreeNode* tmp = root->left;
                delete root;
                return tmp;
            }
            // 情况 3：有两个子节点，用后继节点替换
            TreeNode* successor = findMin(root->right);
            root->val = successor->val;
            root->right = remove(root->right, successor->val);
        }
        return root;
    }

private:
    TreeNode* findMin(TreeNode* node) {
        while (node->left) node = node->left;
        return node;
    }
};

4.3 BST 的问题：退化

当插入顺序为升序或降序时，BST 退化为链表，复杂度从 O(log n) 变成 O(n)。

为了解决退化问题，出现了平衡二叉树（AVL）和红黑树。

---

五、平衡二叉树（AVL 树）

5.1 定义

AVL 树是最早发明的自平衡二叉搜索树。任意节点的左右子树高度差（平衡因子）的绝对值不超过 1。

平衡因子 = 左子树高度 - 右子树高度 ∈ {-1, 0, 1}

5.2 四种旋转操作

当插入/删除导致失衡时，通过旋转恢复平衡。

失衡类型	条件	操作
LL（左左）	左子树的左子树插入	右旋 根节点
RR（右右）	右子树的右子树插入	左旋 根节点
LR（左右）	左子树的右子树插入	先左旋左子，再右旋根
RL（右左）	右子树的左子树插入	先右旋右子，再左旋根

5.3 C++ 实现核心

struct AVLNode {
    int val;
    int height;  // 节点高度
    AVLNode* left;
    AVLNode* right;
    AVLNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {}
};

int getHeight(AVLNode* node) {
    return node ? node->height : 0;
}

int getBalance(AVLNode* node) {
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

void updateHeight(AVLNode* node) {
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
}

// 右旋
AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;
    // 旋转
    x->right = y;
    y->left = T2;
    // 更新高度
    updateHeight(y);
    updateHeight(x);
    return x;  // 新的根
}

// 左旋
AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;
    y->left = x;
    x->right = T2;
    updateHeight(x);
    updateHeight(y);
    return y;
}

// 插入（递归，带自动平衡）
AVLNode* insert(AVLNode* node, int key) {
    // 1. 普通 BST 插入
    if (!node) return new AVLNode(key);
    if (key < node->val)
        node->left = insert(node->left, key);
    else if (key > node->val)
        node->right = insert(node->right, key);
    else
        return node;  // 重复键

    // 2. 更新高度
    updateHeight(node);

    // 3. 检查平衡并旋转
    int balance = getBalance(node);

    // LL：左子树的左边插入
    if (balance > 1 && key < node->left->val)
        return rightRotate(node);
    // RR：右子树的右边插入
    if (balance < -1 && key > node->right->val)
        return leftRotate(node);
    // LR：左子树的右边插入
    if (balance > 1 && key > node->left->val) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    // RL：右子树的左边插入
    if (balance < -1 && key < node->right->val) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

5.4 AVL 树特点

特性	说明
时间复杂度	查找/插入/删除均为 O(log n)
平衡条件	严格平衡（高度差 ≤ 1）
适用场景	查找密集型，插入删除相对少
优点	严格平衡，查找效率最高
缺点	插入删除需要频繁旋转，开销较大

---

六、红黑树（Red-Black Tree）

6.1 定义

红黑树是一种弱平衡的二叉搜索树，通过颜色约束和更少的旋转保证 O(log n) 复杂度。C++ STL 的 map/set 底层就是红黑树。

6.2 五条性质

#	性质	含义
1	每个节点是红色或黑色	基本属性
2	根节点是黑色	保证至少有一个黑节点
3	每个叶节点（NIL）是黑色	简化边界处理
4	红色节点的子节点必须是黑色	不能有两个连续的红节点
5	从任一节点到其所有后代叶节点的路径包含相同数量的黑节点	黑高相同（核心约束）

性质 4+5 保证：最长路径 ≤ 2 × 最短路径（最长：红黑交替，最短：全黑）

6.3 插入修复

插入节点默认为红色，然后修复违规。

6.4 C++ 中红黑树的使用（std::map）

#include <map>
#include <set>

// map：键值对，按键排序
map<int, string> mp;
mp[3] = "three";
mp[1] = "one";
mp[2] = "two";
// 自动排序：1, 2, 3
for (auto& [k, v] : mp) {
    cout << k << ": " << v << endl;
}

// 自定义比较器（降序）
map<int, string, greater<int>> mpDesc;

// set：唯一元素，自动排序
set<int> s = {3, 1, 4, 1, 5, 9};  // {1, 3, 4, 5, 9}

// 常用操作
auto it = mp.find(2);           // O(log n)
mp.lower_bound(2);              // 第一个 >= 2 的元素
mp.upper_bound(2);              // 第一个 > 2 的元素
mp.erase(2);                    // O(log n)

6.5 AVL vs 红黑树 对比

维度	AVL 树	红黑树
平衡条件	严格（高度差 ≤ 1）	宽松（最长 ≤ 2×最短）
查找性能	更快（树更矮）	稍慢
插入删除	旋转次数多	旋转次数少（≤ 3 次）
适用场景	查找 >> 修改	频繁插入删除
STL 实现	—	map, set, multimap, multiset
实际应用	数据库索引（少量场景）	广泛（Linux 内核、Java TreeMap、STL）

---

七、B 树 / B+ 树

7.1 为什么需要 B 树？

磁盘 I/O 非常慢（ms 级），B 树通过多路搜索、矮胖结构减少 I/O 次数——每个节点存储多个键，使树的高度极低。

7.2 B 树定义（m 阶）

属性	要求
非根节点关键字数	$\lceil m/2\rceil -1\le keys\le m-1$
非根节点子节点数	$\lceil m/2\rceil \le children\le m$
所有叶节点在同一层	绝对平衡

以 3 阶 B 树（2-3 树）为例最易理解。

7.3 B 树操作要点

插入：

1. 找到对应叶节点
2. 若叶节点未满（keys < m-1），直接插入
3. 若叶节点已满，分裂：将中间键提升到父节点，分裂为两个节点

删除：

1. 若在叶节点且 keys 足够，直接删除
2. 若不够，向兄弟借或合并

7.4 B+ 树（数据库索引核心）

B+ 树是 B 树的变种，MySQL InnoDB 的索引就是 B+ 树。

区别	B 树	B+ 树
数据存放	所有节点都存数据	只在叶节点存数据
叶节点链表	无	叶节点通过链表相连
非叶节点	存 key + data	只存 key（索引）
范围查询	需要中序遍历	$O({\log }_{m}n)$高效
适用场景	随机查询	数据库索引、文件系统

其中 $m$ 是阶数。在数据库场景下，增加 $k$（连续遍历的个数）通常用于描述范围查询。

B+ 树叶节点形成有序双向链表，范围查询只需找到起点，然后沿链表顺序遍历即可。

7.5 B 树 vs B+ 树应用场景

---

八、堆（Heap）

8.1 二叉堆

堆是一棵完全二叉树，满足堆序性质。

类型	性质
最大堆	父节点 ≥ 子节点（根最大）
最小堆	父节点 ≤ 子节点（根最小）

8.2 数组实现堆

由于完全二叉树的性质，堆可以用数组存储，无需指针。

对于下标 i 的节点：
- 父节点：parent(i) = (i - 1) / 2
- 左子节点：left(i) = 2 * i + 1
- 右子节点：right(i) = 2 * i + 2

class MaxHeap {
    vector<int> heap;

    void siftUp(int idx) {
        while (idx > 0) {
            int parent = (idx - 1) / 2;
            if (heap[parent] >= heap[idx]) break;  // 已经满足堆性质
            swap(heap[parent], heap[idx]);
            idx = parent;
        }
    }

    void siftDown(int idx) {
        int n = heap.size();
        while (true) {
            int largest = idx;
            int left = 2 * idx + 1;
            int right = 2 * idx + 2;

            if (left < n && heap[left] > heap[largest])
                largest = left;
            if (right < n && heap[right] > heap[largest])
                largest = right;

            if (largest == idx) break;  // 已就位
            swap(heap[idx], heap[largest]);
            idx = largest;
        }
    }

public:
    void push(int val) {
        heap.push_back(val);
        siftUp(heap.size() - 1);  // O(log n)
    }

    void pop() {
        heap[0] = heap.back();
        heap.pop_back();
        siftDown(0);  // O(log n)
    }

    int top() { return heap[0]; }  // O(1)
    int size() { return heap.size(); }
};

8.3 堆排序

void heapSort(vector<int>& arr) {
    // 1. 建堆 O(n)
    priority_queue<int, vector<int>, greater<int>> minHeap(arr.begin(), arr.end());

    // 2. 依次取出 O(n log n)
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = minHeap.top();
        minHeap.pop();
    }
}

8.4 C++ STL 堆操作

vector<int> v = {3, 1, 4, 1, 5, 9};

// 将数组转为堆
make_heap(v.begin(), v.end());              // 默认大顶堆 O(n)

// 插入元素
v.push_back(10);
push_heap(v.begin(), v.end());              // O(log n)

// 删除堆顶
pop_heap(v.begin(), v.end());               // 将堆顶移到末尾
v.pop_back();

// 堆排序
sort_heap(v.begin(), v.end());              // 将堆变为有序数组 O(n log n)

操作	时间复杂度
push / push_heap	O(log n)
pop / pop_heap	O(log n)
top	O(1)
make_heap	O(n)（不是 O(n log n)！）
sort_heap	O(n log n)

---

九、字典树（Trie）

9.1 定义

Trie（前缀树）是一种用于高效存储和检索字符串集合的树形结构。每个节点代表一个字符，从根到某节点的路径构成一个前缀。

上图存储了四个单词：app、apple、bed、bee。* 标记表示该节点为某个单词的结尾。

9.2 C++ 实现

class Trie {
    struct TrieNode {
        TrieNode* children[26];
        bool isEnd;  // 标记是否为单词结尾

        TrieNode() : isEnd(false) {
            for (int i = 0; i < 26; i++) children[i] = nullptr;
        }
    };

    TrieNode* root;

public:
    Trie() { root = new TrieNode(); }

    // 插入单词 O(len)
    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!node->children[idx])
                node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isEnd = true;
    }

    // 查找单词 O(len)
    bool search(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!node->children[idx]) return false;
            node = node->children[idx];
        }
        return node->isEnd;
    }

    // 判断是否有以此前缀开头的单词 O(len)
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (!node->children[idx]) return false;
            node = node->children[idx];
        }
        return true;
    }
};

9.3 特点与应用

特性	说明
插入/查找	O(len)，len 为字符串长度
空间复杂度	随字符串数量增多，可用压缩 Trie 优化
适用场景	自动补全、拼写检查、IP 路由最长前缀匹配

---

十、线段树（Segment Tree）

10.1 定义

线段树是一种二叉树，用于高效处理区间查询（如区间求和、区间最值）和区间修改。

10.2 原理与实现（区间求和为例）

• 建树：每个节点维护一个区间 [L, R] 的和。叶子节点维护单个元素 [i, i]。
• 查询：将查询区间拆分为若干个线段树上的标准区间。
• 修改：单点修改更新根到叶子的路径。区间修改需引入懒惰标记（Lazy Tag）。

class SegmentTree {
    vector<int> tree;
    vector<int> data;
    int n;

    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = data[start];
            return;
        }
        int mid = start + (end - start) / 2;
        int leftNode = 2 * node + 1;
        int rightNode = 2 * node + 2;
        build(leftNode, start, mid);
        build(rightNode, mid + 1, end);
        tree[node] = tree[leftNode] + tree[rightNode];
    }

    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            data[idx] = val;
            tree[node] = val;
            return;
        }
        int mid = start + (end - start) / 2;
        int leftNode = 2 * node + 1;
        int rightNode = 2 * node + 2;
        if (start <= idx && idx <= mid)
            update(leftNode, start, mid, idx, val);
        else
            update(rightNode, mid + 1, end, idx, val);
        tree[node] = tree[leftNode] + tree[rightNode];
    }

    int query(int node, int start, int end, int L, int R) {
        if (R < start || end < L) return 0;  // 无交集
        if (L <= start && end <= R) return tree[node];  // 完全包含
        
        int mid = start + (end - start) / 2;
        int leftNode = 2 * node + 1;
        int rightNode = 2 * node + 2;
        int sumLeft = query(leftNode, start, mid, L, R);
        int sumRight = query(rightNode, mid + 1, end, L, R);
        return sumLeft + sumRight;
    }

public:
    SegmentTree(vector<int>& arr) {
        data = arr;
        n = arr.size();
        tree.resize(4 * n);  // 线段树空间一般开 4N
        if (n > 0) build(0, 0, n - 1);
    }
    
    void update(int idx, int val) { update(0, 0, n - 1, idx, val); }
    int query(int L, int R) { return query(0, 0, n - 1, L, R); }
};

操作	时间复杂度	空间复杂度
建树	O(n)	O(n) (需 4n 空间)
单点修改	O(log n)	-
区间查询	O(log n)	-
区间修改	O(log n) 带 Lazy Tag	-

---

十一、树状数组（Fenwick Tree / BIT）

11.1 定义

树状数组（Binary Indexed Tree）用数组模拟树形结构，主要用于解决动态前缀和问题。它比线段树代码更短，常数更小。

11.2 核心思想：lowbit

lowbit(x) 取出 x 的二进制中最右侧的 1。

int lowbit(int x) { return x & (-x); }

数组 tree[i] 维护区间 [i - lowbit(i) + 1, i] 的和。

11.3 C++ 实现

class BIT {
    vector<int> tree;
    int n;

    int lowbit(int x) { return x & (-x); }

public:
    BIT(int size) : n(size) {
        tree.assign(n + 1, 0);  // 索引从 1 开始
    }

    // 单点增加：A[i] += delta
    void add(int i, int delta) {
        while (i <= n) {
            tree[i] += delta;
            i += lowbit(i);  // 找父节点
        }
    }

    // 查询前缀和：A[1] + ... + A[i]
    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);  // 找前驱区间
        }
        return sum;
    }

    // 区间和 [L, R]
    int query(int L, int R) {
        return query(R) - query(L - 1);
    }
};

线段树 vs 树状数组：

• 树状数组：代码短，常数小，只支持满足结合律且可差分的操作（如加法、异或）。
• 线段树：功能更强，支持求最值（不可差分）、复杂区间修改。

---

十二、并查集（Union-Find）

12.1 定义

并查集用于处理不相交集合的**合并（Union）和查询（Find）**问题。常用于检测图中的环、计算连通分量、Kruskal 最小生成树算法。

12.2 核心优化

1. 路径压缩：在 Find 时，把经过的节点直接连到根上。
2. 按秩合并：在 Union 时，把较矮的树接到较高的树上。

class UnionFind {
    vector<int> parent;
    vector<int> rank;

public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; i++) parent[i] = i;  // 初始化，每个元素的父节点是自己
    }

    // 查找并进行路径压缩
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }

    // 按秩合并
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

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

时间复杂度：同时使用路径压缩和按秩合并，单次操作复杂度为 O(α(n))，α 是反阿克曼函数，极慢增长，近乎 O(1)。

---

十三、哈夫曼树（Huffman Tree）

13.1 定义

给定 n 个带权叶子节点，构造一棵二叉树，使带权路径长度（WPL）最小的树称为哈夫曼树（最优二叉树）。常用于数据压缩（哈夫曼编码）。

13.2 构造过程（贪心）

每次从森林中选出权值最小的两个节点，合并为一个新节点，权值为两者之和。

// 节点定义
struct HuffNode {
    char data;
    int freq;
    HuffNode *left, *right;
    HuffNode(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
};

// 比较器：最小堆
struct Compare {
    bool operator()(HuffNode* l, HuffNode* r) {
        return l->freq > r->freq;
    }
};

HuffNode* buildHuffmanTree(vector<char>& data, vector<int>& freq) {
    priority_queue<HuffNode*, vector<HuffNode*>, Compare> pq;
    for (int i = 0; i < data.size(); ++i)
        pq.push(new HuffNode(data[i], freq[i]));

    while (pq.size() > 1) {
        HuffNode* left = pq.top(); pq.pop();
        HuffNode* right = pq.top(); pq.pop();
        
        HuffNode* top = new HuffNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        pq.push(top);
    }
    return pq.top();
}

---

十四、图的基础与遍历

14.1 图的表示

1. 邻接矩阵：二维数组，适合稠密图，判断两点是否相连 O(1)。
2. 邻接表：数组+链表/vector，适合稀疏图，节省空间。

// 1. 邻接矩阵表示
vector<vector<int>> matrix(n, vector<int>(n, 0));
matrix[u][v] = w;

// 2. 邻接表表示
vector<vector<int>> adj(n);  // 无权图
adj[u].push_back(v);

vector<vector<pair<int, int>>> adjW(n);  // 有权图 pair<v, weight>
adjW[u].push_back({v, w});

14.2 深度优先搜索（DFS）

利用递归（隐式栈），探索到底，再回溯。

void dfs(int u, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, adj, visited);
        }
    }
}

14.3 广度优先搜索（BFS）

利用队列，逐层探索。常用于求无权图的最短路径。

void bfs(int start, vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";
        
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

---

十五、对比速查表

15.1 树的对比

数据结构	特点	查找/插入/删除复杂度	主要应用场景
BST	有序，但不平衡	O(h)（最坏 O(n)）	基础教学，简单树查找
AVL	严格平衡，高度差 ≤ 1	O(log n)	查找极多、修改少的内存数据
红黑树	弱平衡，最长路径 ≤ 2×最短	O(log n)	C++ STL (map/set)，频繁增删查
B/B+ 树	多路，极矮，适合磁盘	O(log_m n)	数据库索引 (MySQL)、文件系统
Trie	前缀共享，多叉	O(len)	字符串检索、自动补全
堆	维护最大/最小元素	插入 O(log n), 取顶 O(1)	优先队列、堆排序、Top K 问题
线段树	维护区间信息	O(log n)	任意区间求和/最值及区间修改
树状数组	位运算维护前缀和	O(log n)	高效处理动态前缀和

15.2 C++ STL 对照表

数据结构	STL 容器 / 适配器	底层实现
动态数组	std::vector	连续内存块
双向链表	std::list	双向链表
单向链表	std::forward_list	单向链表
栈	std::stack	默认基于 deque
队列	std::queue	默认基于 deque
双端队列	std::deque	分段连续内存块
优先队列	std::priority_queue	数组实现的二叉堆（默认大顶）
有序字典	std::map	红黑树
无序字典	std::unordered_map	哈希表（链地址法）
有序集合	std::set	红黑树
无序集合	std::unordered_set	哈希表（链地址法）

---

十六、如何选择合适的数据结构

1. 需要按键值范围查询/有序遍历吗？
   • 是 → map / set (红黑树)
   • 否 → unordered_map / unordered_set (哈希表)
2. 需要频繁在中间插入/删除吗？
   • 是 → list
   • 否 → vector
3. 需要动态维护区间和/最值？
   • 差分操作(如和) → 树状数组 (代码短)
   • 复杂区间操作 → 线段树
4. 需要维护动态最值（Top K）？
   • → priority_queue (堆)
5. 处理大量的字符串前缀匹配？
   • → Trie (字典树)
6. 处理集合的连通性/分类问题？
   • → 并查集 (Union-Find)