本文按照“理论知识 + 实现与练习”的方式整理数据结构与算法，可以分为三组阅读：
  1. 数据结构基础与线性结构。
  1. 树与图。
  1. 查找、排序与算法选择。

1. 数据结构的定义和表示

数据结构是具有特定关系的数据元素的集合，包括逻辑结构和存储结构两个方面。

1.1 逻辑结构

本节从「按元素关系划分」和「按线性关系划分」两方面说明逻辑结构。
1.1.1 按元素关系划分
四类基本结构：
notion image
1.1.2 按线性关系划分
线性结构（线性表、栈和队列、字符串、数组、广义表）和非线性结构（树、图、集合）

1.2 存储结构

本节从「顺序存储结构」和「链式存储结构」两方面说明存储结构。
1.2.1 顺序存储结构
顺序存储结构把数据元素存放在地址连续的存储单元中，元素之间的逻辑次序与物理位置一致，典型形式是一维数组。
notion image
1.2.2 链式存储结构
链式存储结构通过指针描述元素之间的逻辑关系，各节点可以分布在连续或不连续的存储单元中。
notion image

2. 线性表

本章从「案例引入」「线性表的顺序表示和实现」和「线性表的链式表示和实现」等方面说明线性表。

2.1 案例引入

假设出版社把图书数据保存在文本文件 book.txt 中，每本图书包含 ISBN、书名和价格。图书信息管理系统需要实现以下 6 项功能：
  1. 查找：根据指定的 ISBN 或书名查找相应图书的有关信息，并返回该图书在表中的位置序号。
  1. 插入：插入一种新的图书信息。
  1. 删除：删除一种图书信息。
  1. 修改：根据指定的 ISBN，修改该图书的价格。
  1. 排序：将图书按照价格由低到高进行排序。
  1. 计数：统计图书表中的图书数量。
分别使用线性表的顺序存储结构和链式存储结构实现以上功能。

2.2 线性表的顺序表示和实现

本节从「线性表的顺序存储表示」和「顺序表中基本操作的实现」两方面说明线性表的顺序表示和实现。
2.2.1 线性表的顺序存储表示
假设线性表的每个元素占用 J 个存储单元，并以第一个单元的存储地址作为数据元素的存储起始位置，则线性表中的存储位置满足以下关系：
因此，第 个元素的存储地址为：
2.2.2 顺序表中基本操作的实现
整体实现代码：

2.3 线性表的链式表示和实现

注意：我的实现都是用带头结点的单链表
整体实现代码：
2.3.1 单链表
单链表的定义和表示：单链表由一系列节点组成，每个节点包含数据域和一个指针域，因此只能沿一个方向遍历。
我们可以加入一个头结点来统一操作（对首元结点和判空的统一处理）。
notion image
关键符号说明：
  • L（头指针）：指向头结点 Head，是链表的入口
  • Head（头结点）：不存储数据元素，是链表的起点
  • NULL：空指针，表示链表结束
单链表的创建：可以使用头插法或尾插法逐个连接新节点。
前插法：
notion image
后插法：
将新节点插入链表的最后一个节点后面来创建链表，这里我们需要新创建一个尾指针来实现
notion image
2.3.2 循环链表的定义和表示
循环链表在单链表的基础上设立了一个尾指针指向头结点，我们从表中任意一个节点出发均可以找到表中其他节点。
notion image
2.3.3 双向链表的定义和表示
双向链表的节点有两个指针域，一个指向直接后继，另一个指向直接前驱。
notion image

2.4 小结

