红黑树

平衡二叉树在插入和删除时，很容易破坏“平衡”特性，需要频繁调整树的形态

红黑树的性能尽管和平衡二叉树差不多，但可以在插入和删除后仅进行变色而不旋转，减少了时间开销

红黑树适用于频繁插入和删除的场景

红黑树的定义

红黑树是首先二叉排序树，满足：左子树结点值<=根结点值<=右子树结点值

与普通的二叉排序树相比，需要增加的要求：

每个结点是红色或者黑色的
根结点是黑色的
叶结点（NULL结点）均是黑色的
不存在两个相邻的红色结点（即红色结点的父结点和子结点均是黑色）
对每个结点，从该结点到任一叶结点的简单路径上，所含黑色结点的数目相同

性质1：从根结点到叶结点的最长路径不大于最短路径的2倍（最长路径就是红黑结点交替出现，最短路径就是只有黑结点）

性质2：有n个内部结点的红黑树高度$h\leq 2\log_2(n+1)$ 红黑树查找操作时间复杂度=$O(\log_2n)$

红黑树的插入

新结点是根——染为黑色
新结点非根——先染为红色
- 若插入新结点后仍然满足红黑树定义，则插入结束
- 若插入新结点后不满足红黑树定义
  - 新结点的叔叔为黑：旋转+染色
  - 新结点的叔叔为红：染色+变新

第一章

时间复杂度

T(n)是指算法中所有语句的执行次数之和

人们关心的是n趋于无穷时T(n)的数量级，而非准确大小

T(n)与算法中基本运算的频度f(n)同数量级，因此通常采用基本运算的频度的数量级O(f(n))来分析算法的时间复杂度，记为T(n)=O(f(n))

空间复杂度

空间复杂度S(n)是指算法运行过程中所使用的的辅助空间的大小

算法原地工作是指算法所需辅助空间是常量，即O(1)

第二章

顺序表、链表

逻辑结构：都是线性表

物理结构：顺序表：顺序存储，具有随机存取的特性链表：链式存储

第三章

栈和队列

性质栈：后进先出队列：先进先出

对于n个不同元素进栈，出栈序列为$\frac{1}{n+1}C^n_{2n}$个

循环队列

队列的应用：二叉树的层序遍历

栈的应用：中缀表达式转后缀表达式

第五章

树的基本性质

结点的度：树中一个结点的子结点个数

树的度：结点的度的最大值

结点总数=总度数+1

二叉树的性质

完全二叉树：最底层最右边缺少了一些连续叶子结点

满二叉树：每一层结点数都达到了最大值

二叉树的顺序存储

一定要把二叉树的结点编号与完全二叉树对应起来

二叉树的遍历

先序遍历：根左右中序遍历：左根右后序遍历：左右根

可以唯一确定一棵二叉树的序列组合（都需要中序序列）：

中序序列与先序序列
中序序列与后序序列
中序序列与层序序列

二叉树的层序遍历

根节点入队
若队空（所有节点都已处理完毕），则结束遍历；否则重复3.操作
队列中第一个节点出队，并访问。若其有左子，则将左子入队；若其有右子，则将右子入队，返回

二叉排序树

左子树结点值<根结点值<右子树结点值

中序遍历可以得到一个递增的有序序列

在二叉排序树中删除后又插入同一节点，得到的二叉排序树和原来不一定相同

平衡二叉树

左右子树高度差绝对值不超过1

LL旋转（右单旋转）
RR旋转（左单旋转）
LR旋转（先左后右双旋转）
RL旋转（先右后左双旋转）

树、森林、二叉树的遍历对应关系

线索二叉树

二叉树线索化时，若无左子树，令lchild指向前驱结点，若无右子树，令rchild指向后继结点

哈夫曼树

带权路径长度最小的二叉树

哈夫曼树的构造

给定n个结点

将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F
构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左右子树，并且将新结点的权值置位左右子树上根结点的权值之和
从F中删除选出的两棵树，同时将新得到的树加入F中
重复步骤2和3，直至F中只剩下一棵树为止

第六章图

最小生成树算法

Prim算法：先取顶点。时间复杂度：O(|V|^2^)。适用于边稠密的图 Kruskal算法：先取边。时间复杂度：O(|E|log|E|)。适用于边稀疏而顶点较多的图

最短路径算法

Dijkstra算法

非负权重单点源头

贪心策略

核心思想：每次得到的最短的暂定最短路径对应的点被添加进已知

