《王道考研 · 数据结构》
写在前面
参考书目 & 课程：王道考研 · 数据结构
在刷课的时候为了保持注意力集中写的一些简单记录，尤其记录了一些不熟悉的部分。在描述的过程中用的是通俗的语言，因此可读性可能没有那么强。
仅作为个人学习记录，便于遗忘之后快速回忆。并不推荐作为教学内容阅读。
1 开篇
数据元素：数据的基本单位，通常作为一个整体进行考虑和处理。
数据项：是构成数据元素不可分割的最小单位。（根据实际业务需求来确定）
数据对象：具有相同性质的数据元素的集合（不强调关系）。
数据类型：一个值的集合和定义在此集合上的一组操作的总称，分为原子类型（bool/int）、结构类型（struct）、抽象数据类型ADT（具体实现→数据结构）
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。（= 逻辑结构 + 存储结构 + 数据的运算）
特别注意
1.抽象数据类型ADT描述了数据的逻辑结构和抽象运算，通常用<数据对象，数据关系，基本操作集>这样的三元组来表示。
2.顺序表、哈希表、单链表有具体的存储结构和数据运算，属于数据结构；有序表是关键字有序的线性表，仅表示元素之间的逻辑关系，存储方式可以是链式或顺序，因此属于逻辑结构。
3.循环队列是用顺序表表示的队列，属于数据结构；栈是ADT，存储结构可以是顺序或链式存储，只是逻辑结构。
4.逻辑结构从实际问题出发，独立于存储结构；存储结构是逻辑结构在计算机上的映射，不能独立于逻辑结构存在。
5.存储数据时，不仅要存储数据元素的值，还要存储数据元素之间的关系。
6.链式存储节点内的存储单元地址必须连续
算法的特性：有穷性、确定性（相同的输入只能得出相同的输出）、可行性（执行有限次基本运算）、输入（0+）、输出（1+）。
好算法的特质：正确性、可读性、健壮性、高效率与低存储量需求
时间复杂度：在计算T(n)时，其实是计算执行次数的总和；比较时可以忽略低次项与最高次项的系数。在实际应用中，应该找到基本操作，然后直接用O(n)进行计算。
执行时间与输入数据有关时：最好时间复杂度/最坏时间复杂度/平均时间复杂度。
空间复杂度：内存需求 = 程序代码（固定不考虑）+ 数据（变量数 * 每个变量所占大小）
如果S(n) = O(1)，则称算法原地工作。
对于空间复杂度，在递归问题中，只需要关注递归次数与每次声明的变量即可。
顺序表 & 链表
线性表：相同数据类型的n（n>=0）个数据元素的有限序列。
注意：数据元素的位序（1~n）是从1开始的，区别于索引是从0开始。
顺序表：顺序存储的方式实现线性表。
特点：随机访问（O(1)访问第i个元素），存储密度高，拓展容量不方便（动态分配）、插入删除元素不方便。
链表分为单链表、双链表、循环链表、静态链表。
注意：单链表中，指定节点进行前插，可以仍然执行后插操作，但是交换节点的值。注意空指针问题。
单链表的建立：头插法/尾插法。
链表逆置：1.顺序读取原链表，同时用头插法生成新链表；2.顺序读取原链表，取下节点后使用头插法原地逆置。
循环链表的尾指针指向头节点，因此不存在空指针问题。如果经常要对表头/表尾操作，可以把指针指向尾结点。
静态链表分配一整片连续的内存空间，各个节点集中安置，每个元素内部额外存储下一个元素的地址（索引）。其中index == 0 的节点充当头结点。
栈 & 队列
栈是只允许在一端进行插入或删除的线性表，后进先出LIFO。
顺序存储实现：使用数组，同时用一个int来记录栈顶的索引。
共享站：两个栈使用同一片连续的内存，需要两个int变量来记录索引，提高资源利用率，一定程度可以减少上溢。
链式存储实现：其实是对插入删除加以约束（只能在表头进行）的单链表。
栈的应用 - 括号匹配：使用栈，左括号push，右括号pop（注意查看是否匹配类型），最后查看栈是否为空。
栈的应用 - 表达式求值：
前缀/中缀/后缀表达式（逆波兰式）
将中缀表达式转换为前缀/后缀表达式时，是把运算顺序捋顺了，就可以通过栈来进行计算。
下面详述中缀转后缀的步骤。中缀转前缀需要从右往左扫描，其他同中缀转后缀。
1.中缀转后缀
1.中缀转后缀
手算转换：第一步手算表达式会得到不唯一的结果，因此需要增加约束来获得唯一的输出（左优先原则，即只要左边能先计算就先算，而不是只看运算符和界符的优先级）
机算转换：从左往右扫描（中缀表达式），栈内存的是操作符/界符。遇到数字就加入结果，继续扫描；遇到运算符P，弹出（在遇到左括号和栈底前）栈内优先级>=P的运算符（意味着要先算了）加入结果，P再入栈；遇到界符“（”入栈，遇到界符“）”依次弹出栈内的运算符加入结果，弹出“（”之后丢掉停止。最后依次弹出栈内剩余运算符。
2.表达式计算
手算计算：从左往右扫描（后缀表达式），遇到运算符就与最近的两个数字进行运算（区分左右操作数，根据中缀转后缀时的书写顺序就能确定；在手算时，可以模拟画一个操作数栈，先出栈的是右操作数，但机算还额外需要运算符栈，因为“填回原位”这个操作本身就保持了计算顺序，计算机需要运算符栈来记录计算顺序），把结果填回原位。
机算计算：需要操作数栈和运算符栈。扫描到操作数，压入操作数栈；扫描到运算符/界符，按转换的入栈逻辑压入运算符栈。对于弹出的运算符，需要弹出两个操作数进行计算后，重新压入操作数栈。
栈的应用 - 递归
函数调用栈需要存储的信息：调用返回地址、实参、局部变量。
缺点：递归太深容易栈溢出。容易包含重复运算。
队列只允许在一端进行插入，在另一端删除的线性表，先进先出FIFO。
顺序存储实现：使用数组，设置两个int记录队头和队尾。注意设置队尾指向接下来插入元素的位置索引（这样在队空时也能保持逻辑一致）。
注意因为入队和出队的方向不一致，所以在修改队尾指针的值时，需要对数组长度进行取余。（循环队列）
注意判断队列已满的条件为队尾指针的再下一个位置是队头，因为之前判空的条件是队头和队尾指针指向同一个元素，因此需要加以区别。
当然另一种解决方案是单独用一个变量存储队列内的数量。
或者在最初解决方案的基础上，设置变量记录上一次成功操作的类型是插入还是删除。
链式存储实现：加以约束的单链表。
双端队列：允许从两端插入删除的线性表。
队列的应用：树的层次遍历 图的广度优先遍历（BFS）操作系统的FCFS
特殊矩阵的压缩存储
普通矩阵：二维数组（行优先/列优先存储）
对称矩阵存储：只存储主对角线+下三角区，使用行优先存入一维数组，建立映射关系。
三角矩阵的存储：基本同对称矩阵，修改映射关系即可。
三对角矩阵的压缩存储：只存储带状部分，使用行优先存入一维数组，建立映射关系。
建立映射关系的步骤：确定Aij在数组中的索引值，根据矩阵性质建立分段函数。
由一维数组的索引求元素在矩阵中的位置， 可以通过元素的位置列出不等式，取整得到行号，再求得列号。
稀疏矩阵：
1. 三元组<行，列，值>顺序存储，但缺点是不能随机存取，查找时只能遍历查找。
2. 十字链表法，定义元素结点，包含行、列、值以及向下与向右的指针。
串
子串：串中任意个连续的字符组成的子序列。
字符在主串中的位置：字符在串中的序号（从1开始计数）
存储结构：顺序存储（静态/动态数组），链式存储（缺点存储密度低，指针占用的内存大小比字符还大；可以考虑在每个节点存储多个字符）
获取子串：
1.朴素模式匹配算法
获取与模式串长度相同的串，进行比较，逐位后移，直到匹配为止。
若模式串长度为m，主串长度为n，匹配成功的最好（开头就出现了模式串）时间复杂度为O(m)；匹配失败的最好（每次失败都是第一位就配不上，直接后移）时间复杂度为O(n-m+1)≈O(n)。匹配成功的最坏（即每次失败都是最后一位配不上）时间复杂度为O((n-m+1)*m)=O(nm)。
缺点：指针经常回溯。
2.KMP算法
i 指向主串，j 指向模式串。
如果模式串在第 j 位时匹配失败，则说明前面1 ~ j - 1位都匹配成功了；我们引入辅助数组next[]来存储模式串的一些信息（用于判断j回溯到哪个位置），这里为了使位序和索引统一，next[0]舍弃不用。next[]记录了模式串与主串不匹配时，模式串应该从哪里开始重新匹配。
因为 i 不回溯，在 j 扫描过程中，如果与主串字符不匹配了，那么意味着模式串的头要后移（即 j 回溯到next[j]的位置）；如果与主串字符匹配，那么i和j都后移。
为了使写法统一，规定next[1]=0，然后单独的判断j==0时，使i和j后移。（注意，当j==0（或者其他设计的特殊值，如-1）的时候，意味着第1位就配不上，要把整个模式串后移一格，j还是指向第1位，主串的 i 向后指一格，此处++0正好等于1，所以并入++i;++j;语句的判断条件中了）。
下面讨论如何求解next数组。
串的前缀指包含第一个字符，且不包含最后一个字符的子串；串的后缀指包含最后一个字符，且不包含第一个字符的子串。当模式串的第k个字符匹配失败，则前面1~k-1个字符组成的子串记为S。next[j]=S的最长相等前后缀长度+1。
此时，第 j 个字符匹配失败，i 前面 j - 1个字符（即S），与 j 前面j - 1个字符（即S），是已经匹配上的。这个时候，要找S最大的相等前后缀，为的是防止一下子移动太多错过目标。例如S的长度为L(L = j - 1)，而找到的S最大的相等前后缀长度为 l，那么模式串其实要向后移动L - l个单位，对于 j 指针来说，就是向前移动L - l个单位，即next[j] = j - (L - l) = j - (j - 1 - l) = l + 1
对于程序实现，需要首先计算出next数组，然后扫描比对。计算next数组的时间复杂度为O(m)，而扫描比对时 i 不回溯，因此时间复杂度为O(n)，KMP算法的平均时间复杂度为O(m+n)。
注意，此处408考研没有要求代码实现，因为计算next数组时，要找到最大相等前后缀这一部分未说明（上述解法用手算非常容易实现）。
KMP算法优化：KMP存在的问题是，当模式串的第 j 位出现不匹配时，会让模式串向后移动，如果恰好原本的第 j 位和第next[j]位相同，而不匹配本身就由第 j 位引起的，因此模式串向后移动之后，会导致多一次无意义匹配。
因此用nextval[]数组替代next[]数组，它们唯一的不同是，如果第 j 位和第next[j]位的字符相等，那就设置nextval[j] = nextval[next[j]]（即先看j对应的next[j]，它意味着向后移动、将模式第next[j]位与主串的i位对齐，又因为j和next[j]出现了相等这个情况，是浪费的行为，所以干脆在nextval数组里面，把第next[j]位配不上的移动办法抄到第j位配不上的情况里。因为保不准1 ~ j - 1这个子串S情况极其特殊，我们填写的时候是从左往右填写的，第一次遇到的时候其实就是多移动一格的处理办法，后面如果是多连跳，那么从左抄到右就一定可以实现，不会浪费多比较），其他一般情况nextval与next数组同。
省流手算：
先求next[]数组，先写next[1]=0,next[2]=1，然后通过求解前后缀最大匹配长度+1填写完毕。
接着求nextval数组，先抄nextval[1]=0，nextval[2]=1，从左往右填，遇到第 j 位和第next[j]位字符相同的特殊情况，把next[j]对应字符的nextval值抄下来，普通情况把j对应字符的next值抄下来。完毕。
树
非空树有且仅有一个根节点。除根节点外，任何一个结点有且仅有一个前驱。
结点的深度，从上往下从1开始数；结点的高度，从下往上从1开始数；树的高度/深度，总共多少层；结点的度指有几个孩子结点；树的度是各结点度的最大值。
常考性质：结点数 = 总度数 + 1
度为m的树（或m叉树），第 i 层最多有m^( i - 1)个结点(i >= 1)
高度为h的m叉树最多有(1 - m^h)/(1 - m)个结点，由上一条结论等比数列求和得到；最少为h个结点。
高度为h，度为m的树至少有h + m – 1个结点。
具有n个结点的m叉树的最小高度为：
二叉树是有序树，是递归定义的数据结构。
满二叉树：除叶结点，其他的结点度都为2。按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1。
完全二叉树：每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应。只有最后两层可能有叶结点，最多只有一个度为1的结点，i<=n/2向下取整为分支结点，其余为叶结点。
二叉排序树：左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字，左子树和右子树各是一棵二叉排序树。有利于搜索。
平衡二叉树：任意结点的左子树和右子树的深度之差不超过1。能有更高的搜索效率。
设非空二叉树中度为0、1、2的结点个数分别为n0,n1,n2，则n0 = n2 + 1
二叉树的顺序存储：对于完全二叉树，定义包含值与是否为空信息的元素，存入数组后仍能记录结点之间的逻辑关系。但如果只是普通的二叉树，在标号之后顺序存储就会丢失逻辑关系的信息，所以要转化成完全二叉树，编号后存储。缺点是容易有很多空间会被浪费。
二叉树的链式存储：定义包含<值，左指针，右指针>的元素。注意n个结点的二叉链表共有n+1个空链域（总共有2n个指针，其中有n-1个结点的一个指针是不为空的，因此得出n+1）。对于指定结点p来说，要获得父结点并不方便（需要从根结点遍历），因此可以考虑在元素中增加一个父结点的指针，这被称之为三叉链表。
先/中/后序遍历：基于树的递归特性确定的次序规则。先序遍历NLR，中序遍历LNR，后序遍历LRN。
手算：使用分支节点逐层展开法。
程序：若二叉树为空，不做处理；若二叉树非空，按照遍历的顺序访问节点。（递归遍历左右子树）。
层次遍历：基于树的层次特性确定的次序规则。
首先初始化一个辅助队列，使根节点入队。若队列非空，则队头结点出队，访问该结点，并将其左右孩子插入队尾。
由遍历序列构造二叉树：
一个前/中/后/层序遍历序列可能对应多种二叉树形态。如果需要唯一确定一棵二叉树，则要求（前序 && 中序）||（后序 && 中序）||（层序 && 中序）的遍历序列。
前序 && 中序：
后序 && 中序：
层序 && 中序：
注意找到根节点，根据中序序列划分左右子树。
前序、后序、层序的两两组合无法唯一确定一棵二叉树。
二叉树必须从根节点出发才能完成遍历，对于指定节点无法找到它（中序/先序/后续遍序列中的）前驱，因此引入线索二叉树来解决如上问题。
线索二叉树：
存储结构：<值，左指针，右指针，左线索标志，右线索标志>。因为要对左右指针指向左右孩子和中序遍历的前驱后继这两种情况进行区分，所以设立了两个标志位。tag==0时表示指针指向的是孩子，tag==1时表示指针是线索。
代码实现二叉树的线索化（中序/先序/后序线索化）：用一个pre指针记录当前结点q的前驱结点。当q的左指针为空，就建立q的前驱线索；当pre的右指针为空（注意判断pre!=NULL），就建立pre的后继线索。结束后，对最后一个结点的右指针单独处理。
先序线索化进行先序遍历时，需要额外判断结点的类型，当左结点不为前驱线索时，才执行线序遍历（否则容易陷入死循环）
线索二叉树找前驱/后继：
中序线索二叉树找中序后继
对于中序线索二叉树，其遍历顺序为左根右，因此整棵树的中序遍历序列的第一个结点一定是最左边的结点。对于指定结点p，当rtag==1时，直接返回p->rchild；当rtag==0时，说明p存在右子树，要找到p的后继结点，就要找到以p->rchild为根的右子树的中序遍历序列的第一个节点。
同理寻找p的中序前驱，首先要找最右边的结点。然后判断指定结点p的ltag类型。
先序线索二叉树
对于线序线索二叉树寻找先序前驱，当ltag==0时，说明p必有左孩子，但在先序遍历（根左右）中，左右子树中的结点只可能是根的后继，不可能是前驱，因此在这种情况下是没有办法找到p的先序前驱的。
如果能获得p的父结点，则能讨论情况如下：
对于后序后继来说，它跟先序前驱都有类似的问题，即当rtag==0时，说明p一定有右孩子，而后续遍历（左右根）导致p的左右子树中的结点只可能是根的前驱，不可能是后继，因此这种情况也无法找到。
树的存储结构
双亲表示法（顺序存储）：每个结点中保存指向双亲的指针（即对应数组的索引）。
孩子表示法（顺序+链式存储）：顺序存储各个结点，每个结点中保存孩子链表头指针。
孩子兄弟表示法（链式存储）：包含<值，第一个孩子指针，右兄弟指针>，这就是树与二叉树转换。
森林和二叉树的转换：将每棵树都转换为二叉树，然后将每棵树的根节点看作兄弟结点，用右指针连接。（孩子兄弟表示法）
树和森林的遍历：
树：先根/后根/层次遍历。
森林：先序（效果等同于对二叉树的先序遍历）/中序（效果等同于对二叉树的中序遍历）遍历。
二叉排序树BST
左子树结点值 < 根结点值 < 右子树结点值
因此进行中序遍历，可以得到一个递增的有序序列。
插入：新插入的结点一定是叶子结点。注意若树中存在相同关键字的结点，则插入失败。
构造：依次将每个关键字插入到二叉排序树中。
删除：叶子结点直接删除即可；若结点z只有一棵左子树或右子树，则让z的子树替代z的位置即可；若结点z有左右两棵子树，找到z右子树值最小的结点（中序遍历会得到一个递增的有序序列），用它的值替代z的值，之后删除它；或者找到z左子树值最大的结点，即左子树最右下结点，替代后删除。
查找效率分析：
在查找运算中，需要对比关键字的次数成为查找长度，反映了查找操作时间复杂度。
求取查找成功的平均查找长度ASL。效率很大程度上取决于树的高度，最好的情况是n个结点的二叉树处于最小高度，其平均查找长度为O(log2(n))，而最坏情况下树高h=n，则平均查找长度为O(n)。
求取查找失败的平均查找长度：补齐树的空结点进行计算。
平衡二叉树AVL树：树上任一结点的左子树和右子树的高度之差不超过1。
结点的平衡因子 = 左子树高 – 右子树高
插入：在二叉排序树中插入新节点后，要调整到平衡的状态，每次调整的对象都是“最小不平衡子树”，即从插入点往回找到第一个不平衡结点，调整以该节点为根的子树。
调整最小不平衡子树：分为LL RR LR RL四种。
哈夫曼树：
结点的带权路径长度：从树的根到该结点的路径长度 * 该结点的权值
树的带权路径长度WPL：树中所有叶结点的带权路径长度之和
在含有n个带权叶结点的二叉树中，带权路径长度最小的二叉树，称为哈夫曼树（最优二叉树）。
图
图不可以是空，它的顶点集一定是非空集，但边可以是空集。
连通图，一种特殊的无向图；强连通图，一种特殊的有向图。
无向图中的极大联通子图称为联通分量，即子图必须联通，且包含尽可能多的顶点和边。
有向图中的极大联通子图称为强连通分量。
连通图（无向）的生成树是包含图中全部顶点的一个极小连通子图，即边尽可能少，但要保持联通。
无向完全图：任意两个顶点之间都存在边。
存储结构：
邻接矩阵法：空间复杂度O(n^2)，适合用于稠密矩阵。注意，设图G的邻接矩阵为A（矩阵元素为0/1），则A^n的元素A^n[i][j]等于由顶点i到顶点j的长度为n的路径的数目。
邻接表法
十字链表法：注意只能用于存储有向图。
对于无向图来说，邻接矩阵和邻接表都会存在冗余数据（因为每条边其实可理解为双向的，一定会对应两份数据），可以考虑使用邻接多重表来存储：
BFS
同一个图的邻接矩阵表示方式唯一，因此BFS遍历序列唯一；同一个图的邻接表表示方式不唯一，因此BFS遍历序列不唯一。
需要用辅助数组记录访问过的节点，注意处理非连通图的情况。
DFS
图的DFS类似树的先根深度遍历。需要用辅助数组记录访问过的节点，注意处理非连通图的情况。
最小生成树：
连通图的生成树是包含图种全部顶点的一个极小连通子图，即边尽可能的少，但要保持连通。最小生成树MST是边的权值之和最小的生成树。
Prim算法：从某一个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。时间复杂度O(|V|^2)，适合用于边稠密图
Kruskal算法：每次选择一条权值最小的边，使这两条边的两头连通（原本已经连通的就不选），直到所有结点都连通。时间复杂度O(|E|log|E|)，适合用于边稀疏图
注意在实现过程中，Kruskal需要用到并查集来判断两个订单是否属于同一集合。（并查集不在考研考纲内）
BFS解单源最短路径（求无权图，或边权值都是1的图）
从给定起点出发，用队列进行BFS搜索，在辅助数组中记录信息。在BFS访问一个顶点式，修改最短路径长度d[]，并在path[]记录前驱结点。
Dijkstra解单源最短路径（求带权图、无权图）
final数组记录各订单是否已找到最短路径；dist数组记录最短路径长度；path记录路径上的前驱。
循环遍历所有结点，找到还没确定最短路径且dist[]最小的顶点，令final[i] = true。然后检查所有临接它的顶点，更新其中final为false的结点dist与path信息。
注意，如果有负权值，那本算法无法解决处理。
Floyd解多源最短路径（带权图、无权图）
两个矩阵来记录，A记录各顶点间的最短路径长度，path记录两个顶点之间的中转点。
不能解决带有负权回路的图，这种图可能没有最短路径。
有向无环图 描述表达式
DAG：若一个有向图中不存在环，则称为有向无环图。
尝试手算构造，首先把各操作数不重复地排成一排，然后标出各个运算符的生效顺序，按顺序加入运算符（分层），从底向上检查同层的运算符是否可以合并。
拓扑排序：对DAG顶点的一种排序，使得它符合执行的顺序。
AOV网：用DAG图表示一个工程，顶点表示活动。注意AOV网一定无环。
实现：1.从AOV网中选择一个没有前驱的顶点并输出 2.从网中删除该顶点和所有以它为起点的有向边。3. 重复上述步骤到AOV网为空
逆拓扑排序：考量的是结点的出度。
可以用DFS实现逆拓扑排序。
AOE网：边表示活动，顶点表示状态，以边上的权值表示完成该活动的开销。可以并行进行。仅有一个入度为0的顶点（源点），也仅有一个出度为0的顶点（汇点）。
关键路径：从源点到汇点，具有最大路径长度。关键路径上的活动称为关键活动。
1.状态Vk的最早发生时间ve(k)：决定了所有从Vk开始的活动能够开工的最早时间。首先要求出拓扑序列，按拓扑序列求解。ve(源点) = 0; ve(k) = Max{ve(j) + Weight(vj, vk)};其中vj是vk 的任意前驱。
2.活动ai的最早开始时间e(i)：该活动弧的起点所表示的事件的最早发生时间。首先要求出逆拓扑序列，按逆拓扑序列求解。vl(汇点) = ve(汇点); vl(k) = Min{vl(j) – Weight(vk,vj)}; vj为vk的任意后继。
3.状态Vk的最迟发生时间vl(k)：在不推迟整个工程完成的前提下，该事件最迟必须发生的时间
4.活动ai的最迟开始时间l(i)：活动弧的终点所表示时间的最迟发生时间与该活动所需时间之差
查找
评价指标：ASL平均查找长度，即查找过程中进行关键字的比较次数的平均值。会考虑成功/失败的ASL。
顺序查找：通常用于线性表。优化：如果被查概率不相等，可以考虑按照被查概率进行排序。
折半查找：只适用于有序的顺序表。
折半查找判定树的构造。注意右子树结点数 – 左子树结点数 = 0 或 1。
分块查找：看似是无序的，但可以按照大小范围进行分块，块内无序、块间有序。要用一张索引表保存每个分块的最大关键字和分块的存储区间。首先从索引表中查找所属分块，然后再块内顺序查找。
如果分块时能均匀分块，长度为n的查找表被均匀地分为b块，每块s个元素，则ASLmin = √n + 1，让且仅当s = √n
B树：
为了保证查找效率，规定在m叉查找树中，除了根节点外，任何结点至少有m/2向上取整个分叉；对于任何一个结点，其所有子树的高度都要相同。
B树中所有结点的孩子个数的最大值称为B树的阶。注意我们把对应失败的结点称为叶子结点，把实际有值的最底层结点称为终端节点。
含n个关键字的m阶B树，最大高度：
插入和删除：
在插入key后，若导致原结点关键字超过上限，则从中间位置（m/2向上取整）将关键字分为左右两部分，中间值称为它们的父结点。新元素一定是插入最底层的终端结点，然后查找属于它的位置。
若被删除关键字在终端结点，则直接删除（要注意结点关键字个数是否低于下限）。若低于下限了，且兄弟结点的关键字个数还很宽裕，则需要问兄弟“借”，注意不能直接把兄弟结点关键字的值拿过来，会打乱B树的有序，应该是兄弟结点关键字升上去把父结点里的关键字换下来。若兄弟不够借，则将关键字删除后与兄弟结点及双亲结点中的关键字进行合并。合并的过程中可能导致上层出现不足，则重复合并到符合要求为止。
若被删除关键字在非终端结点，则用直接前驱或直接后继来替代（直接前驱在当前关键字左侧指针所指子树中“最右下”的元素；直接后继在当前关键字右侧指针所指子树中“最左下”的元素）。
B+树：
最底层的结点称为叶子结点，其余为分支结点。每个分支结点最多有m棵子树；非叶根节点（不同时为叶子结点的根节点）至少有两棵子树，其他每个分之结点至少有m/2向上取整棵子树；结点的子树个数与关键字个数相等；所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排序，且相邻叶结点按大小顺序相互链接起来；所有分支结点只包含各个子节点中关键字的最大值及指向其子结点的指针。
B+树中，非叶结点不含有该关键字对应的存储地址，可以使一个磁盘块包含更多关键字，使B+树的阶更大，树高更矮，读磁盘次数更少，查找更快。
散列查找：
散列表（哈希表），数据元素的关键字与存储地址直接相关，通过哈希函数来建立关键字与存储地址的联系。
若不同关键字通过哈希函数映射到同一个值，则它们是同义词，会产生哈希碰撞。
拉链法
把所有同义词存储在链表中。
开放定址法
当发生第i次冲突时，对key做如下变换Hi = (H(key) + di) % m，其中m表示散列表表长，di为增量序列。注意删除时不能简单置空，应当进行逻辑置空。
线性探测法：di = 0,1,2,…,m-1；即发生冲突时，每次向后探测相邻的下一个单元是否为空。
平方探测法：di = 0,1,-1,4,-4,9,-9,…。注意散列表长度m必须是一个可以表示成4j+3的质数才能探测到所有位置。
伪随机序列法：di是一个伪随机序列。
再散列法：除了原始哈希函数外，多准备几个哈希函数，当发生冲突时用下一个哈希函数算一个新地址，直到不冲突为止。
查找长度：需要对比关键字的次数。
装填因子=表中记录数/散列表长度，它会直接影响散列表的查找效率。
常见的哈希函数
除留余数法（散列表表长为m，取一个不大于m但最接近或等于m的质数p，是为了让不同关键字的冲突尽可能地少）；
直接定址法（对key做线性变换，适合关键字的分布基本连续的情况）；
数字分析法（选取数码分布较为均匀的若干位作为散列地址）；
平方取中法（取关键字的平方值的中间几位作为散列地址）
排序
内部排序，数据都在内存中；外部排序，数据太多无法全部放入内存，除了关注时空复杂度之外，还要关注如何减少读写磁盘次数。
插入排序：
空间复杂度O(1)，时间复杂度O(n^2)，稳定
可以用折半查找插入的位置进行优化。
希尔排序：先将待排序表分割成若干形如L[i.i+d,i+2d,…,i+kd]的特殊子表，对各个子表分别进行插入排序。缩小增量d，重复上述过程，直到d=1为止。可以每次将增量缩小一半。
空间复杂度O(1)，最坏时间复杂度为O(n^2)，在某个范围内，可达O(n^1.3)，不稳定
冒泡排序：
空间复杂度O(1)，时间复杂度O(n^2)，稳定
快速排序：在待排序表中任选一个元素pivot作为枢轴，通过一趟排序将待排序表划分为独立的两部分，使得左边所有元素都小于pivot，右边都大于等于pivot。递归地对两个子表重复上述过程，直到每部分只有一个元素或空为止。
若初始序列有序或逆序，快排的性能很差。要进行优化，则可以选头、中、尾三个位置的元素，取中间值为pivot；或者随机选一个元素。
简单选择排序：每一趟在待排序元素中选取关键字最小的元素加入有序子序列。
堆排序：
建立大根堆：从非叶结点开始，自底向上检查当前结点是否满足根>=左右孩子，若不满足将当前节点与更大的孩子互换。若元素互换破坏了下一级的堆，则进行调整。
基于大根堆进行排序：每一趟在待排序元素中选取关键字最大的元素移到末尾。
建堆的时间复杂度O(n)，总时间复杂度O(nlog2n)
插入删除：
插入时，首先放在表尾，与父结点对比，小根堆让新元素尽量一路上升。删除时，让表尾元素代替被删除元素，然后调整它不断下坠。
归并排序：把两个或多个有序序列进行合并（多指针）。
空间复杂度O(n)，时间复杂度O(nlogn)
基数排序：
因为数字每一位都为0~9，因此建立十个辅助链表。第一趟按照个位进行分配，然后按照各位大到小的顺序进行收集。第二趟按照十位重复操作，因为原本个位已满足从大到小排，因此第二趟分配会使得十位相同的链表也满足个位递减的顺序。不断重复。
注意如果位数不满，可以前面补0。
适合解决的问题类型：可以根据关键字拆分为d组，且d较少；每组关键字的取值范围不大，即r较小；数据元素n较大。
外部排序：首先要生成r个初始归并段，然后进行k路归并。分配两块输入缓冲区，一块输出缓冲区。为了减少读写次数，可以增加输入缓冲区，即多路归并。
外部排序时间开销 = 读写外存的时间 + 内部排序时间 + 内部归并时间
归并趟数S = logk r向上取整，归并路数k增加，归并趟数Si就按小，读写磁盘总数减少
增加归并路数，会导致内部对比次数增加，因此要用败者树进行判断。
败者树：可以视为完全二叉树（但多了一个头），k个叶子结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的失败者，而胜者继续比较。
置换-选择排序：
原本构造初始归并段：在外部排序时，可以用一片更大的内存区域来进行内部排序，若用于内部排序的内存工作区WA可以容纳l个记录，则每个初始归并段也只能包含l个记录。若文件共有n个记录，则初始归并段的数量r = n l
为了构造比内存工作区更大的初始归并段，使用置换-选择排序。
构造归并段时，用变量记录当前的最大值。如果从初始待排文件中读入的数小于记录的最大值时，说明不能再加入当前归并段（不能保持有序），留存在内存工作区中。直到内存工作区中的内容都比记录最大值小时，该归并段在此时截止。
最佳归并树：每个初始归并段看作一个叶子结点，归并段的长度作为结点权值。它的带权路径长度 = 读磁盘次数 = 写磁盘次数。
因此要追求磁盘I/O次数最小，因此要使得WPL最小，所以求取哈夫曼树。
注意：对于k叉归并，若初始归并段的数量无法构成严格的k叉归并树，则需要补充几个长度为0的“虚段”，再进行k叉哈夫曼树的构造。
k叉的最佳归并树一定是严格的k叉数，设度为k的结点有nk个，度为0的结点有n0个，总结点数n，则n = n0 + nk，k nk = n -1(分叉总数 = 结点数 - 1)，求解加上nk为一个整数的条件，即能判断需要增加多少虚段。
写在后面
这一次速通数据结构的体验还是不错的。
因为大二学的时候经常听着听着就困了，尤其是像KMP那一块，完全不知道在处理什么。这一次反复暂停思考收获还是很多的，“我还是能学会KMP的”是这种感觉。
ok虽然不见得过一遍就学到多少了，但是下一遍应当会轻松些。
文案/排版：咸
特别鸣谢：王道考研