本节从「顺序表和链表的比较」和「单链表、循环链表和双向链表的比较」两方面说明小结。
2.4.1 顺序表和链表的比较
顺序表（通常指数组）和链表是线性存储结构的两种基本实现方式。
存储结构
顺序表
链表
存储空间
预先分配，会导致空间闲置或者溢出现象，存储密度＝1
动态分配，不会导致空间闲置或者溢出现象，存储密度＜1
存取／查找
O（1）（可以直接通过下标访问）
O(n)（必须从头节点开始遍历）
插入/删除
O(n)（通常需要移动后续元素）
O（1）（找到目标节点后，只需修改指针）
适用情况
表长变化不大，且能事先确定的变化范围；很少进行插删操作，大量按元素序号访问的情况下使用
表长变化大，且频繁插删操作
补充：顺序表通常具有更好的缓存局部性。链表只有在已经持有目标节点或其前驱位置时，局部插入和删除才能达到 O(1)；如果需要先查找位置，总复杂度仍可能退化到 O(n)。
2.4.2 单链表、循环链表和双向链表的比较
链表类型
节点结构
插入/删除操作
空间复杂度
适用场景
单链表
数据 + Next
O(n)（必须从头遍历）
O(n)
简单、数据量变化大、仅需单向遍历
循环链表
数据 + Next
O(n)
O(n)
适合循环处理任务，如队列或轮转调度
双向链表
Prev＋数据 + Next
O(1)（已知当前节点时）
O(n)（指针开销更大）
频繁进行插入/删除操作，或需要双向遍历的场景

3. 栈和队列

本章从「栈」「队列」和「相关案例」等方面说明栈和队列。

3.1 栈

本节从「栈的定义和特点」「栈的表示和实现」和「栈和递归」等方面说明栈。
3.1.1 栈的定义和特点
  • 栈的定义：栈是限定在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。
  • 栈的特点：先进后出（后进先出）。
3.1.2 栈的表示和实现
顺序栈的表示和实现：顺序栈使用连续存储空间，并通过 top 记录栈顶位置。
  1. 空栈
notion image
这时的 top == base
  1. 进栈
notion image
栈满：
notion image
条件：top - base＝stack_size
  1. 出栈
弹出元素 E：
notion image
链栈的表示和实现：链栈以链表保存元素，栈顶通常设在链表头部，以便在 O(1) 时间内完成入栈和出栈。
  1. 空栈：top → NULL
  1. 进栈：
notion image
栈满：
notion image
  1. 出栈：
弹出元素 D：
notion image
3.1.3 栈和递归
递归实现：递归函数会直接或间接调用自身，并通过终止条件结束调用。
  • 定义：递归是指一个函数、过程或者数据结构定义的内部又直接（或间接）出现本身的应用。
  • 特点：包含自己，自己定义自己，直接或间接的调用自己。
  • 示例：
  1. 阶乘公式：
notion image
递归实现：
notion image
时间复杂度：
空间复杂度：
  1. 斐波那契数列公式：
notion image
递归代码实现：
时间复杂度：
空间复杂度：
  1. 汉诺塔问题
问题描述：有三根柱子分别为 A、B、C；在柱子 A 上有 n 个大小不同的圆盘，叠放顺序是大的下面，小的在上面；要求将所有圆盘从柱子 A 上移动到柱子 C。移动规则：
  1. 每次只能移动一个圆盘；
  1. 任何时候都不能将大圆盘放在小圆盘上面；
  1. 可以借助柱子 B 作为辅助。
分析思路：将问题分为三个子问题
  1. 将 n－1 个圆盘从 A 移动到 B，借助 C；
  1. 将最大的圆盘从 A 移到 C；
  1. 将 n－1 个圆盘从 B 移动到 C，借助 A；
递归代码实现：
时间复杂度：
空间复杂度：
总结：
递归问题的精髓就在于通过不断地缩小问题的规模，最终在基准情况下解决问题，然后组合各个子问题的解来得到原问题的解。
效率分析：递归算法结构清晰，程序易读，但是时间复杂度高，工作记录大，只适合数据规模小的时候使用。
使用栈模拟递归：显式栈可以保存调用过程中的状态，从而把递归算法改写为迭代算法。二叉树章节会给出具体实现。
3.1.4 栈的应用
  • 递归转迭代
  • 深度优先搜索（DFS）
  • 回溯算法
  • 表达式求值

3.2 队列

