绪论
数据对象+数据=数据结构;
数据元素是数据的基本单位;
数据项是组成数据元素的最小单位;
数据对象是数据元素的集合;
数据结构分为逻辑结构和存储结构;
逻辑结构:集合、线性、树、图或网;
存储结构:顺序存储、链式存储;
时间复杂度和空间复杂度:大O表示法 O(1)、O(n)、O(logn)……
线性表
特点:有序性、唯一性、动态性、一对一
LOC(元素地址)=L0(基地址)+(i-1)*m(每个元素的地址长度)
顺序表插入到第i个节点前需要移动顺序表的元素(n-i+1)次(n为顺序表中已有元素个数)，平均复杂度O(n);
删除第i个节点需要移动元素(n-i)次
头指针没有数据，指向的是第一个有数据的节点(首元结点);
带头节点的表(头节点指的是头指针指向的节点，数据为空。
在有头节点的表中头节点指向首元结点)
顺序表的存储密度为1，链表的存储密度小于1
链表名称
查找表头结点
查找表尾结点
查找结点*p的前驱结点
带头结点的单链表 L
L->next时间复杂度 O(1)
从 L->next 依次向后遍历时间复杂度 O(n)
通过 p->next 无法找到其前驱
带头结点仅设头指针 L 的循环单链表
L->next时间复杂度 O(1)
从 L->next 依次向后遍历时间复杂度 O(n)
通过 p->next 可以找到其前驱时间复杂度 O(n)
带头结点仅设尾指针 R 的循环单链表
R->next时间复杂度 O(1)
R时间复杂度 O(1)
通过 p->next 可以找到其前驱时间复杂度 O(n)
带头结点的双向循环链表 L
L->next时间复杂度 O(1)
L->prior时间复杂度 O(1)
p->prior时间复杂度 O(1)
比较大类
比较子项
顺序表
链表
空间
存储空间
预先分配，会导致空间闲置或溢出现象
动态分配，不会出现存储空间闲置或溢出现象
存储密度
不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于 1
需要借助指针来体现元素间的逻辑关系，存储密度小于 1
时间
存取元素
随机存取，按位置访问元素的时间复杂度为 O(1)
顺序存取，按位置访问元素时间复杂度为 O(n)
插入、删除
平均移动约表中一半元素，时间复杂度为 O(n)
不需移动元素，确定插入、删除位置后，时间复杂度为 O(1)
适用情况
① 表长变化不大，且能事先确定变化的范围② 很少进行插入或删除操作，经常按元素位置序号访问数据元素
① 长度变化较大② 频繁进行插入或删除操作
栈和队列
栈的特性是LIFO(后进先出)，队列的特性是FIFO(先进先出)
队列实际操作指针:*base+front/rear
循环队列存储了M-1个元素认为队满;
循环队空:Q.front=Q.rear;
循环队满:(Q.rear+1)%MAXSIZE==Q.front (Q.rear与Q.front相邻);
循环队列长度:(Q.rear-Q.front+MAXSIZE)%MAXSIZE
比较项目
栈
队列
逻辑结构
和线性表一样，数据元素之间存在一对一的关系
和线性表一样，数据元素之间存在一对一的关系
存储结构（顺序存储）
顺序存储：存储空间预先分配，可能会导致空间闲置或栈满溢出现象；数据元素个数不能自由扩充
顺序存储（常设计成循环队列形式）：存储空间预先分配，可能会导致空间闲置或队满溢出现象；数据元素个数不能自由扩充
存储结构（链式存储）
链式存储：动态分配，不会出现闲置或栈满溢出现象；数据元素个数可以自由扩充
链式存储：动态分配，不会出现闲置或队满溢出现象；数据元素个数可以自由扩充
运算规则
插入和删除在表的一端（栈顶）完成，后进先出
插入运算在表的一端（队尾）进行，删除运算在表的另一端（队头），先进先出
串、数组和广义表
串（String）的基本概念
串是由零个或多个字符组成的有限序列
两个串相等当且仅当它们的长度相同、内容相同且内容位置相同
串中任意个连续字符组成的子序列称为子串。子串必须是原串中连续的一段字符序列。
空格串：由一个或多个空格字符（ASCII 32）组成的串。空格串的长度等于空格字符的个数，不是空串。
串的存储：串通常使用顺序存储结构，即一组地址连续的存储单元（如数组）存储串值的字符序列。每个字符占一个存储单元（通常为 1 字节），基地址为串首字符的地址。
数组（Array）的基本概念
数组定义：数组是由类型相同的数据元素构成的有序集合，元素通过下标（索引）访问。数组可以是多维的（如一维、二维、三维）。
数组元素地址计算
通用假设：
二维数组 (A) 的行下标范围 ([l_r..h_r])，列下标范围 ([l_c..h_c])。
总行数 (m = h_r – l_r + 1)，总列数 (n = h_c – l_c + 1)。
基地址 (BA) 为 (A[l_r, l_c]) 的地址（即第一个元素地址）。
每个元素占 (L) 个存储单元。
地址计算公式基于偏移量（从基地址开始的元素个数偏移），再乘以 (L) 得到字节偏移。
行序主序（Row-major Order）：先行后列存储（C/C++、Python 等语言默认）。
公式:LOC(i,j)=BA+[(i-lr)*n+(j-lc)] *L
列序主序（Column-major Order）：先列后行存储（Fortran、MATLAB 等语言默认）。
公式：LOC(i,j)=BA+[(j-lc)*m+(i-lr)] *L
树和二叉树
树是n个节点的有序集
结点
树中的一个独立单元
包含一个数据元素及若干指向其子树的分支
结点的度
结点拥有的子树数称为结点的度
树的度
树的度是树内各结点度的最大值
叶子（终端结点）
度为0的结点称为叶子或终端结点
非终端结点（分支结点/内部结点）
度不为0的结点称为非终端结点或分支结点
除根结点之外，非终端结点也称为内部结点
双亲和孩子
结点的子树的根称为该结点的孩子
相应地，该结点称为孩子的双亲
兄弟
同一个双亲的孩子之间互称兄弟
祖先
从根到该结点所经分支上的所有结点
子孙
以某结点为根的子树中的任一结点都称为该结点的子孙
层次
结点的层次从根开始定义起，根为第一层
根的孩子为第二层
树中任一结点的层次等于其双亲结点的层次加1
堂兄弟
双亲在同一层的结点互为堂兄弟
树的深度（高度）
树中结点的最大层次称为树的深度或高度
有序树和无序树
有序树：将树中结点的各子树看成从左至右是有次序的（不能互换）的树
无序树：子树之间可以互换位置的树
在有序树中，最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子
森林
是m（m≥0）棵互不相交的树的集合
对树中每个结点而言，其子树的集合即为森林
也可以用森林和树相互递归的定义来描述树
任何一棵树都是一个二元组Tree=(root, F)
root：数据元素，称作树的根结点
F：是m（m≥0）棵树的森林，F=(T₁, T₂, …, Tₘ)
其中Tᵢ=(rᵢ, Fᵢ)称作根root的第i棵子树
当m≠0时，在树根和其子树森林之间存在如下关系：
RF = {<root, rᵢ> | i=1,2,⋯,m, m>0}
满二叉树:结点全满
完全二叉树:只有最后一层允许有空，且结点全部集中在左侧
若度为2的结点有N2个，则叶子数为N2+1个
性质 1：第 (i) 层的结点数上限
陈述：在二叉树的第 (i) 层上至多有 (2^{i-1}) 个结点（(i \geq 1)）。
详细解释：
二叉树的层级从根结点开始计数（根为第 1 层）。
每个结点最多有两个子结点，因此第 (i) 层的结点数由第 (i-1) 层的结点数决定。
性质 2：深度为 (k) 的二叉树结点总数上限
陈述：深度为 (k) 的二叉树至多有 (2^k – 1) 个结点（(k \geq 1)）。
详细解释：
深度 (k) 表示从根结点到最远叶子结点的路径长度（根深度为 1）。
性质 3：终端结点与度 2 结点的关系
陈述：对任何一棵二叉树 (T)，若终端结点（叶子结点）数为 (n_0)，度为 2 的结点数为 (n_2)，则 (n_0 = n_2 + 1)。
二、完全二叉树的定义与特点
定义
深度为 (k)、有 (n) 个结点的二叉树，当且仅当其每一个结点都与深度为 (k) 的满二叉树中编号从 1 至 (n) 的结点一一对应时，称为完全二叉树。
核心特征：
结点按层序（从上到下、从左到右）编号后，无“空缺”位置。
示例：深度为 4 的完全二叉树，其结点编号连续覆盖满二叉树的前 (n) 个位置。
完全二叉树的特点
叶子结点分布：
叶子结点只可能在层次最大的两层上出现（即最底层和次底层）。
原因：若某结点在非最大层次且无子结点，则其右侧或下层必然存在空缺，违反完全二叉树定义。
子树层次约束：
对任一结点，若其右子树的最大层次为 (l)，则其左子树的最大层次必为 (l) 或 (l+1)。
原因：层序编号要求左子树优先填满，右子树层次不能超过左子树超过 1 层。
三、完全二叉树的性质
性质 4：深度计算公式
陈述：具有 (n) 个结点的完全二叉树的深度为 (log_2 n + 1)。
性质 5：层序编号的结点关系
陈述：对 (n) 个结点的完全二叉树（深度为 log_2 n + 1)），按层序编号（从第 1 层到第 (log_2 n + 1) 层，每层从左到右），对任一结点 (i)（1<=i<=n）：
关系
条件
结论
双亲结点
(i > 1)
双亲为 (i/2)
左孩子结点
(2i <=n)
左孩子为 (2i)
右孩子结点
(2i + 1 <= n)
右孩子为 (2i + 1)
无左孩子
(2i > n)
无左孩子
无右孩子
(2i + 1 > n)
无右孩子
线索化二叉树原理:[lchild,LTag,data,RTag,rchild]，就是具象化其中一种遍历过程，使得遍历过程可以使用链表表示，先遍历，再构造
LTag:0(有左孩子就代表lchild指针指向左孩子) 1(没有左孩子就代表lchild指针指向遍历时上一个元素->>即二叉树中对应的某个结点)
RTag:0(有有孩子就代表rchild指针指向右孩子) 1(没有右孩子就代表rchild指针指向遍历时下一个元素->>即二叉树中对应的某个结点)
树、二叉树与森林的相互转换
树转换为二叉树（长子-长兄法）
转换步骤：
连接兄弟：将树中每个结点的兄弟结点从左到右连接起来
保留父子，删除其他：仅保留每个结点与其第一个孩子的连线，删除与其他孩子的连线
旋转调整：将所有兄弟连接线顺时针旋转45°，使其成为右孩子指针
操作口诀：
"左孩子，右兄弟；兄弟相连转45°"
"只认第一个孩子，其他都变兄弟"
图示说明：
原始树： 转换后二叉树：
A A
/|\ /
B C D B
/| |\ → / \
E F G H E C
\ \
F D
/ \
G H
二叉树转换为普通树
转换步骤：
右孩子变兄弟：将二叉树中所有右孩子指针转换为兄弟关系
恢复父子关系：将所有通过右指针连接的结点重新连接到其父结点
调整结构：恢复原树的层次结构
操作口诀：
"左为子，右为兄；恢复层次结构"
"右子树全变兄弟，重新认爹"
图示说明：
二叉树： 恢复的普通树：
A A
/ /|\
B B C D
/ \ /| |\
E C E F G H
\ \
F D
/ \
G H
三、森林与二叉树的转换
森林转换为二叉树
转换步骤：
每棵树转二叉树：将森林中的每棵树分别转换为二叉树
连接根结点：将第一棵树的根作为新二叉树的根，第二棵树的根作为第一棵树根的右孩子，第三棵树作为第二棵树根的右孩子，依此类推
形成整体：所有树的根结点形成一个右斜链表
操作口诀：
"各自转，根连根；第一棵为根，其他作右子树"
"根根相连成斜线"
图示说明：
森林(两棵树)： 转换后二叉树：
A D A
/ \ \ / \
B C E B D
/ \ \
C (空) E
二叉树转换为森林
转换步骤：
断开右链：从二叉树根开始，不断断开根的右孩子连接
恢复每棵树：每次断开后，将剩余部分转换为普通树
集合形成森林：所有恢复的树组成森林
操作口诀：
"断右链，分森林；右子树即新树"
"根的右子树是下一棵树的根"
记忆口诀：
"树转二叉：左孩子，右兄弟"
"二叉转树：右子树，变兄弟"
"森林转二叉：第一棵为根，其余作右子树"
"二叉转森林：根的右子树，棵棵是新树"
路径
树中从一个结点到另一个结点的分支序列构成两结点间的路径。
路径长度
路径上包含的分支（边）数量，即两结点间的边数。
树的路径长度
从树根到所有结点的路径长度之和（包含非叶子结点）。
权
对实体属性的数值化描述。在树结构中，分为结点权（结点属性）和边权（边属性），具体含义由应用场景决定。
结点的带权路径长度
该结点到树根的路径长度与其权值的乘积。
树的带权路径长度（WPL）
所有叶子结点的带权路径长度之和，公式表示为：
其中 w_k 为叶子结点权值，l_k 为路径长度，n 为叶子结点总数。
哈夫曼树（最优二叉树）
定义：给定 m个权值(w1-wm)构造含 n 个叶子结点（n = m）的二叉树，其中带权路径长度 WPL 最小的树称为哈夫曼树。
核心特性：通过贪心算法构造，确保高频权值结点路径最短，广泛应用于数据压缩（如哈夫曼编码）。
图
图的顶点集不能为空，边集可以为空
度指该顶点的边数
有向图指边有方向，使用<A,B>来表示边，且<A,B>!=<B,A>
无向图指边无方向，使用(A,B)来表示边，且(A,B)==(B,A)
(1) 子图
专业描述：设存在两个图 G=(V,E) 和 G'=(V',E')，若满足 V'⊆V 且 E'⊆E，则称 G' 为 G 的子图。
通俗解释：子图是从原图中"选取"的一部分，只保留原图的部分顶点及与这些顶点相关的边，不能包含原图中不存在的顶点或边。
(2) 无向完全图和有向完全图
专业描述：对于无向图，若具有 n(n-1)/2 条边，则称为无向完全图；对于有向图，若具有 n(n-1) 条弧，则称为有向完全图。
通俗解释：无向完全图中任意两个顶点之间都有边相连；有向完全图中任意两个顶点之间都有两个方向的弧相连（双向连接）。
(3) 稀疏图和稠密图
专业描述：边或弧的数量很少（如 e<nlog₂n）的图称为稀疏图，反之称为稠密图。
通俗解释：稀疏图是顶点之间连接较少、结构松散的图；稠密图则是顶点之间连接紧密、边数较多的图。
(4) 权和网
专业描述：在实际应用中，每条边可标上具有特定含义的数值，该数值称为边上的权，可用于表示顶点间距离或耗费。这种带权的图称为网。
通俗解释：权相当于给图中的边"标价"，表示通过这条边的代价（如距离、时间、费用）；带有这些"价格"的图就是网。
(5) 邻接点
专业描述：在无向图 G 中，若边 (v,v')∈E，则称顶点 v 和 v' 互为邻接点，即 v 和 v' 相邻接。边 (v,v') 依附于顶点 v 和 v'。
通俗解释：如果两个顶点之间有边直接相连，它们就是"邻居"，称为邻接点。
(6) 度、入度和出度
专业描述：顶点 v 的度是与 v 相关联的边的数目，记为 TD(v)。对于有向图，顶点 v 的度分为入度 ID(v)（以 v 为头的弧数）和出度 OD(v)（以 v 为尾的弧数），满足 TD(v)=ID(v)+OD(v)。
通俗解释：度是与一个顶点相连的边的总数；入度是从其他顶点指向该顶点的边数，出度是从该顶点指向其他顶点的边数。
(7) 路径和路径长度
专业描述：在无向图中，从顶点 v 到 v' 的路径是顶点序列 (v=vᵢ,₀, vᵢ,₁,⋯, vᵢ,ₘ=v')，其中每对连续顶点间有边相连。路径长度是路径上边或弧的数量。
通俗解释：路径是从一个点到另一个点的行走路线；路径长度就是这条路线中经过了多少条边。
(8) 回路或环
专业描述：第一个顶点和最后一个顶点相同的路径称为回路或环。
通俗解释：回路是一条"绕圈"的路径，从某点出发后最终又回到起点。
(9) 简单路径、简单回路或简单环
专业描述：顶点不重复的路径称为简单路径；除首尾顶点外其余顶点不重复的回路称为简单回路或简单环。
通俗解释：简单路径是不重复经过任何顶点的路线；简单回路是除起点终点重合外，中间不重复经过任何顶点的环。
(10) 连通、连通图和连通分量
专业描述：在无向图中，若从顶点 v 到 v' 有路径，则称 v 和 v' 连通。若任意两个顶点都连通，则称图是连通图。连通分量是无向图中的极大连通子图。
通俗解释：连通指两点间有路可走；连通图是指图中任意两点都有路可走；连通分量是图中不能进一步扩展的"连成一片"的部分。
(11) 强连通图和强连通分量
专业描述：在有向图中，若任意两个不同顶点间都存在双向路径，则称图是强连通图。有向图中的极大强连通子图称为强连通分量。
通俗解释：强连通图是指有向图中任意两点间都能"双向通行"；强连通分量是有向图中不能进一步扩展的"双向连通"子图。
(12) 连通图的生成树
专业描述：含有图中全部顶点且仅有 n-1 条边的极小连通子图称为生成树。n 个顶点的生成树有且仅有 n-1 条边。
通俗解释：生成树是将图"简化"成树的结构，保留所有顶点但只保留最少边数（n-1条），确保所有点连通且无环。
(13) 有向树和生成森林
专业描述：有一个顶点入度为 0，其余顶点入度均为 1 的有向图称为有向树。有向图的生成森林由若干棵有向树组成，包含图中全部顶点。
通俗解释：有向树是一种特殊有向图，只有一个"根"顶点没有箭头指向它，其他顶点都只有一个箭头指向它们；生成森林是由多棵这样的有向树组成的集合。
AOE网:有向无环图(有方向->指箭头 没有环结构)
拓扑排序:每次找出当前AOE网中没有入度的结点，输出并删除，只到全部结点输出
查找
顺序查找:在顺序表中从前向后查找
折半查找(针对有序顺序表)(相当于二分查找):
1.绘制判定树(一般是左孩子小于根节点，右孩子大于根节点)
2.从中间开始查找，等于当前元素则退出，如果小于当前元素，递归查找左子树，否则递归查找右子树
二叉排序树为空树，或满足：左子树所有结点值均小于根结点值，右子树所有结点值均大于根结点值，且左右子树均为二叉排序树。
二叉排序树查找:当前值等于查找值->输出指针；当前值大于查找值->在左子树递归查找；当前值小于查找值->在右子树递归查找
二叉排序树创建和插入:新建一棵空树(创建);当二叉树T中不存在插入元素时新建结点，左右孩子置空，作为T返回；否则如果小于当前结点数据，递归插入到左子树；否则如果大于当前结点数据，递归插入到右子树
二叉排序树删除结点
核心原则：删除后仍保持二叉排序树性质（左子树 < 根 < 右子树）。分三种情况处理：
1. 无子结点（叶子结点）
操作：直接删除该结点。
调整：将其父结点的对应子指针置空。
示例：删除结点 3（无子结点），父结点 2 的右指针置空。
2. 仅有一个子结点
操作：用其唯一子结点替代自身位置。
调整：
父结点的指针指向被删结点的子结点。
释放被删结点内存。
示例：删除结点 2（仅有右子 3），父结点 1 的右指针指向 3。
3. 有两个子结点
核心技巧：用中序后继（或中序前驱）替代被删结点。
中序后继 = 右子树中最小关键字的结点（即右子树最左结点）。
中序前驱 = 左子树中最大关键字的结点（即左子树最右结点）。
操作步骤：
查找替代结点：在右子树中找到最小关键字结点 S（中序后继）。
复制数据：将 S 的关键字值复制到被删结点 P。
转为简单删除：递归删除原 S 结点（此时 S 必为 情况1或2，因其无左子树）。
关键：
不直接删除 P，而是用 S 的值覆盖 P，再删除 S。
保证树结构平衡性（避免破坏BST性质）。
示例：
删除根结点 50（有左右子树）。
右子树最小结点为 60 → 将 60 复制到根 → 删除原 60 结点（此时 60 无左子树，属情况2）。
平衡二叉树、B-树、B+树、红黑树详解
1. 平衡二叉树（AVL树）
定义规则：
二叉搜索树（BST）的每个节点的左子树与右子树高度差（平衡因子）的绝对值不超过1。
平衡因子定义：BF = height(left) – height(right)，取值范围为{-1, 0, 1}。
树高为O(log n)，保证操作效率。
插入过程：
按BST规则插入新节点。
从插入点回溯至根，更新路径上各节点的平衡因子。
若发现失衡节点（|BF| > 1），执行旋转调整：
LL型（左子树左倾）：单右旋。
RR型（右子树右倾）：单左旋。
LR型（左子树右倾）：先左旋后右旋。
RL型（右子树左倾）：先右旋后左旋。
调整过程：
旋转操作：
右旋（LL型）：失衡节点A的左子节点B成为新根，A成为B的右子节点，B原右子树挂载到A左子树。
左旋（RR型）：对称处理。
双旋（LR/RL型）：先对子树旋转转为LL/RR型，再执行单旋。
调整后需更新相关节点高度及平衡因子。
查找过程：
与BST相同：从根开始，若key小于当前节点则搜索左子树，大于则搜索右子树，等于则返回。时间复杂度O(log n)。
删除过程：
按BST规则删除节点（分三类：无子节点、单子节点、双子节点）。
从删除点回溯至根，更新平衡因子。
遇到失衡节点时，根据子树平衡因子执行旋转（规则同插入，但可能需多次调整）。
删除可能导致多级失衡，需持续回溯调整。
2. B-树（B树）
定义规则（m阶B-树）：
每个节点最多含m-1个关键字、m个子树指针。
根节点至少2个子树（除非是叶节点）；非根非叶节点至少⌈m/2⌉个子树。
所有叶节点在同一层。
节点内关键字升序排列，子树指针分隔关键字范围。
插入过程：
从根开始查找插入位置（叶节点）。
若叶节点未满（关键字数 < m-1），直接插入并排序。
若叶节点满：
分裂节点：中间关键字上移至父节点，原节点分裂为左右两子节点。
若父节点满，递归分裂直至根（根分裂时树高增1）。
调整过程：
分裂：节点满时，取中间关键字k，左半关键字+左子树构成新左节点，右半构成新右节点，k插入父节点。
合并（删除时用）：兄弟节点不满时，与父节点关键字及另一兄弟合并。
查找过程：
从根开始，顺序查找节点内关键字：
若key等于当前关键字，返回。
若key小于首个关键字，搜索最左子树。
否则，找到首个大于key的关键字，搜索其左子树。
时间复杂度O(log_m n)。
删除过程：
定位待删关键字（若在非叶节点，用后继/前驱替换至叶节点）。
从叶节点删除关键字：
若节点关键字数 ≥ ⌈m/2⌉，直接删除。
否则，尝试从兄弟节点借关键字：
若兄弟节点关键字数 > ⌈m/2⌉-1，父节点下移关键字，兄弟节点上移关键字。
若无法借，则与兄弟节点及父节点关键字合并，递归调整父节点。
3. B+树
定义规则（m阶B+树）：
非叶节点仅含索引关键字（无数据），叶节点含所有关键字及数据指针。
叶节点通过指针链接成双向链表。
非叶节点关键字数k满足：⌈m/2⌉ ≤ k+1 ≤ m（子树数）。
叶节点关键字数k满足：⌈m/2⌉ ≤ k ≤ m。
每个非叶节点关键字是其子树最大关键字的复制。
插入过程：
与B-树类似，定位至叶节点插入。
若叶节点满，分裂为两节点，左节点满，右节点含剩余关键字。
将右节点最小关键字复制至父节点（而非上移），父节点调整同B-树。
若父节点满，递归分裂。
调整过程：
分裂：叶节点分裂时，复制分裂点关键字至父节点；非叶节点分裂同B-树。
合并：删除时若叶节点不满，优先从兄弟借关键字；否则合并兄弟节点，更新父节点。
查找过程：
从根开始，按关键字范围搜索至叶节点。
范围查询高效：通过叶节点链表顺序访问。
时间复杂度O(log_m n)。
删除过程：
定位关键字至叶节点删除。
调整：
若叶节点关键字数 ≥ ⌈m/2⌉，结束。
否则，尝试从左/右兄弟借关键字（更新父节点索引）。
若无法借，则合并自身与兄弟节点，删除父节点对应关键字，递归调整。
4. 红黑树
定义规则：
每个节点为红或黑。
根节点为黑。
叶节点（NIL）为黑。
红节点子节点必为黑（无连续红节点）。
任一节点到叶节点的路径含相同数目的黑节点（黑高平衡）。
插入过程：
按BST插入新节点（默认设为红）。
修复性质：
Case 1：父节点黑，结束。
Case 2：父节点红，叔节点红：父/叔变黑，祖父变红，递归检查祖父。
Case 3：父节点红，叔节点黑：
LL/RR型：父节点变黑，祖父变红，旋转（右旋/左旋）。
LR/RL型：先旋转转为LL/RR型，再处理。
调整过程：
旋转：同AVL树，但结合颜色翻转。
颜色翻转：Case 2中批量调整颜色；Case 3中旋转后调整颜色。
调整确保黑高不变，且无连续红节点。
查找过程：
同BST，忽略颜色。时间复杂度O(log n)。
删除过程：
按BST删除节点（若双子节点，用后继替换）。
若删除黑节点，可能导致黑高失衡，执行修复：
Case 1：兄弟节点红：旋转使兄弟变黑，父变红，转Case 2。
Case 2：兄弟黑且子节点全黑：兄弟变红，递归修复父节点。
Case 3：兄弟黑，近侄子红：旋转调整，转Case 4。
Case 4：兄弟黑，远侄子红：兄弟变父颜色，父/远侄子变黑，旋转。
散列表、散列函数及相关技术详解
散列表（Hash Table）
概念：基于键值对（Key-Value）存储的数据结构，通过散列函数将键映射到固定大小的数组位置，实现平均时间复杂度 O(1) 的查找、插入和删除。
适用范围：
高频查找场景（如数据库索引、缓存系统）
需要快速去重（如布隆过滤器）
内存充足且键分布均匀的场景
核心挑战：冲突（Collision） —— 不同键映射到相同位置。
散列函数（Hash Function）
概念：将任意大小的键转换为固定范围整数（散列地址）的函数。
要求：
确定性：相同输入始终输出相同结果
均匀分布：最小化冲突概率
高效计算：时间复杂度 O(1)
常用方法：
除留余数法：H(key) = key % p（p 为质数，如 11、101）
折叠法：将键分段后叠加（如电话号码 13812345678 → 138+123+456+78=795）
平方取中法：取 key² 的中间几位（如 123²=15129 → 取 512）
手算举例（除留余数法）：
键集合 {17, 60, 29, 45}，表长 p=11：
17 % 11 = 6，60 % 11 = 5，29 % 11 = 7，45 % 11 = 1
冲突解决方法
(1) 开放地址法（Open Addressing）
概念：所有元素存储在散列表数组中，冲突时通过探测序列寻找下一个空位。
适用范围：内存受限、装填因子（α = 元素数/表长）< 0.7 时高效。
关键规则：删除需标记DELETED（避免破坏探测链）。
a. 线性探测法（Linear Probing）
探测序列：H_i = (H(key) + i) % m（i=1,2,…,m-1）
手算举例：
表长 m=11，键 {17, 60, 29, 45, 38}（38 % 11 = 5，但位置 5 已被 60 占用）：
i=1：(5+1)%11=6（17 占用）
i=2：(5+2)%11=7（29 占用）
i=3：(5+3)%11=8（空位）→ 38 存入位置 8
缺点：一次聚集（Primary Clustering） —— 连续占用导致探测链变长。
b. 二次探测法（Quadratic Probing）
探测序列：H_i = (H(key) + c1·i + c2·i²) % m（常用 c1=0, c2=1 → H_i = (H(key) + i²) % m）
要求：表长 m 为质数且 m ≡ 3 mod 4（如 11, 19）
手算举例：
键 38 冲突于位置 5：
i=1：(5+1²)%11=6（冲突）
i=2：(5+2²)%11=9（空位）→ 38 存入位置 9
优点：缓解一次聚集。
缺点：二次聚集（Secondary Clustering） —— 相同初始位置的键探测序列相同。
c. 伪随机探测法（Pseudo-random Probing）
探测序列：H_i = (H(key) + rand(i)) % m，rand(i) 由固定种子生成的伪随机序列。
手算举例：
伪随机序列 {3,1,4,2}，键 38 冲突于位置 5：
i=1：(5+3)%11=8（空位）→ 38 存入位置 8
优点：探测序列随机化，冲突概率更低。
(2) 链地址法（Separate Chaining）
概念：每个散列位置维护一个链表，冲突键存入同义词链表。
适用范围：装填因子 α > 1 时仍高效（如 Java HashMap）。
手算举例：
表长 m=5，键 {5, 21, 8, 15}（H(key)=key%5）：
位置 0：15 → null
位置 1：21 → null
位置 3：8 → null
位置 0 的链表：5 → 15（5%5=0, 15%5=0）
优点：无聚集问题，删除简单（直接移除链表节点）。
缺点：额外指针内存开销。
方法对比与选择
方法
优点
缺点
适用场景
线性探测
内存连续，缓存友好
一次聚集，删除复杂
小数据集、内存受限
二次探测
缓解聚集
二次聚集，表长限制严格
中等规模、冲突较少
链地址法
无聚集，删除简单
指针内存开销大
大规模数据、高冲突场景
排序
一、直接插入排序
思路
将数组分为已排序区和未排序区
从未排序区取出首元素，在已排序区从后向前扫描
将大于该元素的已排序元素后移，找到插入位置
时间复杂度：O(n²)（平均/最坏），O(n)（最好）
稳定性：稳定（相同元素相对位置不变）
过程演示（每趟状态）
初始: [12], 2, 16, 30, 28, 10, 16*, 20, 6, 18
第1趟: [2, 12], 16, 30, 28, 10, 16*, 20, 6, 18 (插入2)
第2趟: [2, 12, 16], 30, 28, 10, 16*, 20, 6, 18 (插入16)
第3趟: [2, 12, 16, 30], 28, 10, 16*, 20, 6, 18 (插入30)
第4趟: [2, 12, 16, 28, 30], 10, 16*, 20, 6, 18 (插入28)
第5趟: [2, 10, 12, 16, 28, 30], 16*, 20, 6, 18 (插入10)
第6趟: [2, 10, 12, 16, 16*, 28, 30], 20, 6, 18 (插入16*，保持16*在16后)
第7趟: [2, 10, 12, 16, 16*, 20, 28, 30], 6, 18 (插入20)
第8趟: [2, 6, 10, 12, 16, 16*, 20, 28, 30], 18 (插入6)
第9趟: [2, 6, 10, 12, 16, 16*, 18, 20, 28, 30] (插入18)
二、希尔排序
思路
分组插入排序：按增量序列(gap)分组
每组内进行插入排序
增量序列递减（如5→3→1），最后gap=1时完成精细排序
时间复杂度：O(n log²n)（依赖增量序列）
稳定性：不稳定（跨组交换破坏稳定性）
过程演示（增量5→3→1）
初始: 12, 2, 16, 30, 28, 10, 16*, 20, 6, 18
增量5分组: [12,10], [2,16*], [16,20], [30,6], [28,18]
增量5排序: 10, 2, 16, 6, 18, 12, 16*, 20, 30, 28
增量3分组: [10,6,16*,28], [2,18,20], [16,12,30]
增量3排序: 6, 2, 12, 10, 18, 16, 16*, 20, 30, 28
增量1分组: 整个序列
增量1排序: 2, 6, 10, 12, 16, 16*, 18, 20, 28, 30
三、冒泡排序
思路
重复遍历未排序区，比较相邻元素
逆序则交换，每趟将最大元素沉底
优化：设置交换标志，若一趟无交换则提前终止
时间复杂度：O(n²)（平均/最坏），O(n)（最好）
稳定性：稳定
过程演示（每趟沉底最大元素）
初始: 12, 2, 16, 30, 28, 10, 16*, 20, 6, 18
第1趟: 2, 12, 16, 28, 10, 16*, 20, 6, 18, 30 (30沉底)
第2趟: 2, 12, 16, 10, 16*, 20, 6, 18, 28, 30 (28沉底)
第3趟: 2, 12, 10, 16, 16*, 6, 18, 20, 28, 30 (20沉底)
第4趟: 2, 10, 12, 6, 16, 16*, 18, 20, 28, 30 (18沉底)
第5趟: 2, 10, 6, 12, 16, 16*, 18, 20, 28, 30 (16*沉底)
第6趟: 2, 6, 10, 12, 16, 16*, 18, 20, 28, 30 (6沉底，已有序)
四、快速排序
思路
分治策略：选基准(pivot)，分区(partition)
小于基准放左，大于基准放右
递归处理左右子区间
时间复杂度：O(n log n)（平均），O(n²)（最坏）
稳定性：不稳定（分区交换破坏稳定性）
过程演示（首元素为基准）
初始: 12, 2, 16, 30, 28, 10, 16*, 20, 6, 18
第1趟(基准12): 10, 2, 6, 12, 28, 30, 16*, 20, 16, 18
第2趟(左子列基准10): 6, 2, 10, 12, 28, 30, 16*, 20, 16, 18
第3趟(右子列基准28): 6, 2, 10, 12, 16, 18, 16*, 20, 28, 30
第4趟(左子列基准6): 2, 6, 10, 12, 16, 18, 16*, 20, 28, 30
第5趟(右子列基准16): 2, 6, 10, 12, 16, 16*, 18, 20, 28, 30 (完成)
五、简单选择排序
思路
每趟从未排序区选择最小元素
与未排序区首元素交换
逐步扩大已排序区
时间复杂度：O(n²)（始终）
稳定性：不稳定（交换可能破坏相同元素相对位置）
过程演示（每趟选择最小元素）
初始: [12], 2, 16, 30, 28, 10, 16*, 20, 6, 18
第1趟: [6], 2, 16, 30, 28, 10, 16*, 20, 12, 18 (选6，与12交换)
第2趟: [6, 2], 16, 30, 28, 10, 16*, 20, 12, 18 (选2，已在位)
第3趟: [6, 2, 10], 30, 28, 16, 16*, 20, 12, 18 (选10，与16交换)
第4趟: [6, 2, 10, 12], 28, 16, 16*, 20, 30, 18 (选12，与30交换)
第5趟: [6, 2, 10, 12, 16], 28, 16*, 20, 30, 18 (选16，与28交换，保持16*在16后)
第6趟: [6, 2, 10, 12, 16, 16*], 28, 20, 30, 18 (选16*，已在位)
第7趟: [6, 2, 10, 12, 16, 16*, 18], 20, 30, 28 (选18，与28交换)
第8趟: [6, 2, 10, 12, 16, 16*, 18, 20], 30, 28 (选20，已在位)
第9趟: [6, 2, 10, 12, 16, 16*, 18, 20, 28], 30 (选28，与30交换)
六、堆排序
思路
建最大堆：父节点≥子节点
将堆顶(最大值)与末尾交换
调整剩余元素为最大堆
重复上述过程
时间复杂度：O(n log n)（始终）
稳定性：不稳定
过程演示（最大堆）
初始序列: 12, 2, 16, 30, 28, 10, 16*, 20, 6, 18
初始建堆: 30, 28, 16, 20, 18, 10, 16*, 2, 6, 12
第1趟: 28, 20, 16, 12, 18, 10, 16*, 2, 6, 30 (30归位)
第2趟: 20, 18, 16, 12, 6, 10, 16*, 2, 28, 30 (28,30归位)
第3趟: 18, 12, 16, 6, 2, 10, 16*, 20, 28, 30 (20,28,30归位)
第4趟: 16*, 12, 16, 6, 2, 10, 18, 20, 28, 30 (18,20,28,30归位)
第5趟: 12, 10, 16, 6, 2, 16*, 18, 20, 28, 30 (16*,18,20,28,30归位)
第6趟: 10, 6, 16, 2, 12, 16*, 18, 20, 28, 30 (12,16*,18,20,28,30归位)
第7趟: 6, 2, 16, 10, 12, 16*, 18, 20, 28, 30 (10,12,16*,18,20,28,30归位)
第8趟: 2, 6, 16, 10, 12, 16*, 18, 20, 28, 30 → 调整: 16, 2, 6, 10, 12, 16*, 18, 20, 28, 30 (6,10,…归位)
第9趟: 2, 16, 6, 10, 12, 16*, 18, 20, 28, 30 → 2,6,10,12,16,16*,18,20,28,30 (完成)
七、关键特性对比
排序算法
时间复杂度(平均)
空间复杂度
稳定性
优势场景
直接插入排序
O(n²)
O(1)
稳定
小规模/基本有序数据
希尔排序
O(n log²n)
O(1)
不稳定
中等规模数据
冒泡排序
O(n²)
O(1)
稳定
教学演示/小数据
快速排序
O(n log n)
O(log n)
不稳定
通用场景(平均性能最优)
选择排序
O(n²)
O(1)
不稳定
交换操作代价高的场景
堆排序
O(n log n)
O(1)
不稳定
大数据量/内存受限/实时系统
八、稳定性的重要性
稳定排序：相同值元素保持原始相对顺序（如16在16*前）
应用场景：多关键字排序（如先按班级排，再按成绩排）
本例中：直接插入、冒泡、归并排序保持16*在16后
不稳定排序：可能改变相同值元素的相对顺序
本例中：希尔、快速、选择、堆排序可能使16*出现在16前
注：实际代码实现中，需通过元组(值, 原始索引)或自定义对象保持稳定性，比较时优先比较值，值相等时比较原始索引。
通过本例的详细分析，可深入理解各排序算法的核心机制、执行过程和适用场景。在实际应用中，应根据数据规模、有序程度、稳定性要求和内存限制选择合适算法。
直接插入排序:每次将一个元素插入到已排好的序列中
折半插入排序:将插入时查找插入位置的方法改为折半查找
希尔排序(插入排序的优化):1.寻找增量队列 每个数组长度->从原数组长度/2开始，每次/2，直到递减为1时有序;
2.第一次每个增量序列只有两个元素，最后一次只有一个序列，包含全部元素;3.对每个序列采取插入排序
希尔排序例子:
原序列:
49,38,65,97,76,13,27,49*,55,04
第一次增量序列:[(49,13),(38,27),(65,49*),(97,55),(76,04)] (逻辑序列，物理结构不变)
直接插入排序后:13,27,49*,55,04,49,38,65,97,76
第二次增量序列:[(13,55,38,76),(27,04,65),(49*,49,97)] (逻辑序列，物理结构不变)
直接插入排序后:13,04,49*,38,27,49,55,65,97,76
冒泡排序:每次比较最小的元素从后交换到表头，只到没有交换时退出
快速排序(冒泡排序的优化):
去第一个元素作为关键字保存
low指针指向第一个元素的位置
high指针指向最后一个元素的位置
从high指针开始与关键字比较–>如果high指针的值小于关键字，high指针指向的值赋给low指针指向的位置，low指针++，low指针开始与关键字比较；否则high指针–，继续与关键字比较重复
当low指针开始与关键字比较时如果大于关键字，low指针指向的值赋给high指针指向的位置，high指针–
当low指针和high重合时，重合的位置放入关键字
此时顺序表被关键字划分为左右两个子序列
对左右两个子序列做同样的处理(递归)，只到子序列的元素个数为1时整个序列有序
选择排序:每次遍历数组找到最小的元素，与第k个元素交换(k初始为1，每次交换完成就++)。只到k=初始数组长度时排序结束
归并排序:原理:合并若干个子序列
做法1.将原数组每相邻两个元素一组划分成若干有序子序列
每两个子序列合并，重复只到没有子序列
算法实现:
初始数组:49,38,65,97,76,13,27
[49],[38],[65],[97],[76],[13],[27]
[38,49],[65,97],[13,76],[27]
[38,49,65,97],[13,27,76]
有序数组
合并算法:
初始化三个指针,head,head1,head2,
head初始指向空，head1指向数组1首元素,head2指向数组2首元素
比较head1和head2指向元素值，head指向小的那个元素，同时小的那个元素指针执行数组的下一个元素，
重复比较只到其中一个原数组遍历完成
直接将另一个数组的尾部接到head新数组尾部即可
堆排序
思想
利用堆（完全二叉树）的性质：大顶堆根节点为最大值。通过反复将堆顶元素与末尾交换，缩小堆范围，再调整堆，实现原地排序。
原理
建堆：将数组调整为大顶堆（从最后一个非叶子节点向前调整）。
交换与调整：
将堆顶（最大值）与堆末尾元素交换。
堆大小减1，调整新堆顶使剩余元素保持大顶堆性质。
重复：重复步骤2，直到堆大小为1。
手算过程（序列：4, 10, 3, 5, 1）
初始建大顶堆： [10, 5, 3, 4, 1]
交换10与1： [1, 5, 3, 4, 10] → 调整堆 → [5, 4, 3, 1, 10]
交换5与1： [1, 4, 3, 5, 10] → 调整堆 → [4, 1, 3, 5, 10]
交换4与3： [3, 1, 4, 5, 10] → 调整堆 → [3, 1, 4, 5, 10]
交换3与1： [1, 3, 4, 5, 10] → 完成
最终序列：1, 3, 4, 5, 10
基数排序
思想
非比较排序，按位（个、十、百…）分配元素到桶中，再按桶顺序收集，从低位到高位重复，直到最高位有序。
原理
确定位数：找到最大元素，计算最大位数。
分配与收集：
从最低位（LSD）开始，按当前位数字0-9分配到10个桶中。
按桶0到9的顺序收集元素，形成新序列。
重复：处理更高位，直到最高位。
手算过程（序列：170, 45, 75, 90, 802, 24, 2, 66）
个位分配：
0: 170,90 → 2: 802,2 → 4:24 → 5:45,75 → 6:66
收集：170,90,802,2,24,45,75,66
十位分配：
0: 802,2 → 2:24 → 4:45 → 6:66 → 7:170,75 → 9:90
收集：802,2,24,45,66,170,75,90
百位分配：
0: 2,24,45,66,75,90 → 1:170 → 8:802
收集：2,24,45,66,75,90,170,802（有序）
关键总结
算法
核心思想
时间复杂度
空间复杂度
适用场景
树形选择排序
胜者树减少重复比较
O(n log n)
O(n)
理论教学，少实用
堆排序
大顶堆原地排序
O(n log n)
O(1)
内存受限，需稳定复杂度
基数排序
按位分配收集（LSD）
O(d·(n+k))
O(n+k)
整数，位数少
外部排序
分块内排 + 多路归并
I/O密集
O(k)
超大文件（TB级）