一个集合S，用于记录已求得的最短路径的顶点，用一个数组s[]来实现，初始化为0，s[vi]=1时表示将顶点$v_i$放入S，初始时把源点$v_0$放入S

两个辅助数组

dist[]: 记录从源点$v_0$到其他各顶点的最短路径长度，dist[i]的初值为arcs[v0][i]
path[]: path[i]表示从源点到顶点i之间的最短路径的前驱结点，在算法结束时，可根据其值追溯得到源点$v_0$到顶点$v_i$的最短路径

步骤

初始化
S<--{$v_0$}
dist[j]<--edge[0][j]

找最短路径
dist[j]<--min{dist[i]}
S<--S并{k}
更新
对每一个$i\in V-S$
dist[i]<--min{dist[i],dist[k]+edge[k][i]}
如果使得S=V，返回。否则重回第一步

算法复杂度为$O(|V|^2)$

不适用于于边上带有负权值的情况

Floyd算法

时间复杂度O(|V|^3^)

适用于于边上带有负权值的情况，对每对顶点$v_i\neq v_j$都求出最短路径和最短路径长度

基本思想：递推产生一个n阶方阵序列$A^{(-1)},A{(0)},...,A^{(n-1)}$，其中$A^{(k)}[i][j]$表示从顶点$v_i$到$v_j$的路径长度，k表示绕行第k个顶点的运算步骤。初始时，对于任意两个顶点$v_i$和$v_j$，若它们之间存在边，则以此边上的权值作为它们之间的最短路长度；若它们之间不存在有向边，则以$\infty$作为它们之间的最短路长度。以后逐步尝试在原路径中加入顶点k(k=0,1,...,n-1)作为中间顶点。若增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径。

算法描述：定义一个n阶方阵序列$A^{(-1)},A^{(0)},...,A^{(n-1)}$，其中 $$A^{(-1)}[i][j]=arcs[i][j]$$ $$A^{(k)}[i][j]=Min{A^{(k-1)}[i][j],A^{(k-1)}[i][k]+A^{(k-1)}[k][j]},k=0,1,...,n-1$$

式中，$A^{(0)}[i][j]$是从顶点$v_i$到$v_j$、中间顶点是$v_0$的最短路径的长度，$A^{(k)}[i][j]$是从顶点$v_i$到$v_j$、中间顶点的序号不大于k的最短路径的长度。Floyd算法是一个迭代的过程，每迭代一次，在从$v_i$到$v_j$的最短路径上就多考虑了一个顶点；经过n次迭代后，所得到的$A^{(n-1)}[i][j]$就是$v_i$到$v_j$的最短路径长度，即方阵$A^{(n-1)}$中就保存了任意一对顶点之间的最短路径长度

算法复杂度为$O(|V|^3)$

代码

for(k=1;k<=n;k++)  
    for(i=1;i<=n;i++)  
        for(j=1;j<=n;j++)  
            if(e[i][j]>e[i][k]+e[k][j])  
                e[i][j]=e[i][k]+e[k][j];

不能解决带有“负权回路”（或者叫“负权环”）的图，因为带有“负权回路”的图没有最短路

第七章查找

顺序查找、折半查找

B树、B+树

B树及其基本操作

B树，本质为m叉搜索树，有助于减少硬盘读取，m称为B树的阶

一棵m阶B树或为空树，或满足以下要求

树中每个结点至多有m棵子树（即至多含有m-1个关键字）
若根结点不是终端结点，则至少有两棵子树
除根结点外的所有非叶结点至少有[m/2]（向上取整）棵子树（即至少含有[m/2]-1个关键字）
所有非叶子结点的结构如下：

n

P0

K1

P1

K2

P2

...

Kn

Pn

其中，$K_i(i=1,2,...,n)$为结点的关键字，且满足$K_1<K_2<...<K_n$；$P_i(i=0,1,...,n)$为指向子树根结点的指针，且指针$P_{i-1}$所指子树中所有结点的关键字均小于$K_i$，$P_i$所指子树中所有结点的关键字均大于$K_i$，$n（[m/2]-1\leqslant n\leqslant m-1）$为结点中关键字的个数

所有叶子结点在同一层

B树的插入

每次都插入到叶子结点，如果结点所含关键字超过个数限制，取中间的上移，假如有偶数个，就取小的那个，如果上一层也满了，继续取中间的上移

向4阶B树中依次插入6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4，动画如下：