本节从「队列的定义和特点」「队列的表示和实现」和「队列的应用」等方面说明队列。
3.2.1 队列的定义和特点
  • 队列的定义：队列也是一种线性表，只允许在表的一端进行插入，在表的另一端删除。允许插入的一端称为队尾，允许删除的一端称为队头。（和生活中排队结账的行为一样）
  • 特点：先进先出。
3.2.2 队列的表示和实现
队列的顺序表示和实现：顺序队列使用连续存储空间，并通过 front 和 rear 记录队头与队尾位置。
  1. 空队列
notion image
队空条件：front == rear
  1. 入队
入队元素 A
notion image
入队元素 B
notion image
队满条件：（rear＋1）％MaxSize == front
其中 MaxSize 为队列的空间大小
  1. 出队
notion image
notion image
notion image
队列的链式表示和实现：链式队列通过队头指针和队尾指针连接节点，入队在队尾完成，出队在队头完成。
  • 空队列
notion image
front → NULL
rear → NULL
  • 入队
notion image
notion image
notion image
  • 出队
notion image
notion image
3.2.3 队列的应用
  • 广度优先搜索（BFS）
  • 层级遍历
  • 任务调度
  • 消息传递

3.3 相关案例

  1. 1 数制的转换：将十进制转换为二进制
分析：
  • 二进制是＂逢二进一＂的计数系统。
  • 十进制的二进制的基本方法时＂除 2 取余，逆序排列＂。
  • 需要特殊处理的情况：0、负数。
代码：
  1. 2 括号匹配检验
题目：给定一个只包括＇（＇，＇）＇，＇｛＇，＇}‘,’[‘,’]’ 的字符串 s，判断字符串是否有效。
有效字符串需满足：
  1. 左括号必须用相同类型的右括号闭合。
  1. 左括号必须以正确的顺序闭合。
  1. 每个右括号都有一个对应的相同类型的左括号。
Leetcode 题目链接：20. 有效的括号 - 力扣（LeetCode）
思考不匹配的情况：
  1. 字符串里左方向的括号多余了，所以不匹配：已经遍历完了字符串，但是栈不为空，说明左括号没有匹配完。
  1. 括号没有多余，但是类型匹配不上：在匹配的过程，发现栈里要匹配字符的类型对不上。
  1. 字符串右方向的括号多余了，所以不匹配：匹配过程中，栈已经为空了，说明多出了右括号。
实现代码：

3.4 表达式求值

tokens 表示一个逆波兰表达式。题目要求计算并返回该表达式的整数结果。
  • 有效运算符包括 +、-、* 和 /。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是向零截断。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位整数表示。
Leetcode 题目链接：150. 逆波兰表达式求值 - 力扣（LeetCode）
解释：
逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 )。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * )。
实现代码：

4. 字符串、数组、广义表

本章围绕「字符串的模式匹配算法」展开，先明确核心概念与适用边界。

4.1 字符串的模式匹配算法

Leetcode 题目链接：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
在字符串 haystack 中查找字符串 needle 的第一次出现位置；若不存在，则返回 -1。
BF 算法（暴力匹配算法）
 
最好时间复杂度：（模式串出现在主串开头）
最坏时间复杂度：
平均时间复杂度：
空间复杂度：
KMP 算法：
时间复杂度：
空间复杂度：（用于存储 next 数组）

5. 树和二叉树

本章从「树」「二叉树」和「二叉树的遍历」等方面说明树和二叉树。

5.1 树

本节从「树的定义」和「树的基本术语」两方面说明树。
5.1.1 树的定义
树是 n 个结点的有限集，它要么是空树要么是非空树，对于非空树：
  1. 有且仅有一个特定的称为根的结点
  1. 当 n>1 时，除根节点以外的其余节点可分为 m 个互不相交的有限集 T1，T2，…，Tm，其中每个集合本身又是一棵树，称为根的子树。
