191 KiB
查找
基本概念
- 查找：在数据集合中寻找满足某种条件的数据元素的过程。
- 查找表（查找结构）：用于查找的数据集合，由同一类型的数据元素或记录组成。
- 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该唯一。
- 静态查找表：只查找符合条件的数据元素。（顺序查找、折半查找、散列查找）
- 动态查找表：出来要查找，还要进行删除或插入，除了查找速度还要考虑插入删除操作是否方便。（二叉查找树查找、散列查找）
- 查找长度：查找运算中，需要对比关键字的次数。
- 平均查找长度$ASL$：所有查找过程中进行关键字比较次数的平均值。$ASL=\sum_{i=1}^nP_iC_i$。其中$P_i$表示查找第$i$个元素的概率，$C_i$表示查找第$i$个元素的查找长度。
线性表查找
顺序查找
又称为线性查找，常用于线性表，从头到尾逐个查找。
一般查找
在算法实现时一般将线性表的$0$号索引的元素值设为查找的值，从表最后面开始向前查找，当没有找到时就直接从$0$返回。这个数据称为哨兵，可以避免不必要的判断线性表长是否越界语句从而提高程序效率。
$ASL$查找成功为$\dfrac{1+2+3+\cdots+n}{n}=\dfrac{n+1}{2}$，$ASL$查找失败为$n+1$，时间复杂度为$O(n)$。
顺序表
可以让数据集变为有序的，这样对比数据大小也可以知道是否还需要遍历从而减少查找时间。这样顺序结构从逻辑上就变成了一个二叉树结构（一般是顺序的），左子树代表小于（失败结点），右子树代表大于（需要继续向右查找），所有数据结点挂在右子树上。
对于顺序查找，无论顺序表还是乱序表，查找成功的时间都是相同的。$ASL$也是相同的。
若有$n$个结点，则有$n+1$个查找失败结点。
查找情况还要比普通乱序查找加上一个大于最大值的情况。
虽然有$n+1$个失败结点，但是失败结点都是不存在的，如果结点失败只会在一个不存在的区间上，所以查找平均概率是$\dfrac{1}{n+1}$而不是$\dfrac{1}{2n+1}$。同理，查找成功查找失败都会在那个区间停下，一旦判断所在区域不存在就会退出，所以查找失败的次数跟最坏查找成功次数一样都是$n$查完所有。
$ASL$查找失败为$\dfrac{1+2+3+\cdots+n+n}{n+1}=\dfrac{n}{2}+\dfrac{n}{n+1}$。成功结点的查找长度等于自身所在层数，失败结点的查找长度等于其父结点所在层数。
注意，有序线性表的顺序查找和后面的折半查找的思想是不一样的（有序顺序查找是从两端开始向右比较，折半查找从中间开始不断取中间值比较）。且有序线性表的顺序查找中的线性表可以是链式存储结构。
查找概率不等
当数据元素查找概率不等时，可以将查找概率更大的元素放在靠前的位置，以减少大概率元素被遍历的时间。
$ASL$查找成功为$\sum\limits_{i=1}^nP_ii$，$P_i$为第$i$个元素出现概率。
但是此时数据是乱序的，所以查找失败的时间复杂度与没有优化的是一样的。
折半查找
也称为二分查找，只适用于有序的顺序表，链表无法适用，因为链表很难折半找到元素。
折半查找的结构
定义三个指针，$low$指向查找范围的最小值，$high$指向查找范围的最大值，$mid$指向查找范围的中间值，$mid=\lfloor(low+high)\div2\rfloor$。（也可以向上取整，过程会有所不同）
折半查找的过程
- 定义左边界$low$，默认为$0$，右边界$high$，默认为$length-1$，循环执行折半查找（2，3两步）。
- 计算出$mid=\lfloor(low+high)\div2\rfloor$。
- 判断中间索引值$data\lbrack mid\rbrack$是否与搜索值$target$相等。
- 若$data\lbrack mid\rbrack=target$，返回中间索引。
- 若$data\lbrack mid\rbrack<target$，则将$high=mid-1$。
- 若$data\lbrack mid\rbrack>target$，则将$low=mid+1$的值。
- 当查找最后$low>high$则查找失败。
$ASL$查找成功为$\dfrac{1+2+3+\cdots+n}{n}=\dfrac{n+1}{2}$，$ASL$查找失败为$n+1$，时间复杂度为$O(n)$。
折半公式优化
在对$mid$进行取值时，如果数据量太大，查找到右侧时计算$mid$进行两数相加$low+high$可能会数值溢出。那么如何解决？
- 变幻公式：$(low+high)\div2\rightarrow low\div2+high\div2$或$\rightarrow low-(low\div2-high\div2)\rightarrow low+(high-low)\div2$。
- 无符号右移运算：$mid=(low+hight) >>> 1$。直接将除以$2$变为右移运算，速度更快，且舍去了小数位不需要进行取整运算。
折半查找判定树
折半查找的过程可用二叉树来描述，称为判定树。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找不成功的情况。从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数。
构建判定树方式：
- 若当前$low$和$high$有奇数个元素，则$mid$分割后左右两部分元素个数相等。
- 若当前$low$和$high$有奇数个元素，则$mid$分割后左部分元素个数小于右部分一个。
- 结点索引从$0$或$1$开始，相加除以二后向下取整，并且两端要移动一位，否则会有问题。
- 数值结点为圆形，末端结点后再加一层方形的叶子结点，表示查找失败，失败的叶子结点是虚拟的，所在层数跟上层圆形结点是一样的，所以在计算查找长度时该点层数为其父结点成功结点的层数。
判定树性质：
- 折半查找判定树一定是一个平衡二叉树。只有最下面一层不满，元素个数为$n$时树高与完全二叉树相等$h=\lceil\log_2(n+1)\rceil$。
- 根据折半查找判定树可以计算对应的$ASL$：查找成功的$ASL$=($\sum\limits_{i=1}^n$第$i$层的成功结点数
\times i)$\div$成功结点总数，查找失败的$ASL$=($\sum\limits_{i=1}^n$第$i$层的失败结点数\times i)$\div$失败结点总数。 - 折半查找判定树也是一个二叉查找树，失败结点$=n+1$（成功结点的空链域结点数）。
- 折半查找判定树的中序序列应该是一个有序序列。
$ASL$查找成功查找失败都一定小于折半查找树的树高，时间复杂度为$O(\log_2n)$。
查找的折半查找判定树和排序的二叉查找树都是同样的二叉逻辑结构，但是不同的是折半查找判定树是已知完整序列，所以总是从中间开始，时间性能为固定的$O(\log_2n)$，而二叉查找树的构造是根据输入来的，如果输入的序列正好是从中间切分的，则时间性能为最好的$O(\log_2n)$，如果输入的序列恰好有序，则为单枝树，时间性能为最坏的$O(n)$。
分块查找
分块查找又称为索引顺序查找，需要对数据进行一定的排序，不一定全部是顺序的，但是要求在一个区间内是满足一定条件的，即块内无序，块间有序。即$n$块内的元素全部小于$n+1$块内的任意元素。
将查找表分割为若干子块，其中分割的块数和每块里的数据个数都是不定的。
分块查找结构
除了保存数据的顺序表外还需要定义一个索引表，保存每个分块的最大关键字、每块的存储空间，第一个元素的地址。
很明显这种定义方式定义了两个顺序结构，并且如果插入删除时需要大量移动元素，所以可以采用链表的形式。
定义一种最大元素结点，包含数据、指向后继最大元素结点的指针、指向分块内元素的指针；定义一种块内元素结点，包含数据、指向后继分块内元素的指针。但是这时候就无法折半查找，只能顺序查找。
所以总的来说分块查找还是一种静态查找，动态插入删除的效率较低。
分块查找过程
在查找时先根据关键字遍历索引表，然后找到索引表的分块（可以顺序也可以折半），再到存储数据的顺序表的索引区间中查找。
若适用折半查找查找索引表的分块，索引表中若不存在目标关键字，则折半查找索引表最终会停在$low>high$，要在$low$所指向分块中查找。
分块查找的效率
$ASL$查找成功失败的情况都十分复杂，所以一般不会考。
假设长度为$n$的查找表被均匀分为$b$块，每块$s$个元素，假设索引查找和块内查找的平均查找长度$ASL$分别为$L_I$和$L_S$，则分块查找的平均查找长度为$ASL=L_I+L_S$。
使用顺序查找索引表，则$L_I=\dfrac{(1+2+\cdots+b)}{b}=\dfrac{b+1}{2}$，$L_S=\dfrac{(1+2+\cdots+s)}{s}=\dfrac{s+1}{2}$。所以$ASL=\dfrac{b+1}{2}+\dfrac{s+1}{2}=\dfrac{s^2+2s+n}{2s}$，当$s=\sqrt{n}$时，$ASL_{min}=\sqrt{n}+1$。
使用折半查找索引表，则$L_I=\lceil\log_2(b+1)\rceil$，$L_S=\dfrac{(1+2+\cdots+s)}{s}=\dfrac{s+1}{2}$。所以$ASL=\lceil\log_2(b+1)\rceil+\dfrac{s+1}{2}$。
二叉查找
二叉查找树
即$BST$，是一种用于排序的二叉树。
二叉查找树定义
二叉查找树也是二叉排序树。左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字；左右子树又各是一棵二叉查找树。
中序遍历二叉查找树会得到一个递增的有序序列。
二叉查找树查找
- 若树非空，目标值与根结点的值比较。
- 若相等则查找成功，返回结点指针。
- 若小于根结点，则在左子树上查找，否则在右子树上查找。
- 遍历结束后仍没有找到则返回$NULL$。
遍历查找的时间复杂度是$O(\log_2n)$，则递归查找的时间复杂度是$O(\lceil\log_2(n+1)\rceil)$，其中$\lceil\log_2(n+1)\rceil$代表二叉树的高度。
查找成功的平均查找长度$ASL$，二叉树的平均查找长度为$O(\log_2n)$，最坏情况是每个结点只有一个分支，平均查找长度为$O(n)$。
二叉查找树插入
- 若原二叉查找树为空，就直接插入结点。
- 否则，若关键字小于根结点值，插入左结点树。
- 若关键字大于根结点值，插入右结点树。
二叉查找树删除
- 搜索到对应值的目标结点。
- 若被删除结点$p$是叶子结点，则直接删除，不会破坏二叉查找树的结构。
- 若被删除结点只有一棵左子树或右子树，则让该结点的子树称为该结点父结点的子树，来代替其的位置。
- 若被删除结点有左子树和右子树，则让其结点的直接后继（中序排序该结点后一个结点，其右子树的最左下角结点，不一定是叶子结点）或直接前驱（中序排序该结点前一个结点，其左子树的最右下角结点，不一定是叶子结点）替代该结点，并从二叉查找树中删除该的结点直接后继、直接前驱，这就变成了第一种或第二种情况。
二叉查找树删除或插入时得到的二叉查找树往往与原来的不同。
二叉查找树查找效率
二叉查找树的查找效率主要取决于树的高度，若是平衡二叉树，则平均查找长度为$O(\log_2n)$，若最坏情况下只有一个单枝树，则平均查找长度为$O(n)$。
若按顺序输入关键字则会得到单枝树。
查找过程来看，二叉查找树和二分查找类似。但是二分查找的判定树唯一，而二叉查找树的查找不唯一，相关关键字插入顺序会极大影响到查找效率。
从维护来看，二叉查找树插入删除操作只需要移动指针，时间代价为$O(\log_2n)$，而二分查找的对象是有序顺序表，代价是$O(n)$。
所以静态查找时使用顺序表进行二分查找，而动态查找时使用二叉查找树。
平衡二叉树
为了限制判定树高增长过快，降低二叉查找树的性能，规定插入时要保证平衡。
即$AVL$树，树上任意一结点的左子树和右子树的高度之差不超过$1$。
树高即树的深度。
结点的平衡因子=左子树高-右子树高。
即平衡二叉树的平衡因子只可能为$-1,0,1$。
在插入一个结点时，查找路径上的所有结点都可能收到影响。
从插入点往回（从下往上）找到第一个不平衡的结点，调整以该结点为根的子树。每次调整的对象都是最小不平衡树。
平衡二叉树结点
$h$为平衡二叉树高度，$n_h$为构造此高度的平衡二叉树所需的最少结点数。
注意：平衡二叉树最少结点数（所有非叶结点的平衡因子均为$1$的）的递推公式为$n_0=0$，$n_1=1$，$n_2=2$，$n_h=1+n_{h-1}+n_{h-2}$。此时所有非叶结点的平衡因子均为$1$。
假设$T$为高度为$h$的平衡二叉树，其需要最少的结点数目为$F(h)$。
又假设$TL$，$TR$为$T$的左右子树，因此$TL$，$TR$也为平衡二叉树。
假设$FL$、$FR$为$TL$，$TR$的最少结点数，则，$F(h)=FL+FR+1$。那么$FL$、$FR$到底等于多少呢？
由于$TL$，$TR$与$T$一样是平衡二叉树，又由于我们知道$T$的最少结点数是$F(h)$，其中$h$为$T$的高度，因此如果我们知道$TL$，$TR$的高度就可以知道$FL$、$FR$的值了。
由平衡二叉树的定义可以知道，$TL$和$TR$的高度要么相同，要么相差$1$，而当$TL$与$TR$高度相同（即都等于$h-1$）时，我们算出来的$F(h)$并不能保证最小，两边都是$h-1$明显比只有一边$h-2$的结点数更多。
因此只有当$TL$与$TR$高度相差一，即一个高度为$h-1$，一个高度为$h-2$时，计算出来的$F(h)$才能最小。
此时我们假设$TL$比$TR$高度要高$1$，即$TL$高度为$h-1$，$TR$高度为$h-2$，则有$F1=F(h-1)$，$F2=F(h-2)$。
因此得到结论：$F(h)=F(h-1)+F(h-2)+1$。
- 平衡二叉树最多结点数$2^n-1$。即该二叉树为满二叉树。
平衡二叉树插入
最重要的是根据二叉查找树的大小关系算出从大到小的序列，然后把最中间的作为新根，向两侧作为左右子树。
即先找到插入路径上离插入结点最近的平衡因子的绝对值大于$1$的结点$A$，再对以$A$为根的子树，在保持二叉查找树特性的前提下调整各结点位置。
每次调整的都是最小不平衡子树。
平衡二叉树删除
与插入操作类似，都是需要从下往上进行调整。
不同的是插入操作只对子树进行调整，而删除操作可能要对整个树进行调整。
在任意一棵非空二叉查找树$T_1$中，删除某结点$v$之后形成二叉查找树$T_2$，再将$v$插入$T_2$，形成二叉查找树$T_3$。
- 若$v$是$T_1$的叶结点，则$T_1$与$T_3$相同。
- 若$v$不是$T_1$的叶结点，则$T_1$与$T_3$不同（如果是一定不同则是错误的）。
右单旋转
从结点的左孩子的左子树中插入导致不平衡：
A(2)
|
------------
| |
B(1) AR(H)
|
------------
| |
BL(H+1) BR(H)
BL<B<BR<A<AR
由于在结点$A$的左孩子$B$的的左子树$BL$上插入了新结点，$A$的平衡因子由$1$变成了$2$，导致以$A$为根的子树失去了平衡，需要进行一次向右的旋转操作。
将$A$的左孩子$B$向右上旋转代替$A$成为根结点，将$A$结点向右下选择为成$B$的右子树的根结点，而$B$的原右子树则作为$A$结点的左子树。
B(0)
|
------------
| |
BL(H+1) A(0)
|
------------
| |
BR(H) AR(H)
左单旋转
从结点的右孩子的右子树中插入导致不平衡：
A(-2)
|
------------
| |
AL(H) B(-1)
|
------------
| |
BL(H) BR(H+1)
AL<A<BL<B<BR
由于在结点$A$的右孩子$R$的右子树$R$上插入了新结点，$A$的平衡因子由$-1$减至$-2$，导致以$A$为根的子树失去平衡，需要一-次向左的旋转操作。
将$A$的右孩子$B$向左上旋转代替$A$成为根结点，将$A$结点向左下旋转成为$B$的左子树的根结点，而$B$的原左子树则作为$A$结点的右子树。
B(0)
|
------------
| |
A(0) BR(H+1)
|
------------
| |
AL(H) BR(H)
先左后右双旋转
从结点的左孩子的右子树中插入导致不平衡：
A(2)
|
------------
| |
B(-1) AR(H)
|
------------
| |
BL(H) C(-1)
|
------------
| |
CL(H-1) CR(H)
A(2)
|
------------
| |
B(-1) AR(H)
|
------------
| |
BL(H) C(-1)
|
------------
| |
CL(H) CR(H-1)
将$BR$拆分为$C$和$CL$、$CR$，假设插入的是$CR$部分，插入$CL$也同理。
BL<B<CL<C<CR<A<AR
由于在$A$的左孩子$L$的右子树$R$上插入新结点，$A$的平衡因子由$1$增至$2$，导致以$A$为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转先将$A$结点的左孩子$B$的右子树的根结点$C$向左上旋转提升到$B$结点的位置，然后再把该$C$结点向右上旋转提升到$A$结点的位置。
C(0)
|
--------------------
| |
B(1) A(0)
| |
------------ ------------
| | | |
BL(H) CL(H-1) CR(H) AR(H)
C(0)
|
--------------------
| |
B(0) A(-1)
| |
------------ ------------
| | | |
BL(H) CL(H) CR(H-1) AR(H)
先右后左双旋转
从结点的右孩子的左子树中插入导致不平衡：
A(-2)
|
------------
| |
AL(H) B(1)
|
------------
| |
C(1) BR(H)
|
------------
| |
CL(H) CR(H-1)
A(-2)
|
------------
| |
AL(H) B(1)
|
------------
| |
C(1) BR(H)
|
------------
| |
CL(H-1) CR(H)
AL<A<CL<C<CR<B<BR
由于在$A$的右孩子$R$的左子树L. 上插入新结点，$A$的平衡因子由$-1$减至$-2$，导致以$A$为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将$A$结点的右孩子$B$的左子树的根结点$C$向右上旋转提升到$B$结点的位置，然后再把该$C$结点向左上旋转提升到$A$结点的位置。
C(0)
|
--------------------
| |
A(0) B(-1)
| |
------------ ------------
| | | |
AL(H) CL(H) CR(H-1) BR(H)
C(0)
|
--------------------
| |
A(0) B(-1)
| |
------------ ------------
| | | |
AL(H) CL(H-1) CR(H) BR(H)
平衡二叉树查找
含有$n$个结点的平衡二叉树最大深度为$O(\log_2n)$，平均查找长度为$O(\log_2n)$。
红黑树
红黑树定义
为了维持二叉平衡树，需要反复对树整体进行插入合删除，代价巨大，所以引入为弱化版相对平衡的二叉查找树——红黑树：
- 每个结点或是红色，或是黑色的。
- 根结点是黑色的。
- 叶结点（$n+1$个虚构的外部结点、$NULL$结点）都是黑色的，保证红黑树的内部结点左右孩子均非空。
- 不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的）。
- 对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。
所以定义某结点出发到达一个叶结点的任一简单路径上的黑结点总数（不含该目的结点）称为该结点的黑高（记为$bh$），根结点的黑高就是红黑树的黑高。
红黑树性质
从根到叶结点的最长路径不大于最短路径的两倍。
- 由性质⑤，当从根到任一叶结点的简单路径最短时，这条路径必然全由黑结点构成（即第二层的结点）。
- 由性质④，当某条路径最长时，这条路径必然是由黑结点和红结点相间构成的，此时红结点和黑结点的数量相同（非第二层的其他所有结点）。
有$n$个内部结点的红黑树的高度$h\leqslant2\log_2(n+1)$。
- 若红黑树的总高度为$h$，则根结点黑高$\geqslant\dfrac{h}{2}$，所以内部结点$n\geqslant2^{\frac{h}{2}-1}$（假设没有红结点），所以$h\leqslant2\log2(n+1)$。
红黑树查找、插入、删除的时间复杂度都是$O(\log_2n)$。
- 插入和删除：由于红黑树的每次操作平均要旋转一次和变换颜色，而普通二叉查找树如果平衡因子在指定范围内不会旋转（如果要旋转则可能旋转多次），所以它比普通的二叉查找树效率要低一点，不过时间复杂度仍然是$O(\log_2n)$。
- 普通查询：没有使用到红黑树的性质，所以红黑树和二叉查找树的效率相同。对于二叉平衡树而言，平衡树的效率更高。
- 插入数据有序查询：红黑树的查询效率就比二叉查找树要高了，因为此时二叉查找树不是平衡树，它的时间复杂度$O(n)$。
红黑树插入概述
假定当前结点为$x$，其父结点为$p$，叔父结点（父结点的兄弟结点）为$u$，祖父结点为$g$。
红黑树的插入过程和二叉查找树的插入过程基本类似，从右至左，右上至下。不同之处在于，红黑树中插入新结点后需要进行调整（主要通过重新着色或旋转操作进行），以满足红黑树的性质。
- 插入红黑树中的结点$x$初始着为红色。
假设新插入的结点初始着为黑色，那么这个结点质在的路径比其他路径多出一个黑结点（几乎每次插入都破坏性质⑤），调整起来也比较麻烦。如果插入的结点是红色的，此时所有路径上的黑结点数量不变，仅在出现连续两个红结点时才需要调整，而且这种调整也比较简单。
| 父结点 | 叔结点 | 插入类型 | 操作 |
|---|---|---|---|
| 黑 | - | - | 无需操作 |
| 红 | 黑 | 左左 | 右旋，变色 |
| 红 | 黑 | 右右 | 左旋，变色 |
| 红 | 黑 | 左右 | 左旋，右旋，变色 |
| 红 | 黑 | 右左 | 右旋，左旋，变色 |
| 红 | 红 | - | 父叔变黑，祖父变色，祖父变为当前结点，递归调整 |
- 父叔同色：只进行变色操作。
- 父叔异色，需要平衡二叉树同样的旋转：
- 父亲是左儿子，自己是左儿子，进行$L$旋转。
- 父亲是右儿子，自己是右儿子，进行$R$旋转。
- 父亲是左儿子，自己是右儿子，进行$LR$旋转。
- 父亲是右儿子，自己是左儿子，进行$RL$旋转。
以$1\sim7$的序列构建红黑树：
虽然有六种情况，但是由于两种是镜像的，所以归纳为四种。
父结点黑
默认插入结点为红色，且父结点为黑，所以此时插入后不影响黑高和平衡，从而不需要调整。
插入$2$，只有一个父结点为根结点，没有叔结点，直接插入到$1$的右子树位置，没有其他变化。
父结点红叔结点黑同侧插入
即插入类型为左左或右右，即在其祖父结点的左子树的左侧插入元素或其祖父结点的右子树的右侧插入元素。
由于插入结点为红色，父结点也为红色，不能出现连续的红色，所以就要变色，此时就应该先旋转。
由于是同侧插入，所以应该往另一侧旋转，旋转方式与二叉查找树一样，旋转完成后重新涂色。
插入$3$，$3$插入$2$的右子树位置，其父结点$2$为红色，而叔结点为$1$的左$NULL$结点为黑色，所以需要旋转，由于插入的是$2$的右侧，而$2$是其父结点的右子树，所以是同侧插入，需要反方向向左旋转，$2$结点上升变为根结点，$2$的左侧$NULL$结点给$1$结点的右侧，$1$下沉，$3$同样上升，完成旋转。然后涂色，根结点$2$为黑色，$NULL$为黑色，所以中间的$1$和$3$都涂成红色。
父结点红叔结点黑异侧插入
即插入类型为左右或右左，即在其祖父结点的左子树的右侧插入元素或其祖父结点的右子树的左侧插入元素。
此时红黑树末端会不平衡，此时就需要向插入的同侧方向旋转一下，从而变成父结点红树结点黑同侧插入的情况，再按照这个类型的处理方式进行处理。
插入$5$，注意此时图中是按同侧插入，即$5$是插入到$4$这个右子树的右侧的，而现在我们将$5$插入到$4$的左子树位置。$5$的父结点$4$是红色的，其叔结点$3$的左$NULL$结点是黑色的，而$5$插入的位置是$4$所在右子树的结点左侧，所以符合异侧插入的处理方式。首先对$4$和$5$这个子树进行右旋，将$5$右侧的$NULL$给$4$的左子树位置，$5$上升变成$3$的子结点，$4$下沉变成$5$的子结点。此时就是同侧插入插入的情况。再进行左旋，$5$的左$NULL$结点给当前父结点$3$的右子树位置，$5$上升变为父结点，变成$2$的子结点，$3$、$4$下沉变为$5$的子结点。此时红黑树形态一样，但是$2$的子结点从$1$和$4$变成了$1$和$5$。
父结点红叔结点红
由于插入结点为红色，父结点也为红色，不能出现连续的红色，所以就要变色。
这种情况是不需要进行旋转的。
由于父结点和叔结点都是红色，不能连续红色，所以将父结点和叔结点都涂为黑色；由于父结点和叔结点都是红色，所以其祖父结点一定是黑的，涂为黑色。此时将当前结点移动到祖父结点上，查看先祖结点的涂色是否正确，递归这个逻辑直到根结点，根结点一定是黑色的。
插入$4$，$4$插入$3$的右子树位置，由于不能连续的红色，所以其父结点$3$和叔结点$2$都变为黑色，祖父结点变为红色，由于祖父结点$2$为根结点，所以重新变成黑色。
红黑树删除概述
红黑树的播入操作容易导致连续的两个红结点，破坏性质④。而删除操作容易造成子树黑高的变化（删除黑结点会导致根结点到叶结点间的黑结点数量减少），破坏性质⑤。
所以红黑树删除要比红黑树插入更复杂。
删除过程也是先执行二叉查找树的删除方法。若待删结点有两个孩子，不能直接删除，而要找到该结点的中序后继（或前驱）填补，即右子树中最小的结点，然后转换为删除该后继结点。由于后继结点至多只有一个孩子，这样就转换为待删结点是叶结点或仅有一个孩子的情况。
- 前驱结点为二叉查找树中序遍历中当前点的前一个结点，往往在其左子树的最右测。
- 后继结点为二叉查找树中序遍历中当前点的后一个结点，往往在其右子树的最左测。
对于二叉查找树删除而言有三种情况：
- 被删除结点无子结点， 直接删除。
- 被删除结点只有一个子结点，用子结点替换要被删除的结点。
- 被删除结点有两个子结点，可以用前驱结点或者后继结点进行替换删除操作。
第一种情况不用多考虑，融合后两种情况并结合红黑树特性分为三种情况。
以完成所有插入后的红黑树为例。
$x$为父亲的左儿子：
- 兄弟为红色：将兄弟变成黑色，父节点变成红色；对父节点左旋，恢复左子树的黑色高度，左侄子成为新的兄弟。
- 兄弟为黑色，左右侄子为黑色：兄弟变成红色，$x$指向父节点，继续进行调整。
- 兄弟为黑色，右侄子为黑色（左侄子为红色）：左侄子变成黑色，兄弟变成红色；兄弟右旋，恢复右子树的黑色高度，左侄子成为新的兄弟。
- 兄弟为黑色，右侄子为红色：兄弟变成父节点颜色，父节点和右侄子变成黑色；父节点左旋，$x$指向整棵树的根节点，结束循环
填充结点红
即删除后用来填补该位置的结点为红色结点。
此时无论当前结点是什么颜色，删除后不影响黑高，所以不影响红黑树平衡。
- 当前结点为红：删除$4$，后继结点$5$为红结点，所以直接$5$替换$4$的位置并变红，其他不变。
- 当前结点为黑：删除$6$，后继结点$7$为红结点，所以直接$7$替换$6$的位置并变黑，其他不变。
填充结点黑且为左结点
即删除后用来填补该位置的结点为黑色结点，且该结点为其父结点的左子结点。
- 填充结点的兄弟结点是红结点：删除$2$，前驱结点$1$为黑结点，其兄弟结点$4$为红结点。
- 填充结点的兄弟结点是黑色，同时兄弟结点的右子结点是红色的，左子结点任意颜色：删除$4$，前驱结点$3$为黑结点，其兄弟结点$6$为黑结点，$6$的右子结点$7$为红结点。
填充结点黑且为右结点
即删除后用来填补该位置的结点为黑色结点，且该结点为其父结点的右子结点。
红黑树与二叉查找树
由二叉查找树树的“高度平衡”，降低到红黑树的“任一结点左右子树的高度，相差不超过两倍”的“适度平衡”，也降低了动态操作时调整的频率。对于一棵动态查找树，如果插入和删除操作比较少，查找操作比较多，采用$AVL$树比较合适，否则采用红黑树更合适。
二叉查找树使用平衡因子来约束树高，而红黑树用黑高相同约束树高。
二叉查找树只要平衡因子不超过$1$的绝对值就不用每次调整树整体，而红黑树每次插入货删除都需要进行对树进行调整。
红黑树与B树
红黑树在被发明之初被称为平衡二叉$B$树，所以红黑树与$B$树之间必然有联系。
- 将红黑树的所有红色结点上移到和他们的父结点同一高度上组成一个$B$树结点，就会得到一棵四阶$B$树。
- 红黑树的黑色结点个数与四阶$B$树的结点总个数相等。
- 在所有的$B$树结点中，黑色结点是父结点，红色结点是子结点。黑色结点在中间，红色结点在两边。
树表查找
B树
即多路平衡查找树，要求掌握基本特定点、操作。
B树定义
为了保证$m$叉查找树中每个结点都能被有效利用，避免大量结点浪费导致树高过大，所以规定$m$叉查找树中，除了根结点以外（根结点最小为$1$）：
- 任何结点至少有$\lceil\dfrac{m}{2}\rceil$个分叉，即至少包含$\lceil\dfrac{m}{2}\rceil-1$个结点。
- 至少有两棵子树。
- 数据最下面的为终端结点，查询失败的结点为叶节点。
为了保证$m$叉查找树是一棵平衡树，避免树偏重导致树高过大，所以规定$m$叉查找树中任何一个结点，其所有子树的高度都要相同。
而能保证这两点的查找树，就是一棵$B$树，即多路平衡查找树，多少叉，就是一棵多少阶的$B$树。
非叶结点定义：${n,P_0,K_1,P_1,\cdots,K_n,P_n}$。其中$K_i$为结点关键字，$K_1<K_2<\cdots<K_n$，$P_i$为指向子树根结点的指针。$P_{i-1}$所指子树所有结点的关键字均小于$K_i$，$P_i$所指子树的关键字均大于$K_i$。
B树性质
- 树的每个结点至多包含$m$棵子树，至多包含$m-1$个关键字。
- 若根结点不是终端结点，则至少有两颗子树，有一个关键字。
- 任意结点的每棵子树都是绝对平衡的。所有结点的平衡因子均等于$0$的。
- 除根结点以外的所有非叶结点至少有$\lceil\dfrac{m}{2}\rceil$棵子树，即至少包含$\lceil\dfrac{m}{2}\rceil-1$个结点。
- 每个结点中的关键字是有序的。子树$0$<子树$1$<子树$2$<……。
- 所有叶结点都出现在同一个层次上且不带信息。（可以视为外部结点或类似于折半查 找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。
- $B$树最底端的失败的不存在的结点就是常说的叶子结点，而最底端的存在数据的结点就是终端结点。（一般的树的叶子结点和终端结点都是指最底端的有数据的结点）
- 携带数据的是内部结点，最底部的叶子结点也称为外部结点。
$B$树相关性质计算涉及多个单元，注意一定要区分：
- 树高（默认是不包含无数据的叶子结点）。
- 子树棵数。
- 关键字。
- 结点（结点数往往小于关键字数）。
B树树高与关键字
$B$树中的大部分操作所需的磁盘存取次数与$B$树的高度成正比。高度一般与关键字相关。
计算$B$树高度大部分不包括叶子结点。若含有$n$个关键字的$m$阶$B$树。
- 最小高度：让每个结点尽可能满，有$m-1$个关键字，$m$个分叉，则一共有$(m-1)(m^0+m^1+m^2+\cdots+m^{h-1})$个结点，其中$n$小于等于这个值，从而求出$h\geqslant\log_m(n+1)$。
- 最大高度：
- 让各层分叉尽可能少，即根结点只有两个分叉，其他结点只有$\lceil\dfrac{m}{2}\rceil$个分叉，所以第一层$1$个，第二层$2$个，第$h$层$2(\lceil\dfrac{m}{2}\rceil)^{h-2}$个结点，而$h+1$层的叶子结点有$2(\lceil\dfrac{m}{2}\rceil)^{h-1}$个，且$n$个关键字的$B$树必然有$n+1$个叶子结点，从而$n+1\geqslant2(\lceil\dfrac{m}{2}\rceil)^{h-1}$，即$h\leqslant\log_{\lceil\frac{m}{2}\rceil}\dfrac{n+1}{2}+1$。
- 让各层关键字尽可能少，记$k=\lceil\dfrac{m}{2}\rceil$。第一层最少结点数和最少关键字为$1$；第二层最少结点数为$2$，最少关键字为$2(k-1)$，第三层最少结点数为$2k$，最少关键字为$2k(k-1)$，第$h$层最少结点数为$2k^{h-2}$，最少关键字为$2k^{h-2}(k-1)$，从而$h$层的$m$阶$B$树至少包含关键字总数$1+2(k-1)(k^0+k^1+\cdots+k^{h-2})=1+2(k^{h-1}-1)$，若关键字总数小于这个值，则高度一定小于$h$，所以$n\geqslant 1+2(k^{h-1}-1)$，则$h\leqslant\log_{\lceil\frac{m}{2}\rceil}\dfrac{n+1}{2}+1$。
B树关键字与结点
树高与结点：
- 对于已知树高和阶求最大最小关键字数量就是上面公式的逆运算。已知树高可以求出关键字数量。
- 根据关键字数量和结点之间的关系相除。求最大高度就除以每结点最小关键字数，求最小高度就除以每结点最大关键字数。
关键字与结点：
- 具有$n$个关键字的$m$阶$B$树，应有$n+1$个叶结点。
叶结点即查询失败的结点，对于$n$个关键字查找则可能的失败范围有$n+1$种。
- 有$n$个非叶结点的$m$阶$B$树中至少包含$(n-1)(\lceil\dfrac{m}{2}\rceil-1)+1$个关键字。
除根结点外的$n-1$个$m$阶$B$树中的每个非叶结点最少有$\lceil\dfrac{m}{2}\rceil-1$，然后再加上根结点的一个，所以最少为$(n-1)(\lceil\dfrac{m}{2}\rceil-1)+1$个。
B树查找
$B$树的查找包含两个基本操作：
- 在$B$树中找结点。
- 在结点内找关键字。
由于$B$树常存储在磁盘上，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法。
在$B$树上查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找，则说明树中没有对应的关键字，查找失败。
B树插入
新元素插入一定是插入到最底层的终端结点，使用$B$树的查找来确定插入位置。插入位置一定是最底层的某个非叶结点。
若导致原结点关键字数量超过上限溢出（$m-1$个关键字），就从中间位置$\lceil\dfrac{m}{2}\rceil$（如果是偶数则默认是$\lceil\dfrac{m}{2}\rceil-1$）分开，将左部分包含的关键字放在原来结点，右部分包含的关键字放在一个新结点，并插入到原结点的父结点的后一个位置上，而在原结点的父结点连接后的结点后移一个连接让位给分割出来的右半部分结点，中间的一个结点$\lceil\dfrac{m}{2}\rceil$插入到原结点的父结点上，并考虑在父结点的顺序对指针进行调整保证顺序。
若父结点插入时也溢出了，则同理在父结点的中间进行分割，左半部分在原来父结点；右半部分新建一个父结点，并把中间结点右边开始的所有连接移动到新父结点上；中间的结点上移到祖父结点，如果没有就新建，然后建立两个指针分别指向原父结点和新父结点。
B树删除
若被删除关键字在终端结点，且结点关键字个数不低于下限，则直接删除该关键字，并移动后面的关键字。
若被删除关键字在非终端结点，则用直接前驱或直接后继来替代被删除关键字，然后后面的元素直接前移：
- 直接前驱：当前关键字左侧指针所指子树遍历到最右下的元素。
- 直接后继：当前关键字右侧指针所指子树遍历到最左下的元素。
若被删除关键字在终端结点，但是结点关键字个数删除后低于下限：
- 右兄弟够借：若原结点右兄弟结点里的关键字在删除一个后高于下限，则可以用结点的后继以及后继的后继来顶替：
- 将原结点在父结点的连接的后一个关键字（后继元素）下移到原结点并放在最后面。
- 将原结点右兄弟结点的第一个关键字上移插入到下移的元素的空位。
- 原结点右兄弟结点里的关键字全部前移一位。
- 左兄弟够借：若原结点里右兄弟的关键字在删除一个后低于下限，但是左兄弟的结点足够，则可以用结点的前驱以及前驱的前驱来顶替：
- 将原结点在父结点的连接的前一个关键字（前驱元素）下移到原结点并放在最前面，其余元素后移。
- 将原结点左兄弟结点的最后一个关键字上移插入到原结点父结点的连接的前面。
- 原结点左兄弟结点里的关键字全部前移一位。
- 左右兄弟都不够借：若左右兄弟结点的关键字个数均等于下限值，则将关键字删除后与左或右兄弟结点以及父结点中的关键字进行合并：
- 将原结点的父结点连接后的关键字插入到原结点关键字最后面。
- 将原结点的左或右兄弟结点的关键字合并到原结点（前插或后插），并将连接也转移到原结点上。
- 若父结点的关键字个数又不满于下限，则父结点同样要于与它的兄弟父结点进行合并，并不断重复这个过程。
- 若父结点为空则删除父结点。（兄弟合并，父亲下沉）
B+树
$B+$树考的并不是很深。用于数据库。
与分块查找的思想类似，是对$B$树的一种变型，多用于索引结构。
B+树定义
一个$m$阶的$B+$树需要满足以下条件：
- 每个分支结点最多有$m$棵子树或孩子结点。
- 为了保持绝对平衡，非叶根结点至少有两棵子树，其他每个分支结点至少有$\lceil\dfrac{m}{2}\rceil$棵子树。（不同于$B$树，$B+$树又重新将最下面的保存的数据定义为叶子结点）
- 结点的子树个数与关键字个数相等。（$B$树结点子为树个数与关键字个数加$1$）
- 所有叶结点包含所有关键字以及指向记录的指针，叶结点中将关键字按大小排序，并且相邻叶子结点按大小顺序相互连接起来。所以$B+$树支持顺序查找。
- 所有分支结点中仅包含其各子结点中关键字的最大值以及指向其子结点的指针（即分支结点只是索引）。
B+树查找
无论查找成功与否，$B+$树的查找一定会走到最下面一层结点，因为对应的信息指针都在最下面的结点。而$B$树查找可以停留在任何一层。
$B+$树可以遍历查找，即从根结点出发，对比每个结点的关键字值，若目标值小于当前关键字值且大于前一个关键字值，则从当前关键字的指针向下查找。
$B+$树可以顺序查找，在叶子结点的块之间定义指向后面叶子结点块的指针，从而能顺序查找。
B+树与B树区别
对于$m$阶$B+$树与$B$树：
| B+树 | B树 | |
|---|---|---|
| 结点的n个关键字对应的子树个数 | n |
n+1 |
| 根结点的关键字数 | [1,m] |
[1,m-1] |
| 其他结点的关键字数 | [\lceil\dfrac{m}{2}\rceil,m] |
[\lceil\dfrac{m}{2}\rceil-1,m-1] |
| 关键字分布 | 叶子结点包含所有关键字，非叶结点包含部分重复关键字 | 所有结点的关键字不重复 |
| 结点作用 | 叶子结点包含信息，非叶子结点是索引作用 | 所有结点都包含信息 |
| 结点存储内容 | 叶子结点包含关键字与对应记录的存储地址，非叶子结点包含对应子树的最大关键字和指向该子树的指针 | 所有结点都包含关键字与对应记录存储地址 |
| 查找方式 | 随机查找、顺序查找 | 随机查找 |
| 查找位置 | 需要查找到叶子结点的最底层才能判断是否查找成功或失败 | 查找到数的任何地方都能判断 |
| 查找速度 | 非叶子结点不包含关键字对应记录的存储地址，可以使一个磁盘块含有多格关键字，从而让树的阶数更大，树更矮，读磁盘次数更是，查找更快 | 所有结点都包含存储地址，保存的关键字数量更少，树高更高，所以读写磁盘次数更多，查找更慢 |
散列表查找
线性表和树表中，数据位置与数据关键字无关，而散列表数据位置与关键字有关。
散列表定义
散列表又称哈希表，是一种数据结构，数据元素的关键字与其存储地址直接相关。一个散列结构是一块地址连续的存储空间。
散列函数
关键字与地址通过散列函数（哈希函数）来实现映射。即记录位置=散列函数(记录关键字)。
- 直接定址法：可表示为散列函数(关键字)=$a\times$关键字$+b$，其中$a$、$b$均为常数。这种方法计算特别简单，并且不会发生冲突，但当关键字分布不连续时，会出现很多空闲单元，会将造成大量存贮单元的浪费。
- 数字分析法：分析关键字的各个位的构成，截取其中若干位作为散列函数值，尽可能使关键字具有大的敏感度，即最能进行区分的关键字位，这些位数都是连续的。
- 平方取中法：先求关键字的平方值，然后在平方值中取中间几位为散列函数的值。因为一个数平方后的中间几位和原数的每一位都相关，因此，使用随机分布的关键字得到的记录的存储位置也是随机的。适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
- 折叠法：将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为散列函数的值。例如，假设关键字为某人身份证号码$430,1046,8101,5355$，则可以用$4$位为一组进行叠加，即有$5355+8101+1046+430=14932$，舍去高位，则有$H(430104681015355)=4932$。
- 随机数法：对于存储位置给定随机数安排，查找起来会很麻烦。
- 除留余数法：散列函数(关键字)=关键字$%p$，$p$一般是不大于表长的最大质数。这种方法使用较多，关键是选取较理想的$p$值，使得每一个关键字通过该函数转换后映射到散列空间上任一地址的概率都相等，从而尽可能减少发生冲突的可能性。一般情形下，取$p$为一个素数较理想，如果是合数则因为可以被多个数整除从而多个关键字余数相同造成冲突。
映射冲突
一般情况下，设计出的散列函数很难是单射的，即不同的关键字对应到同一个存储位置，这样就造成了冲突（碰撞）。此时，发生冲突的关键字互为同义词。
开放定址法
可存放新表项的空闲地址既向同义词开放也向非同义词开放。从发生冲突的那个单元开始，按照一定的次序，从哈希表中找出一个空闲的存储单元，把发生冲突的待插入关键字存储到该单元中，从而解决冲突。既指如果当前冲突，则将元素移动到其他空闲的地方。
$H_i=(H(key)+d_i)\mod m$。
- $i$表示发生第$i$次冲突，$i=1,2,\cdots,m-1)$。
- $m$为散列表长度，类似于循环队列，超出表长以后就循环到最左边。
- $d_i$为增量序列，是指发生第$i$次冲突的时候，$H(key)$偏移了多少位。
增量序列选择：
- 线性探测法：$d_i=1,2,3,\cdots,m-1$。线性探测法充分利用了哈希表的空间，但在解决一个冲突时，可能造成新的冲突。
- 二次（平方）探测法：$di=1,-1,2^2,-2^2\cdots,(\dfrac{m}{2})^2,-(\dfrac{m}{2})^2$。对比线性探测法更不容易产生聚集问题。注意：散列表长度$m$必须是一个可以表示为$4j+3$的素数才能探测到所有位置。
- 伪随机探测法：定义$d_i$是一个伪随机数。
- 再散列法：$d_i=Hash_2(key)$，又称双散列法。需要使用两个散列函数,当通过第一个散列函数$H(key)$得到的地址发生冲突时，则利用第二个散列函数$Hash_2(key)$计算该关键字的地址增量。它的具体散列函数形式：$H_i=(H(key)+i\times Hash_2(key))%m$。初始探测位置$H=H(key)%m$。$i$是冲突的次数，初始为$0$。在再散列法中，最多经过$m-1$次探测就会遍历表中所有位置，回到$H_0$位置。
聚集：同义和非同义关键字都堆积到一起。原因是选取不当的处理冲突的方法。对查找长度有直接的影响。
注意：在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此，要删除一个元素时，可给它做一个删除标记，进行逻辑删除。但这样做的副作用是:执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除。
链地址法
又称为拉链法或链接法，是把相互发生冲突的同义词用一个单链表链接起来，若干组同义词可以组成若干个单链表。思想类似于邻接表的基本思想，且这种方法适合于冲突比较严重的情况。
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
每次冲突都要重新哈希，计算时间增加。
公共溢出区法
为所有冲突的关键字记录建立一个公共的溢出区来存放。在查找时，对给定关键字通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表进行顺序查找。如果相对于基本表而言，在有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。
散列查找
查找实现
先通过散列函数计算目标元素存储地址，然后根据解决冲突的方法进行下一步的查询。
如果使用拉链法通过散列函数计算得到存储地址为空，则可以直接代表查找失败，这时候一般定义查找长度这里不算。
而如果使用开放地址法计算得到空位置的时候，代表查找失败，但是这时候需要定义查找长度要算这个地址。
若散列函数设计得足够好，散列查找时间复杂度可以达到$O(1)$，即不存在冲突。
散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。
装填因子=表中记录数÷散列表长度。装填因子代表一个散列表中的满余情况，越大则查找效率越低。
若只给出了装填因子$\alpha$，则此时平均查找长度为：$ASL=\dfrac{1}{2}(1+\dfrac{1}{1-\alpha})$。
查找长度计算
以题目为例：
现有长度为$11$且初始为空的散列表$HT$，散列函数是$H(key)=key%7$，采用线性探查 （线性探测再散列）法解决冲突。将关键字序列$87,40,30,6,11,22,98,20$依次插入$HT$。
首先构造散列表：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 98 | 22 | 30 | 87 | 11 | 40 | 6 | 20 |
查找失败的平均查找长度：
- 即获得一个新数据，在散列表中查找，发现找不到，那么如何判断找不到？当前位置为空，如比较到索引$8$后没有其他数据了，这时查询失败。（特别是有些题目数据存储位置是间断的，一定要注意到为空的位置就算查询失败）
- 首先由于模是模$7$，所以数据插入的范围是$0\sim6$，所以查找的范围是$0\sim6$。
- 比如查找一个值，模$7$后为$0$，从$0$开始一直对比到$8$这个位置，一共比较了$9$次。
- 同理一直到$6$结束，因为模运算结果是从$0\sim6$，所以一共$9+8+7+6+5+4+3=42$次。
- 由于是模$7$所以一共有比较七轮，所以最后平均查找长度为$42/7=6$。
计算查找成功的平均查找长度：
- 计算成功的长度，就是记录下每个数值比较了几次找到可存储的空间。
- 其中除了$20$前六个都是正好在对应的位置上，最后一个$20$本来应该在$6$位置上，因为冲突所以放在了$7$上，所以一共要对比$1+1+1+1+1+1+1+2=9$次。
- 由于一共$8$个数据，所以总的要比较$8$次，所以平均查找长度为$9/8=1.125$。