查找

基本概念

• 查找长度：在查找运算中，需要对比关键字的次数称为查找长度

• 平均查找长度(ASL)：其数量级反映了查找算法时间复杂度。(在二叉排序树中可见详细概念)

评价一个查找算法的效率时，通常考虑查找成功/查找失败两种情况的ASL。

线性查找

顺序查找

又称线性查找，通常用于线性表，其思想在于从头遍历到尾，简单粗暴。

顺序查找的实现：

1
2
3
4

typedef struct{
    ElemType *elem; //基于数组
    int TableLen;	//表长
}SSTable

1
2
3
4
5
6

int Search_seq(SSTable ST,ElemType key){
    ST.elem[0] = key; //设置哨兵，
    int i;
    for(i = ST.TableLen;ST.elem[i]!=key;--i);//从后向前查找
    return i; //查找成功，直接返回下标，查找失败，此时下标位于哨兵处，返回0；
}

优化：对于一个递增/递减表，每一轮判断一下表中元素与查找目标的大小关系即可完成任务。

查找成功结点ASL：自身所在层数

查找失败结点ASL：父节点所在层数

对于查找元素被查概率不等的表，可以将被查概率大的放在靠前位置，优化ASL，同时最坏查找情况变差。

二分查找

又称折半查找，仅适用于有序的顺序表(链表因没有随机访问的特性故无法使用)

• 核心思想：在每一轮都与中间值作比较，直至成功或失败跳出.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

typedef struct{
    ElemType *elem;
    int TableLen;
}SSTable;
int Binary_Search(SSTable L,ElemType key){
    int low=0,high=L.TableLen-1,mid;
    while(low<=high){ //左闭右闭区间
        mid = (low+high)/2;//取中间值
        if(L.elem[mid]=key){
            return mid;//查找成功
        }else if(L.elem[mid]>key){
            high=mid-1;//左半区域查找
        }else{
            low=mid+1;//右半区域查找
        }
    }
    return -1;
}//样例代码适用于升序顺序表，降序需更改判断条件。

在代码中需要注意循环不变量，即每一次while循环中判断的key值是在左闭右闭区间还是左闭右开区间

参考卡哥的二分查找详解(代码随想录 (programmercarl.com)

• 折半查找的判定树一定是平衡二叉树
• 折半查找的判定树中，只有最下面一层是不满的，因此元素n的树高h=|log~2~(n+1)|（该树高不包含失败节点）
• 其算法时间复杂度为O(log₂n)

分块查找

又称索引顺序查找，算法过程如下：

1. 在索引表中确定待查记录所属的分块(可顺序，可折半)
2. 在块内顺序查找

使用折半查找查索引时：

若索引表中不包含目标关键字，则折半查找索引表最终停在low>high，要在low所指分块中查找

因为要跳出while循环，low必须大于high

效率分析

设长度为n的查找表被均匀地分为b块，每块s个元素

如果采用顺序查找索引块，则 $$ ASL = \frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2}\ 当s=\sqrt{n}时\ ASL_{最小}=\sqrt{n}+1 $$

如果采用折半查找索引块，则

$$ASL = \lceil log_{2}(b+1) \rceil +\frac{s+1}{2}$$

树形查找

二叉排序树BST

一个具有以下特性的二叉树：

1. 若左子树非空，则左子树所有结点值均小于根节点值
2. 若右子树非空，则右子树所有节点值均大于根节点值
3. 左右子树本身也是二叉排序树

可以是一个空树，对二叉排序树进行中序遍历将得到升序序列

删除

分三种情况：

1. 若删除的是叶节点，则不需要进行额外处理
2. 若结点z只有一棵左子树或右子树，则让z的子树成为z父节点的子树，替代z的位置
3. 若结点z有左右两棵子树，令z的直接后继或直接前驱替代z，从二叉排序树中删掉该直接后继或直接前驱，转为1或2情况

效率分析

与二分查找判定树类似，ASL也类似，但二分查找的判定树唯一，二叉排序树的查找不唯一

对于维护表(删除、插入结点)，二叉排序树只需修改指针即可完成，平均执行时间为O(log₂n)，适合动态查找表

而二分查找的维护，平均执行时间为O(n)，适合静态查找表

平衡二叉树AVL

在二叉排序树的基础上，对插入与删除操作进行规范，满足以下特性：

1. 任意结点的左右子树高度差的绝对值不超过1
2. 左右子树均是平衡二叉树

插入

在插入前，检查插入路径上的结点是否因此次操作导致不平衡，若不平衡：

找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，对以A为根节点的子树，进行调整

• 即LL LR RL RR平衡旋转

LL平衡旋转(右单旋转)：即在A的左孩子L的左子树L插入新节点

1. 将A的左孩子右上旋转代替A成为根节点

2. A结点向右下旋转成为B的右子树的根节点

3. B的原右子树作为A结点的左子树

RR平衡旋转(左单旋转)：在A的右孩子R的右子树R插入新节点

1. 将A的右孩子左上旋转成为根节点

2. A结点向左下旋转成为B的左子树的根结点

3. B的原左子树成为A的右子树

LR平衡旋转(先左后右双旋转)：在A的左孩子L的右子树R插入新节点

1. 将B左旋成为C的左子树

2. 将A右旋成为C的右子树

RL平衡旋转(先右后左双旋转)：在A的右孩子R的左子树插入新节点

1. 将B右旋成为C的右子树

2. 将A左旋成为C的左子树

删除

使用二叉排序树的删除方法对结点w进行删除后

1. 从w结点开始，向上回溯，找到第一个不平衡的结点z，设y为结点z的高度最高的孩子结点，x为结点y的高度最高的孩子结点