5.1.2 树的基本术语
  1. 结点：树中的一个独立单元。
  1. 结点的度：结点拥有的子树的数量称为结点的度
  1. 树的度：是树内结点各节点度的最大值。
  1. 叶子：度为 0 的节点称为叶子节点或终端结点。
  1. 双亲和孩子：结点的子树的根称为该结点的孩子，该结点称为孩子的双亲。
  1. 兄弟：同一个双亲的孩子之间互称兄弟。
  1. 层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。
  1. 树的深度：树中节点的最大层次称为树的深度或高度。
  1. 结点的深度：从根节点到该节点所经过的边数（路径长度）从上往下数。
  1. 结点的高度：从该节点到其子树中最远的叶子节点所经过的边数（最长路径长度）从下往上数。
  1. 有序树和无序树：如果将树中节点的各子树看成从左到右是有次序的，则称该树为有序树，否则为无序树。
  1. 森林：是 m（m>=0）棵互不相交的树的集合。
 

5.2 二叉树

本节从「二叉树的定义」和「二叉树的性质」两方面说明二叉树。
5.2.1 二叉树的定义
  • 二叉树是 n（n>=0）个结点所构成的集合，该集合或者为空集，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
  • 满二叉树：深度为 k 且含有 个结点的二叉树。
 
notion image
 
  • 完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点集中在该层最左侧的若干连续位置。若最底层为第 h 层且根节点位于第 1 层，则该层节点数范围为 1～2^(h−1)。
notion image
  • 平衡二叉树：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
notion image
  • 二叉搜索树：二叉搜索树是一棵有序树：
  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉搜索树
5.2.2 二叉树的性质
  1. 在二叉树的第 i 层上至多有 2^(i-1)个结点（i>=1，1 为根节点所在的层次）。
  1. 深度为 k 的二叉树至多有 2^k-1 个结点（k>=1）。
  1. 对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n=n+1。
  1. 具有 n 个结点的完全二叉树的深度为 k=floor()+1。

5.3 二叉树的遍历

前序遍历算法：遍历顺序 中左右
递归法实现：
迭代法实现：
中序遍历算法：遍历顺序 左中右
递归法实现：
迭代法实现：
 
后序遍历算法：遍历顺序 左右中
递归法实现：
迭代法实现：
层序遍历算法：
notion image
版本一：基于队列的广度优先搜索 (BFS)
时间复杂度：
空间复杂度：
版本二：递归法实现
时间复杂度：
空间复杂度：

5.4 哈夫曼树

本节从「哈夫曼树的基本概念」和「应用：求最优前缀编码（哈夫曼编码）」两方面说明哈夫曼树。
5.4.1 哈夫曼树的基本概念
哈夫曼树（Huffman Tree）又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为 0 层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为 WPL，WPL 最小的二叉树就是哈夫曼树。
5.4.2 应用：求最优前缀编码（哈夫曼编码）
哈夫曼编码是一种可变字长编码方式，是数据压缩算法中的一种。该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。
构建过程：反复选择权值最小的两棵树合并，直到森林中只剩一棵树。
  1. 将 n 个权值看作 n 棵只有根节点的二叉树，组成森林 F。
  1. 在森林 F 中选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且新二叉树的根节点权值为其左右子树根节点权值之和。
  1. 在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。
  1. 重复步骤 2 和 3，直到 F 中只剩下一棵树为止。
哈夫曼编码：从根节点开始，向左的路径标记为 0，向右的路径标记为 1；到达叶子节点时，路径上的标记序列就是该字符的编码。
构造算法：下面使用小根堆维护当前权值最小的两个节点。

5.5 常见搜索树与多路平衡树

本节从「二叉搜索树（BST）」「AVL 树」和「红黑树」等方面说明常见搜索树与多路平衡树。
5.5.1 二叉搜索树（BST）
性质：
  • 左子树键小于根键；
  • 右子树键大于根键；
  • 中序遍历得到有序序列。
平均查找复杂度可接近 O(log n)，但插入顺序不佳时可能退化为链表，复杂度达到 O(n)。
重复键如何处理不是唯一规定，可禁止重复、记录计数或制定固定插入侧。
5.5.2 AVL 树
AVL 是严格高度平衡的 BST：
优点：
  • 查询高度严格受控；
  • 查找性能稳定。
代价：
  • 插入和删除可能需要更多旋转；
  • 维护信息和实现复杂度更高。
