Ch7 查找

效率指标

1. 平均查找长度 $ASL=\frac{1}{n}{\Sigma }_{i=1}^n{l}_i$ ，其中 $\frac{1}{n}$ 说明每个元素查找概率相等。若查找概率不相等则使用通用公式 $ASL={\Sigma }_{i=1}^n{p}_i{l}_i$
2. ASL 包括查找成功的 ASL 和查找失败的 ASL

线性结构查找

顺序查找

性质

1. $AS{L}_{成功}=\frac{n+1}{2}=\frac{1}{n}\frac{n(n+1)}{2}=从1加到n$
2. $AS{L}_{失败}=n+1$ (其中 n 个元素共比较 n 次，最后还需一次比较以确认列表结束)

折半查找

性质

1. 时间复杂度为 $O(logn)$
2. 折半查找的判定树是一棵平衡二叉树
3. 折半查找和二叉排序树的时间性能不一定相等，因为折半查找的判定树肯定是平衡树，时间复杂度永远是 $O(logn)$ ，而二叉排序树跟输入顺序有关，有可能会成为一个单支树，此时时间复杂度变成 $O(n)$
4. 折半查找对应的二叉排序树的高度是 $h=\lceil {\log }_2(n+1)\rceil$
5. 求折半查找的查找成功 ASL，可以先画出判定树，然后根据图求出所有关键词的权值的和；求查找失败 ASL，可以补全判定树的所有失败结点，然后求出所有失败结点的父结点的权值的和

代码

int Binary_Search(SSTable L,ElemType key){
	int low=0,high=L.TableLen-1,mid;
	while(low<=high){
		mid=(low+high)/2;//一般向下取整；
		if(key<L.elem[mid]){
			high=mid-1;
		}
		else if(key>L.elem[mid]){
			low=mid+1;
		}
		else{
			return mid;//查找成功则返回位置；
		}
	}
	return -1;//查找失败 返回-1；
}

分块查找 (索引顺序查找)

基本思想

把查找表分为若干子块。块内元素可以无序，块间元素是有序的。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

性质

1. 分块查找的平均长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的平均查找长度为 $L_I$ 和 $L_S$ ，则分块查找的平均查找长度为 $ASL=L_I+L_S$
2. 将长度为 n 的查找表均匀分为 b 块，每块有 $s=\frac{n}{b}$ 个记录，在等概率情况下，若在块内和索引表中均采用顺序查找，则 $L_I=\frac{b+1}{2}$ ， L_S=\frac{s +1}{2}$$ASL=\frac{b+s+2}{2}=\frac {s^2+2s+n}{2s} ，当 $s=\sqrt{n}$ 时， $AS{L}_{min}=\sqrt{n}+1$

树形结构查找

二叉排序树

性质

1. ASL 为 $O(logn)$ ，最差情况下 ASL 为 $O(n)$
2. 二叉排序树的左子树的所有结点都小于根结点的值
3. 二叉排序树的右子树的所有结点都大于根结点的值
4. 左、右子树也是二叉排序树
5. 动态查找表适合使用二叉排序树作为其逻辑结构。而静态查找表适合使用顺序表作为存储结构，采用折半查找实现查找操作

操作

查找

将 key 与根结点作比较，key 小于（大于）根结点则递归查找左子树（右子树）。

插入

树为空就直接插入，key 小于（大于）根结点则递归插入左子树（右子树）。

代码

int BST_insert(BiTree &T,KeyType k){
	if(T==NULL){//若原树为空
		//分配新结点为根结点
		T=(BiTree)malloc(sizeof(BSTNode));
		T->data=k;
		T->lchild=NULL;
		T->rchild=NULL;
		return 1;//返回1，插入成功
	}
	else if(k<T->data){
		return BST_insert(T->lchild,k);//若关键字小于该结点则递归插入左子树
	}
	else if(k>T->data){
		return BST_insert(T->rchild,k);//若关键字大于该结点则递归插入右子树
	}
	else {
		return 0;//已存在相同关键字结点，插入失败
	}
}

删除

二叉排序树的删除有三种情况：

1. 若被删除结点 $z$ 是叶结点，则直接删除
2. 若 $z$ 只有一颗左子树或右子树，则让 $z$ 的子树替代 $z$ 的位置
3. 若 $z$ 有左右两棵子树，则令 $z$ 的直接后继（或直接前驱）替代 $z$ ，然后删除这个直接后继（或直接前驱）的原本位置

平衡二叉树（AVL 树）

性质