2. 对以z为根的子树进行平衡调整，此时x,y,z有4种位置分布：

   • y为z的左孩子，x为y的左孩子，进行LL

   • y为z的左孩子，x为y的右孩子，进行LR

   • y为z的右孩子，x为y的左孩子，进行RL

   • y为z的右孩子，x为y的右孩子，进行RR

查找

以n_h表示深度为h的平衡树拥有的最少结点数，则显然n0=1，n1=1，n2=2，且n_h = n_h-1+n_h-2+1

则其最大深度为log₂n，ASL=O(log₂n)

红黑树

满足如下特性的二叉树：

• 每个节点或黑或红，根节点定为黑色

• 叶节点(虚构的外部节点、NULL结点)都是黑色

• 不存在两个相邻的红节点，红节点的父节点和子节点全黑

• 对每个结点，从该节点到任意叶节点的简单路径上，所含黑节点的数量相同

*待施工*

B树

满足下列条件的树称为m阶B树，又称多路平衡查找树

1. m叉查找树中，规定除了根节点外(最少有一个关键字)，任何节点至少有$\lceil m/2 \rceil$个子树，即至少含有$\lceil m/2 \rceil-1$个关键字，最多$m-1$个关键字。

2. m叉查找树，规定对于任何一个节点，其所有子树的高度都要相同

3. 所有叶子节点都出现在同一层次上，并且不带信息，查到叶子结点说明查找失败，又称失败节点

如何让B树高度达到最大：

1. 保证各层分叉尽可能少，即根节点两个分叉，其他节点$\lceil m/2 \rceil$个分叉
2. 各层节点至少$2\lceil m/2\rceil^{h-2}$个，第h+1层共有叶子节点$2\lceil m/2 \rceil^{h-1}$
3. n个关键字的B树必有n+1个叶子节点，则$n+1 \geq 2\lceil m/2 \rceil^{h-1}$，解出h即是B树的最大高度

插入

​ 新元素一定是插入到最底层“终端节点”，用“查找”来确定插入位置。

• 插入key时，若导致原节点关键字数超过上限，则从中间位置($\lceil m/2 \rceil$)将其中的关键字分为两部分，左部分包含的关键字放在原节点中，右部分包含的关键字放到新节点中，中间位置($\lceil m/2 \rceil$)的节点插入原节点的父节点

• 如果向上新增的关键字导致父节点关键字超限，则继续进行分裂，直到传递到根节点，导致树高+1

删除

分有四种情况：

1. 若被删除关键字在终端节点，则直接删除该关键字

2. 若被删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字

直接前驱：当前关键字左侧指针所指子树最右下的元素

3. 被删结点的兄弟够借：
   1. 若删除前结点的关键字数量已经最小$\lceil m/2 \rceil-1$，兄弟结点关键字数$\geq \lceil m/2 \rceil$
   2. 通过父子换位法，使结点达到新平衡

• 当右兄弟很宽裕时，用当前节点的后继、后继的后继来填补空缺。
• 当左兄弟很宽裕时，用当前节点的前驱、前驱的前驱来填补空缺。

4. 兄弟不够借：将关键字删除后与左或右兄弟结点及双亲结点中的关键字进行合并

• 逐层向上合并

B+树

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

1. 每个分支节点最多有m棵子树
2. 非叶根节点至少有两颗子树，其他每个分支节点至少有$\lceil m/2\rceil$棵子树
3. 结点的子树个数与关键字个数相等
4. 所有叶节点包括全部关键字及指向相应记录的指针，叶节点中将关键字按大小顺序排列，且相邻叶节点按大小顺序相互连接，支持顺序查找，这也是与B数最大的不同
5. 所有分支节点中仅包含它的各个子结点中关键字的最大值及指向其子节点的指针

散列查找

​ 散列表(Hash Table),又称哈希表。其特点是数据元素的关键字与其存储地址直接相关。

• 若不同的关键字通过散列函数映射到同一个值，则称他们为“同义词”
• 通过散列函数确定的位置已经存放了其他元素，则称折冲情况为“冲突”

常见的散列函数

1. 除留余数法—-$H(key)=key%p$

   • 散列表表长为m,取一个不大于m但最接近或等于m的质数p
   • 取质数是因为可以让数据更均匀分布在表上，冲突更少—详见《数论》

2. 直接定址法—-$H(key)=key$或$H(key)=a*key+b$

   • 适用于关键字的分布基本连续的情况

   • 不会产生冲突。

3. 数字分析法—–选取数码分布较为均匀的若干位作为散列地址

4. 平方取中法—–取关键字的平方值的中间几位作为散列地址

   • 这种方法得到的散列地址与关键字的每位都有关系，使得散列地址分布比较均匀(不代表不发生冲突)

散列函数是典型的”用空间换时间“的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。

处理冲突的方法

1. 开放定址法

   • 指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。

   1. 线性探测法：发生冲突时，每次往后探测相邻的下一个单元是否为空。

      • 线性探测法很容易造成同义词，非同义词的”聚集现象“，严重影响查找效率

   2. 平方探测法

   • 散列表长度m必须是一个4j+3的素数，才能探测所有位置
   3. 伪随机序列法
   4. 再散列法：准备多个散列函数，当通过第一个散列函数得到的地址发生冲突时，利用第二个散列函数计算地址增量

采用开放定址时，删除节点需要进行删除标记，进行逻辑删除，否则将截断在它之后填入散列表的同义词结点查找路径

2. 拉链法：

把所有的”同义词“存储在一个链表中

​ 装填因子$\alpha = \frac{记录数n}{表长m}$

• 装填因子的大小将直接影响查找效率，$\alpha$越大装填记录越满，越容易冲突
• ”冲突“越多，查找效率就越低，所以散列(哈希)函数的定义非常关键