5.5.3 红黑树
红黑树是一种近似平衡 BST。常见定义使用黑色 NIL 哨兵叶节点。
典型规则：
  1. 每个节点为红或黑；
  1. 根通常视为黑色；
  1. 所有 NIL 哨兵叶节点为黑色；
  1. 红节点的子节点不能为红色；
  1. 从任意节点到其所有后代 NIL 叶节点的路径包含相同数量的黑节点。
红黑树将树高控制在 O(log n)，插入和删除时的调整通常比 AVL 树更宽松。
C++ 标准并未规定 std::map 和 std::set 必须使用红黑树，只规定有序关联容器的行为和复杂度。常见实现确实使用红黑树或相近平衡树。
5.5.4 B 树
B 树是多路平衡搜索树：
  • 一个节点保存多个键和多个子指针；
  • 所有叶节点通常处于同一层；
  • 通过提高分支数降低树高；
  • 适合块设备和页式存储。
5.5.5 B+ 树
B+ 树与 B 树相关，但常见区别是：
  • 内部节点主要保存索引键；
  • 实际记录集中在叶节点；
  • 叶节点通常按顺序链接；
  • 范围查询和顺序扫描更高效。
数据库索引中常见的是 B+ 树或其变体。不能简单写成“MySQL 索引就是 B 树”；具体结构取决于存储引擎和索引类型。

6. 图

本章从「图的定义」「图的基本术语」和「图的遍历」等方面说明图。

6.1 图的定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：，其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。

6.2 图的基本术语

  • 无向图：图中任意两个顶点之间的边都是无向边。其中，有 n(n-1)/2 条边则称为无向完全图。
  • 有向图：图中任意两个顶点之间的边都是有向边。其中，有 n(n-1)条弧则称为有向完全图。
  • 顶点的度：无向图中，顶点的度是指依附于该顶点的边的个数。有向图中，顶点的度分为入度和出度。
  • 路径：从顶点 vi 到 vj 的路径是一个顶点序列。
  • 连通图：在无向图中，如果任意两个顶点都是连通的，则称该图是连通图。
  • 强连通图：在有向图中，如果任意两个顶点都是强连通的，则称该图是强连通图。
  • 连通分量：无向图中的极大连通子图。
  • 强连通分量：有向图中的极大强连通子图。
  • 生成树：一个连通图的生成树是一个极小的连通子图，它含有图中全部 n 个顶点，但只有足以构成一棵树的 条边。
  • 有向树：有一个顶点的入度为 0，其余顶点的入度均为 1 的有向图。

6.3 图的遍历

本节从「深度优先搜索」和「广度优先搜索」两方面说明图的遍历。
6.3.1 深度优先搜索
代码实现：
6.3.2 广度优先搜索
代码实现：

6.4 图的应用

本节从「小生成树」和「最短路径」两方面说明图的应用。
6.4.1 小生成树
最小生成树（Minimum Spanning Tree，MST）是一个连通图的生成树中边的权值之和最小的那棵生成树。
普里姆（Prim）算法：
Prim 算法从任意一个顶点开始，每次选择一条连接当前已构建的树和树外顶点且权值最小的边，将对应的顶点加入到树中，直到所有顶点都被加入。
算法步骤：
  • 初始化：任取一个顶点 u0，将其加入到集合 U 中，U={u0}，TE={}。
  • 在所有 u∈U，v∈V-U 的边(u,v)中找一条权值最小的边(u0,v0)，将这条边加入 TE，同时将 v0 加入 U。
  • 重复步骤 2，直到 U=V。
代码实现：
 
克鲁斯卡尔（Kruskal）算法：
Kruskal 算法按权值从小到大的顺序选择边，若该边连接的两个顶点不在同一个连通分量中，则选择该边，直到所有顶点都在同一个连通分量中。
算法步骤：
  • 将图中的所有边按权值从小到大排序。
  • 初始化：每个顶点自成一个连通分量。
  • 按权值从小到大选择边，若该边连接的两个顶点不在同一个连通分量中，则将该边加入生成树，同时合并这两个顶点所在的连通分量。
  • 重复步骤 3，直到所有顶点都在同一个连通分量中。