1. 定义结点左右子树的高度差为高度因子，高度因子只可能是-1、0 或 1
2. $n_h$ 层 AVL 树的最少结点数为 $n_h=n_{h-1}+n_{h-2}+1$

操作

插入

每次调整的对象都是最小不平衡子树。当因为插入一个元素而导致出现两个不平衡点，应该调整距离插入结点最近的不平衡点。

==秒杀方法：调整方法为沿最小不平衡子树的根结点到新插入的结点这条路径，选前三个结点，调整这三个结点的大小位置，再将剩余结点按大小添加进去。==

LL 型

当插入元素后构成 LL 型，如下图所示，则以 2 为支，高右转，把 3 右旋下来保证平衡。

RR 型

当插入元素后构成 RR 型，如下图所示，则以 2 为支，高左转，把 1 左旋转下来保证平衡。

LR 型

当插入元素后构成 LR 型，如下图所示，先 2,3 整体左旋，在根据 LL 型进行右旋转来保证平衡。

RL 型

当插入元素后构成 RL 型，如下图所示，先将 5 右转，在与 6 进行交换，在根据 RR 型进行旋转来保证平衡。

删除

1. 用 [[#二叉排序树#删除 | 二叉排序树的删除]] 方法对结点进行操作。
2. 若导致了不平衡则找到最小不平衡子树和二叉排序树的四种插入（LL 型， RR 型， LR 型， RL 型 ）一样调整至平衡。

==秒杀方法：选最小不平衡子树的根结点以及树高更高的一边子树的根结点和该子树的树高更高的子树根结点，共三个结点，调整这三个结点的大小位置，再将剩余结点按大小添加进去。==

查找

和[[#二叉排序树#查找|二叉排序树的查找]]过程相同

红黑树

为了解决平衡二叉树（AVL 树）频繁调整全树拓扑结构导致的开销较大的问题，在 AVL 树的平衡标准上进一步放宽条件，引入了红黑树的结构。

性质

一颗红黑树是满足如下红黑性质的二叉排序树：

1. 每个结点是红色或是黑色的
2. 根结点是黑色的
3. 叶子结点（虚构的外部结点、NULL 结点）都是黑色的
4. 不存在两个相邻的红结点
5. 对每个结点，从该结点到任意一个叶子结点的简单路径上，所含黑结点的数量相同 （每个结点的左右黑色结点数相等）
6. 从根到叶结点的最长路径不大于最短路径的 2 倍
7. 有 n 个内部结点的红黑树的 $高度h\le 2lo{g}_2(n+1)$

由于红黑树不能有两个连续红结点，所以一条简单路径上至少一半是黑结点，再结合 5. ，所以没有一条路径会比其他路径长出两倍，可推出 6. 。因而，红黑树是相对接近平衡的二叉树。

由于从根结点到任意一个叶子结点的简单路径上，都至少有一半是黑色结点，所以树的黑高至少为 $h/2$ ，于是有 $n\ge 2^{h/2}-1$ ，可推出 7.

操作

插入

1. 插入的结点默认是红结点
2. 如果插入的是根结点，直接变黑
3. 看叔叔结点的颜色：
   1. 红色：则插入结点的上面的三角颜色取反。
   2. 黑色：则取新插入结点、父结点、爷结点进行排序，将中间值提为黑根，左右子树根是红结点。(类似于[[#平衡二叉树（AVL 树）#插入|平衡二叉树的插入]]方法，只是需要额外调整颜色)

删除

//todo

B 树

$M$ 阶 B 树是所有结点的平衡因子均等于 0 的 m 路平衡查找树。

性质

一颗 $m$ 阶 B 树或为空树，或为满足以下特性的 $m$ 叉树

1. 树中每个结点至多有 $m$ 棵子树，即至多有 $m-1$ 个关键字
2. 若根结点不是叶结点，则至少有 2 棵子树，1 个关键字
3. 除根结点外的所有非叶结点至少有 $\lceil m/2\rceil$ 棵子树，即至少有 $\lceil m/2\rceil -1$ 个关键字
4. 所有叶结点都出现在同一层次上，并且不带信息（类似折半查找 判定树的失败结点）

大多数教材把 B 树的叶结点定义为失败结点，但是 408 真题却常将 B 树的叶结点定义为最底层的终端节点。实际做题时要注意区分。

操作

插入

1. 先计算出该 $m$ 阶 B 树的每个结点的关键字个数最多为 $m-1$ 个
2. 定位要插入的位置并插入
3. 插入后看如果超过了关键字个数最大值，则取中间位置 $\lceil m/2\rceil$ 的值，提到父结点中，原结点就左右两边分裂成两个新结点。如果导致父结点的关键字个数也超了上限，则继续分裂，向上传递，直到传到根结点为止，则导致 B 树高度+1

删除

1. 先计算出该 $m$ 阶 B 树的每个结点的关键字个数最少为 $\lceil m/2\rceil -1$ 个
2. 当要删除的关键字 $k$ 不在终端结点中时，使用 $k$ 的前驱（或后继） $k^{\prime }$ 替代 $k$ 然后删除终端结点中的 $k^{\prime }$ 。（类似于 [[#二叉排序树#删除|二叉排序树的删除]]中的将删除结点转化为叶子结点的思想）
3. 然后只需讨论关键字 $k$ 在终端结点的情况：
   1. 若删除后关键词个数满足最少个数，则直接删除
   2. 若不满足，但是兄弟够借，则向父亲借一个，父亲向兄弟借一个，然后删除结点
   3. 若兄弟也不够借，则向父亲借一个，然后此时足够删除了，但是此时父结点关键词少了一个，所以分叉减一，于是把原结点和兄弟结点合并

B+树

B+树是应数据库所需而出现的一种 B 树的变形树。

与 B 树的差异

1. B+树中， $n$ 个关键字对应 $n$ 个子树，即一个关键字对应一个子树；B 树中 $n$ 个关键字的结点含有 $n+1$ 棵子树
2. B+树中结点的关键字个数范围是 $\lceil m/2\rceil \le n\le m$ （非叶根结点最少 2 个），整体比 B 树多一个
3. B+树中，叶结点包含了全部关键字，非叶结点中出现的关键字也会在叶结点中重复出现；B 树中结点的关键字是不重复出现的
4. B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点的每个索引项只含有对应子树的最大关键字和指向该子树的指针，这样使一个磁盘块存储更多的关键字，使磁盘读写次数更少，查找速度更快
5. B+树中，用一个指针指向关键字最小的叶结点，将所有叶结点串成一个线性链表
6. B+树的查找过程中，非叶结点的关键字等于查找值时并不停止，而是继续向下查找，直到叶结点上的该关键字为止

散列结构查找 (散列表、Hash 表)

散列函数

直接定址法

$H(key)=key$ 或 $H(key)=a\times key+b$

计算简单，不会冲突，适合关键词分布基本连续的情况，若关键词分布不连续，空位较多，会造成存储空间的浪费。

除留余数法

$H(key)=key\mathrm{mod}p$ （ $p$ 不大于散列表表长 $m$ 但最接近或等于 ）

数字分析法

设关键词是 $r$ 进制数，而 $r$ 个数码在各位出现的频率不一定相同，选取数码分布较为均匀的若干位作为散列地址。这种方法适用于已知的关键字集合，更换关键字后需要重新构造新的散列函数。

平方取中法

取关键字的平方值的中间几位作为散列地址。

处理冲突的方法

开放定址法

Tip

在开放地址散列表中，删除操作要小心。通常只能“懒惰删除”，即需要增加一个“删除标记（Deleted）”，而并不是真正删除它，不然会影响查找时的判断，其空间可以再下次插入时重用。

线性探测法

发生冲突时，顺序查看表中下一个单元，直到找到一个空闲单元，或查遍全表。

线性探测法可能使大量元素在相邻的散列地址上聚集（或堆积） 起来，大大降低查找效率，堆积现象直接影响 ASL。

平方探测法（二次探测法）

$d_i=1^2,-1^2,2^2,-2^2,...,k^2,-k^2$ ，其中 $k\le m/2$ 散列表长度 $m$ 必须是一个可以表示成 $4k+3$ 的素数。

不能探测到散列表上的所有单元，但至少能探测到一半单元。

双散列法

$d_i=i\times Has{h}_2(key)$

$H_i=(H(key)+i\times Has{h}_2(key))\mathrm{mod}m$

初始探测位置 $H_0=H(key)\mathrm{mod}m$ . $i$ 是冲突的次数。

伪随机序列法

$d_i$ 为伪随机数序列

拉链法（链接法，chaining）

适用于经常插入、删除的情况。

使用 $m$ 个链表，将这些链的链首指针构成一个指针数组。

散列查找及性能分析

散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。

$装填因子\alpha =\frac{表中记录数n}{散列表长度m}$

散列表查找失败的 ASL：长为 $m$ 的散列表有 $m$ 种查找失败的情况，每一种都要遍历一直到空位置时在判断查找失败。