B树的删除

叶子结点直接删

内部结点，找下一层比它大的最小数上移至它的位置

如果删后结点关键字个数太少，打破了[m/2]-1的规则，此时如果左右兄弟结点有多余的结点，则借给它，如果没有，则从父结点借

详细情况见此链接：B树的删除操作，5种情况图解

B+树的基本概念

一种B树的变形树

一棵m阶B+树满足下列条件

每个分支结点最多有m棵子树
非叶子根结点至少有两棵子树，其他每个分支结点至少有[m/2]棵子树
结点的子树个数与关键字个数相等
所有叶子结点包含全部关键字及指向相应记录的指针，叶子结点中将关键字按大小顺序排列，并且相邻叶子结点按大小顺序相互链接起来
所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针

B+树和B树的区别在于

非叶子结点只起到索引作用，不包含具体数据
每个关键字对应一棵子树
每个结点的关键字范围为$[m/2]\leqslant n\leqslant m$
叶子结点包含了全部关键字，即在非叶子结点中出现的关键字也会出现在叶子结点中
B+树支持顺序查找，B树只能从根结点开始查找

下图为一个4阶B+树的例子

散列（哈希）

词典存储了很多的键值对，能够更快地搜索
单词名：键解释：值

散列查找比二分查找更快，拥有常数级的时间复杂度

散列表（Hash table）

支持操作：

查找
插入
删除

数据间没有线性关系，因此不支持以下操作：

求最小值或最大值
找前驱后继数据
找一个范围内的数据
按顺序列出数据

不可行的思路

全部键值和位置一一对应浪费空间

可行的思路

数据的可能取值范围为N，实际为K
散列表的大小设为大于K（多一些），小于N（远远小于）的M，即M<<N

K个数怎么存到M中

通过散列函数 $H(k)$ 计算出相应位置（散列地址）$H(K_i)$

散列函数

一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr（这里的地址可以是数组下标、索引或内存地址等）

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，发生冲突的不同关键字称为同义词。一方面，设计得好的散列函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法

散列函数的构造方法

在构造散列函数时，必须注意以下几点：

散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围
散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间，从而减少冲突的发生
散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址

1. 直接定址法

直接去关键字的某个线性函数值为散列地址，散列函数为 $$H(key)=a\times key+b$$

式中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费

2. 除留余数法

最简单、最常用。假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为 $$H(key)=key\mod p$$

除留余数法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突

3. 数字分析法

设关键字是r进制数，则r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数

4. 平方取中法

顾名思义，这种方法取关键字的平方值的中间几位作为散列地址。具体取多少位要根据实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数

5. 折叠法

将关键字分割成位数相同的几部分（最后一部分的位数可以短一些），然后取这几部分的叠加和作为散列地址，这种方法称为折叠法。关键字位数很多，而且关键字中的每位上数字分布大致均匀时，可以采用折叠法得到散列地址

方法2是重点

实际情况中会用String作为key

方法1：把字符的ASCII码相加。缺点是但不能均匀分布
方法2：取前三个字母的ASCII码值
方法3：将所有字符的ASCII值乘以权重相加

处理冲突的方法

1. 分离链法（拉链法、链接法、chaining）

把所有散列地址一样的放入一条链表中

适用于经常进行插入和删除操作

2. 开放定址法

发生冲突时存到别的位置

数学递推公式为 $$H_i=(H(key)+d_i)\mod m$$

其中，$i=0,1,2,...,k(k\leqslant m-1)$；$m$代表散列表表长；$d_i$为增量序列

怎么找其他位置？

线性探测法 Linear probing

$d_i=0,1,2,...,m-1$

问题：冲突太多，每次都会争夺后一个元素的位置，容易形成簇

一般不用

平方探测法

$d_i=i^2$

问题：初始地址一样的探测地址也一样，会形成二次簇

双散列法（再散列法）

定义两个散列函数。一个求散列地址，一个$Hash_2(key)$。每次往下谈$Hash_2(key)$

当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数$Hash_2(key)$计算该关键字的地址增量。它的具体散列函数形式如下： $$H_i=(H(key)+i\times Hash_2(key))\mod m$$

i代表冲突的次数，初始为0.双散列法中，最多经过m-1次探测就会遍历表中所有位置，回到$H_0$位置

伪随机序列法

$d_i$为伪随机数序列时

实际上平方探测法用的最多

注意：在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址

Files

数据结构核心考点.md

Latest commit

History