代码实现：
6.4.2 最短路径
迪杰斯特拉（Dijkstra）算法：Dijkstra 算法用于求解单源最短路径问题，即从某个源点到其余各顶点的最短路径。该算法要求图中不存在负权边。
算法步骤：
  • 初始化：设置两个顶点集合 S 和 T，S 中存放已找到最短路径的顶点，T 中存放剩余顶点。初始时，S={v0}，T=V-S。dist[i]表示 v0 到 vi 的最短路径长度，初始时，若 v0 到 vi 有边，则 dist[i]为边权，否则为无穷大。
  • 从 T 中选取一个与 S 中顶点有关联边且权值最小的顶点 w，加入 S。
  • 修改 T 中顶点的 dist 值：对于 T 中的每一个顶点 v，若由于 w 的加入使得 v0 到 v 的路径更短，则更新 dist[v] = min(dist[v], dist[w] + weight(w, v))。
  • 重复步骤 2 和 3，直到 S 包含所有顶点。
注意：Dijkstra 算法不能处理有负权边的图。
代码实现：

7. 查找算法

本章从「顺序查找」「二分查找」和「树表的查找」等方面说明查找算法。

7.1 顺序查找

查找过程为：从表中一端开始，依次比较表中元素和给定的目标值，如果元素值等于目标值，则查找成功。
时间复杂度：O(N)
空间复杂度：O(1)
如果数组无序且，数组规模比较小，则可以使用，如果规模很大，那么这个实现性能会很差

7.2 二分查找

二分查找也称为折半查找。使用二分查找的前提是数组元素必须是有序的。查找过程为：给定一个数组和一个目标值，从表的中间位置开始记录，如果目标值和中间元素相同，则查找成功；如果中间元素小于或大于目标值，则在比中间值大或小的那一半中查找。重复操作，直到查找成功。实现代码有两种写法，取决于给定的查找范围是左闭右闭还是左闭右开的。
时间复杂度：O(logN)
空间复杂度：O(1)
时间复杂度计算过程：
第一次比较，剩余规模 n/2
第二次比较，剩余规模 n/4
第三次比较，剩余规模 n/8
……
第 k 次比较，剩余规模
在最坏情况下，搜索区间只剩最后一个元素，所以我们的 k 满足；
所以 ，时间复杂度为

7.3 树表的查找

树表是利用树形结构组织的数据查找表，其目标是实现 级别的高效查找、插入和删除操作。
7.3.1 二叉排序树（BST）
又称为二叉查找树、二叉搜索树，是一种特殊的二叉树，满足以下基本特性：
  1. 左小右大：左边的节点小于中间的节点，中间的节点小于右边的节点
  1. 左右子树本身也分别是二叉排序树
  1. 中序遍历 BST 得到的序列是完全有序的
平均时间复杂度：O(log N)
最坏时间复杂度：O(N)
7.3.2 平衡二叉树（AVL）
是最早被发明的自平衡二叉树，严格满足以下特性：
  1. 任意节点左右子树的高度差的绝对值不超过 1
  1. 平衡因子 = 左子树高度 − 右子树高度
平均时间复杂度（查找、增删）：O(log N)
7.3.3 红黑树
红黑树是一种在平衡性和维护成本很好的折中的自平衡二叉排序树，每个节点被标记为黑色或红色。
满足以下规则：
  1. 根节点是黑色
  1. 叶子节点是黑色
  1. 如果一个节点是红色，那么它的两个子节点必须是黑色
  1. 从任意节点出发到其所有叶子节点上包含的黑色节点数量必须相等（黑色平衡）
平均时间复杂度（查找、增删）：O(log N)
7.3.4 B 树
B 树是一种多路搜索树，它的设计初衷是为了优化外部存储（如硬盘、SSD）的数据查找效率，与前面几种树的内存优化目标不同。
查找复杂度：。虽然理论上与 级别相似，但在外部存储中，M 越大，I／O 次数越少，实际性能越好。

8. 排序算法

本章从「直接插入排序」「二分插入排序」和「希尔排序」等方面说明排序算法。

8.1 直接插入排序

基本思想：类似于我们整理扑克牌，逐个顺序比较后插入。将数组分为已排序和未排序两个部分，第一个元素放入已排序部分，和未排序部分比较，直到排序完成。
时间复杂度：
  • 最好情况：O(n) - 数组已经有序
  • 最坏情况：O(n²) - 数组完全逆序
  • 平均情况：O(n²)
适用条件：当数据规模小、数据基本有序时可以使用。

8.2 二分插入排序

基本思想：二分插入排序是对直接插入排序的优化，在寻找插入位置时用二分查找代替顺序查找，减少了比较次数，但是移动次数不变。
时间复杂度：
  • 比较次数：O(n log n)
  • 移动次数：O(n²)
  • 总时间复杂度：O(n²)
适用条件：比较代价比较高的时候使用。

8.3 希尔排序

基本思想：也是对直接插入排序改进，又称为缩小增量排序，分组比较代替逐个比较。将原序列分成多个子序列进行插入排序，缩小间隔。重复以上过程，直到排序完成。
常见的增量序列：
  1. 希尔增量：n/2, n/4, …, 1
  1. Hibbard 增量：1, 3, 7, 15, …, 2^k-1
  1. Sedgewick 增量：1, 5, 19, 41, …
时间复杂度：
  • 最好情况：O(n log n)
  • 最坏情况：O(n²) - 使用希尔增量时
  • 平均情况：取决于增量序列
适用条件：中等规模数据时使用。

8.4 冒泡排序

基本思想：比较相邻元素，如果第一个元素比第二个元素大，则交换两个元素的位置。比较每一对•相邻元素，最后的元素一定是未排序中最大的。重复以上操作，直到排序完成。
时间复杂度：
  • 平均时间复杂度：O(N^2)
  • 交换次数：O(N^2)
  • 空间复杂度：O(1)
适用条件：小规模数据、数组基本有序、内存受限的情况。

8.5 选择排序

基本思想：在冒泡排序的基础上改进了交换次数，从第一个元素开始和后面的所有元素相比，比较出最小的元素，先记录下标，跟最后一个元素比较完之后再交换位置，得到最小元素。重复以上过程，直到排序完成。
时间复杂度：
  • 平均时间复杂度：
  • 交换次数：O(N)
  • 空间复杂度：O(1)
适用条件：小规模数据且比较代价高，内存受限的情况。

8.6 快速排序

基本思想：采用分治策略。选择一个基准元素，通过一趟排序将序列分隔成独立的两个部分，其中左边部分的所有元素比基准元素小，右边部分的所有元素都比基准元素大，然后再对这两个部分递归排序。
其中基准元素一般选：第一个元素、最后一个元素、中间元素。
时间复杂度
  • 平均时间复杂度：
  • 最坏时间复杂度：
  • 空间复杂度：
适用条件：当数据规模比较大、内存空间受限、数据分布随机时可以使用快排，但是如果数据分布本来就比较有序，选择最后一个元素作为基准时就容易将时间复杂度退化为。

8.7 堆排序

堆排序是一种树形选择排序，可以将待排序的数组看成是一颗完全二叉树的顺序存储结构。基本思想：排序规则是根节点小于或大于子节点，这样就可以将待排序序列构造成一个小顶堆或者是大顶堆。将堆顶元素和末尾元素交换，将剩余元素重新调整成堆，重复以上过程，直到堆中只剩一个元素。
堆的特性：
  1. 结构性：堆是一颗完全二叉树，底层节点从左到右填入
  1. 堆序性：
notion image
时间复杂度：（平均、最好、最坏）
空间复杂度：
适用条件：内存受限，且需要时间复杂度保证的场景。

8.8 归并排序

本节从「分治法」「单链表实现」和「数组实现」等方面说明归并排序。
8.8.1 分治法
分治通常包含三个步骤：
  1. 分解：将原问题拆成规模更小的子问题；
  1. 解决：递归或迭代处理子问题；
  1. 合并：组合子问题结果。
归并排序把“合并”作为核心步骤；快速排序则通过分区把元素放到基准值两侧，再分别处理两个子区间。
8.8.2 单链表实现
链表适合归并排序的原因：链表可以通过调整指针合并有序序列，不依赖随机访问。
  • 找中点可使用快慢指针；
  • 合并有序链表只需调整 next 指针；
  • 不依赖随机访问；
  • 时间复杂度稳定为 O(n log n)；
  • 可以保持稳定性。
递归实现：先使用快慢指针拆分链表，再递归排序并合并两个有序链表。
复杂度：
  • 时间复杂度：O(n log n)
  • 辅助空间复杂度：O(log n)，主要来自递归调用栈
边界条件中，下面这种写法：
在 head == nullptr 时会发生空指针解引用，应写成：
优先队列中转法：先把节点值放入小根堆，再按升序写回链表。
将节点值放入小根堆，再按顺序写回：
  • 时间复杂度：O(n log n)
  • 空间复杂度：O(n)
  • 实现简单；
  • 只改变值，不改变节点顺序。
如果题目要求真正重排节点、节点身份有意义，或节点除 val 外还含有相关数据，只交换/覆盖 val 可能不符合要求。
8.8.3 数组实现
复杂度：
  • 时间复杂度：O(n log n)
  • 空间复杂度：O(n)
  • 稳定：在相等时优先取左侧元素
常见应用：
  • 逆序对；
  • 外部排序；
  • 链表排序；
  • 需要稳定性的排序。
数组归并排序和链表归并排序示例已使用 C++17 编译，并在开启 -Wall -Wextra -Wpedantic -Werror 后通过空数组、重复值、负数及链表排序测试。

8.9 桶排序

基本思想：桶排序的思想不是基于比较来实现的，而是通过分配来实现的一种排序算法。设置固定数量的空桶；遍历数组，将每个元素放入对应的桶里；对每个非空桶进行排序，按照顺序把每个桶里的元素放回原数组。
平均时间复杂度：
最坏时间复杂度：
空间复杂度：
适用条件：数据分布均匀，数据范围有限。如整理扑克牌、给学生成绩排序。

9. 计数排序与基数排序

本章围绕「非比较排序」展开，先明确核心概念与适用边界。

9.1 非比较排序

本节从「计数排序」和「基数排序」两方面说明非比较排序。
9.1.1 计数排序
  • 适合整数键范围较小；
  • 时间复杂度通常为 O(n + k)；
  • 空间复杂度通常为 O(k)；
  • 是否稳定取决于具体实现。
9.1.2 基数排序
  • 按位或按字符分阶段排序；
  • 每一阶段通常要求稳定的子排序；
  • 复杂度取决于位数、基数和子排序；
  • 适合定长整数、字符串等特定键。

10. 数据结构与算法选择建议

  • vector 和数组适合需要随机访问及缓存友好的场景。
  • 需要链表排序：优先归并排序。
  • std::sort 适合一般数组排序；只有在教学、特定分区需求或需要自定义行为时再手写快速排序。
  • 只需要前 K 个：根据目标考虑维护大小为 k 的堆；找最大的 K 个通常维护小根堆，找最小的 K 个通常维护大根堆。
  • 查询很多且更新少：AVL 可能合适。
  • 增删查综合平衡：红黑树类结构常见。
  • 磁盘页和范围查询：B/B+ 树类结构。
  • tuple 可用于临时返回多个值。

11. 总结

本文梳理了线性表、栈与队列、字符串、树、图、查找和排序等核心内容。选择数据结构时，需要同时考虑访问方式、更新频率、数据规模、空间开销和实现复杂度；选择算法时，还应结合输入特征和复杂度要求判断。
示例代码用于说明主要数据结构和算法流程。工程实践中应优先使用经过充分测试的标准库实现，并根据实际输入补充边界条件、异常处理和测试。

12. 参考资料

  • 严蔚敏、李冬梅、吴伟民：《数据结构（C 语言版·第 2 版）》。