考研数据结构——(查找)

查找

一、查找的基本概念
二、顺序、折半、分块查找
三、树形查找
四、 B树与 B+树的基本概念
五、散列表

一、查找的基本概念

查找、查找表、关键字的概念

在这里插入图片描述

静态查找表与动态查找表

在这里插入图片描述

查找长度与平均查找长度

在这里插入图片描述

查找成功计算

在这里插入图片描述

查找失败的计算

在这里插入图片描述

二、顺序、折半、分块查找

2.1 顺序查找

算法思想

就是从头到脚

算法实现

顺序查找的代码

在这里插入图片描述

哨兵模式下的顺序查找

通过哨兵的方式，牺牲第一个存储位置，从后向前找。如果到哨兵的位置还没找到，就返回哨兵的位置0;
哨兵这个方式，不用判断越界问题

在这里插入图片描述

查找效率分析

ASL（平均查找次数），即成功平均查找次数与失败平均查找次数。

在这里插入图片描述
⭐ 查找判定树

在这里插入图片描述

算法优化

排序优化

将查找表有序
假如在升序表查找一个数时，如果已经大于查找的数了，就可以断定查找失败了，不用查到底部了。

查找概率优化

这种情况就是把经常搜索的置于表前部。
利于成功查找算法，对于失败查找，这个优化还是要遍历全表。

在这里插入图片描述
5. 顺序查找的知识总结

在这里插入图片描述

2.2 折半查找

算法思想

要求查找表是有序的顺序表

在这里插入图片描述

增序的查找表折半查找代码

原理

设置 low 指向最小元素的下标， high 指向最大元素的下标。
取中间 mid，与查找数据x进行比较；
当 mid指向元素大于 x，（也就是 x在mid的左侧，所以最大值调整到mid前一个元素，为啥是前一个？因为 mid处元素不是要找的）设置high = mid-1；
同理， mid指向的元素小于 x， low = mid + 1；
直到找到x，否则 low 大于 high 时终止。

在这里插入图片描述

折半查找的判定树

注意失败查找的紫色方块并不是结点，而是指向它的结点对比失败的情况，所以在做折半查找成功/失败平均搜索长度时注意不要算错。

折半查找的判定树

⭐ 判定树的构造

注意结点总数是奇数/偶树分层的情况
- 奇数时
1. 选择中间结点分层
- 偶数时
1. 可以选择 [n/2] 向下取整，即选择较小的数作为中间结点，另一个结点在其右子树；
2. 可以选择 [n/2] 向下取整 + 1，即选择较大的数作为中间结点，另一个结点在其左子树；

在这里插入图片描述

在这里插入图片描述

例如

折半查找一定是平衡二叉树，元素个数为n，其数高为 [log2(n+1)] 向上取整
并且折半查找判定树也符合二叉排序树，并且失败个数正好等于空指针链域的个数

在这里插入图片描述

折半查找的查找效率

注意查找效率区别二叉排序树，可能等于二叉排序树，也有可能不等于，不等于的情况例如二叉排序树只有左右子树的情况。

扩展思维

在这里插入图片描述
6. 折半查找小总结

在这里插入图片描述

2.3 分块查找

分块查找的思想

分块查找的算法思想：其实就是存储的元素，块内无序，块间有序
可以建立一个索引表，索引元素存储一个块内的最大元素和这个块的开始和结束位置

在这里插入图片描述

查找过程

在这里插入图片描述
⭐ 折半查找索引块时应该注意，假如查找元素不是索引块存储的元素
a. 查找元素正好存储在索引块

折半查找查找索引表时，如果查找元素正好是索引表所标识的之间，等于就行

在这里插入图片描述

b. 查找元素不存在索引块

那么折半查找low>high
此时low指向的块索引就是要查找元素所在的块
因为索引表中保存的是最大的元素
所以，我们要找的元素一定是在小于这个最大的元素的块中

在这里插入图片描述

c. 查找元素不在范围

在这里插入图片描述

分块查询的效率分析

索引表采用顺序查询方式，查询一个元素的位置

顺序查询索引表
再顺序查找块内元素

或者

索引表按折半查找
然后块内按顺序查找。

在这里插入图片描述
a . 顺序查索引表

2. 折半查索引表

⭐ 如何最高效率分块?

n条记录，每块只有根好n个记录时，分块，asl最小

分块查询知识点总结

在这里插入图片描述

三、树形查找

3.1二叉搜索树(二叉排序树) (BST)

二叉排序树的定义

在这里插入图片描述

二叉排序树的查找代码

⭐ 采用非递归的方式实现

因为二叉排序树，左子树的结点值都小于当前结点，右子树的结点值都小于当前结点。
因此查找时，根节点不为空，如果查找的值x小于根节点，则向左子树查找；如果x大于根节点的值，则向右子树开始查找；
依次直到找到，或遍历到null；

在这里插入图片描述

⭐采用递归方式实现

在这里插入图片描述

⭐ 递归实现和非递归实现的区别

针对于空间复杂度

非递归(循环) 实现，空间复杂度最差为 O(1);
递归实现，空间复杂度为 O(h); 取决于树的高度；

二叉排序树的插入代码

⭐ 递归实现

插入的结点一定是叶子结点；
注意函数的结点遍历是引用类型，因为插入是带的插入的值一直找到合适的叶子结点处，判断是比叶子结点大还是小，从而插入到其的左右孩子结点(也就是创建一个新的叶子结点)。

在这里插入图片描述
⭐ 采用非递归方式实现

坑🕳。。。。。。。后续补

二叉排序树的构建

其实就是：

首先初始化一个空根；
然后遍历插入序列（可以通过数组存放），将每个遍历值，执行BST_Insert——也就是二叉排序树的插入函数；

注意可能不不同的插入序列，生成的二叉排序树是一棵树；

在这里插入图片描述

二叉排序树的删除（删除位置不同，复杂程度不同⭐）

删除叶子结点的思想

叶子节点，直接删除，不会影响二叉排序树的结构

在这里插入图片描述

删除只有左子树或者右子树的中间结点

假如删除只有左子树的中间结点，那么直接用删除结点的左指针的结点(左子树) 替代要删除的结点即可；
假如删除的结点只有右子树，那直接用删除结点的右指针代替删除结点即可；

在这里插入图片描述
3. 🌙 删除的结点即有左子树，也有右子树。

⭐ 方法一：通过直接后继补位删除

就是因为二叉排序树的中序遍历就是有序的序列，所以删除一个结点即有左子树，又有右子树；则

用这个结点的直接后继代替其值；（直接后继就是该结点的右子树的最左下的结点）
再将其直接后继删除（其直接后继一定是没有左子树[所以，直接后继可能是叶子结点，也可能是只有右子树的结点；所以该结点的处理遵守前两种删除方案]）

在这里插入图片描述

⭐ 方法二：用删除结点的直接前驱代替要删除的结点

我们要删除的结点，通过其直接前驱代替，则：

要删除的结点，用其直接前驱代替；（直接前驱，是要删除结点的左子树的最右下结点）；
删除其直接前驱结点（该结点一定是没有右子树，只有两种情况：叶子结点、只有左子树的结点）删除该结点，要遵守前两种删除方案；

在这里插入图片描述

二叉排序树，查找效率分析(平均查找长度)

二叉排序树的平均查找长度取决于其树的高度，最坏的情况也就是 O(h)； h是树高，因此我们在构建一个二叉排序树的时候，尽量的让它排成一个树高较矮的树，尽可能的保持平衡，称为一个二叉排序平衡二叉树；
如果我们的二叉排序树能够保持平衡，那么它的平均查找长度就是 O (log2 n);

查找成功的平均查找长度 asl
查找失败的平均查找长度 asl

在这里插入图片描述

二叉排序树的知识点回顾

在这里插入图片描述

3.2 平衡二叉树（AVL）

平衡二叉树的概念

注意平衡因子的概念：其值等于左子树高 - 右子树高

如何在构建平衡二叉树（插入）？

构成不平衡的原因！

调整最小不平衡树，具体调整方法在下文；

在这里插入图片描述
🌙 2. 调整最小不平衡子树

⭐a. LL情况（A的左孩子的左子树中插入导致不平衡）

思考为什么所有子树高度都是H？

假如 AR不是H，那么无非就是 h-1，那么A本身就是不平衡因子，不用插入就造成了！那么为h+1时， LL插入，并不会造成不平衡
如何BR 不是 H，那么无非就是 h+1，这时候A本身也是不平衡，如何使h-1，此时LL插入，造成的不平衡因子是B，不是我们要解决的A；

解决思想：

将A的左孩子作为A；
然后按照 BL < B < BR < A < AR 的方式调整；
口诀就是：右单旋转；

在这里插入图片描述

⭐ b. RR情况（在A的右孩子的右子树中插入导致不平衡）

为什么子树高度都是H？类LL分析即可；
解决不平衡的思想：

将A的右子树作为A；
根据 Al < A < BL < B < BR 的顺序进行调整；
口诀就是：左单旋转；

在这里插入图片描述
⭐ LL 与 RR 解决不平衡的代码思想

⭐ c. LR情况（A的左孩子的右子树插入导致的不平衡）

解决思想，将C(A的左孩子的右子树) 先左上旋调整，再将B(C的父结点) 右上旋调整；目的是为了将C放到A的位置。

左旋，右旋都遵守 BL < B < CL < C < CR < A < AR

插入到CL 或CR

⭐ d. RL 情况（A的右孩子的左子树插入造成不平衡）

C(A的有孩子的左子树根)先右旋，再左旋；目的是让其代替A；

保证 AL < A < CL < C < CR < B < BR

插入到CL 或CR

⭐⭐ 调整不平衡的小总结
在这里插入图片描述

填个坑（四种冲突直观图）

在这里插入图片描述

练习RR、RL、LL、LR（注意单旋的时候从出现平衡因子有问题的孙子，具体是哪个孙子看四种模式）

⭐ ⭐ 注意 RR LL 找最小不平衡子树，将最小不平衡子树的根的失衡的孩子结点向上单旋。
⭐ ⭐ 注意 RL LR 找最小不平衡子树，将最小不平衡子树的根的失衡的孙子结点向上单旋两次到不平衡子树的根部。

做题步骤：

从插入结点，往上寻找，最小不平衡子树，也就是平衡因子不为 -1 0 1的三种情况；
分析 LL RR LR RL 四种情况，进行不平衡处理；

RR调整
RL 情况

在最小不平衡树(以平衡因子不为 -1 0 1 的结点为根的子树) 右孩子的左子树插入产生冲突；
在这里插入图片描述
所以先解决左子树-> 右旋；

右子树-> 左旋；

3. LR类型

在最小不平衡树(以平衡因子不为 -1 0 1 的结点为根的子树) 的左孩子的右子树插入造成的不平衡；
所以先解决右子树-> 左旋；再解决左子树 -> 右旋；

平衡二叉树的查找效率

注意一下平衡二叉树最少结点计算

在这里插入图片描述

平衡二叉树的平均查找长度 O(log 2 n)

在这里插入图片描述

平衡二叉树的删除

⭐ 第一个例子

删除同二叉排序树的三种情况
如果删除完，一路向上找不到不平衡子树，则删除成功；
如果出现不平衡，则应该用③解决：
根据孙子问题进行调整

-具体调整类似插入不平衡的四种情况；

在这里插入图片描述
a . 右旋后

b . 再左旋

在这里插入图片描述

调整完没有产生不平衡向上传导情况

⭐ 第二个例子(删除调整完不平衡后，不平衡出现向上传导)
删除结点
从删除结点向上找不平衡子树，找不到就结束了
找到不平衡子树，再画出个头最大的儿子、孙子；
通过解决冲突方法解决冲突
发现出现不平衡向上传导

循环执行第二步。

直到解决不平衡

🌙 二叉树删除的知识点回顾
在这里插入图片描述

平衡二叉树的知识回顾

在这里插入图片描述

3.3 红黑树（RBT）

二叉排序树、平衡树、红黑树的增删查的时间复杂度对比

在这里插入图片描述

为什么要发明红黑树？

插入和删除会破坏平衡，平衡二叉树进行调整，时间花销太大；
而红黑树插入和删除的不经常会破坏红黑特性，即便调整时间开销也是常数级；

在这里插入图片描述

红黑树的概念

红黑树是二叉排序树
与BST(二叉排序树) 相比的概念如下：

在这里插入图片描述
⭐ 黑高

某结点(不包含该结点) 到空叶子结点(包括该结点)的路径上所以黑结点的总数；

在这里插入图片描述

黑高为 h，则内部结点(不包括空结点) 的个数最少为（2 的 h次方 -1 ）也就是一颗全黑的满二叉树(全黑就不用塞红结点，满二叉树因为黑高相等)

在这里插入图片描述

红黑树的性质

在这里插入图片描述
性质二的证明

红黑树的查找

就是 x小于当前结点，向左找； x大于当前结点向右找；
与二叉排序树一样；

在这里插入图片描述

红黑树的插入

🌙 红黑树插入的规则和遇到冲突时的解决方式

几个问题：

为什么插入的是非根结点要定义为红结点？答：因为插入的是红结点不会破坏，平衡二叉树从某个结点到叶子的黑结点数相同的这个性质。

在这里插入图片描述
🌙 训练：
⭐ 注意插入是按 BST(二叉排序树)的方式插入

前三步

第一步插入是根，直接染成黑色即可；
第二步插入是非根，红色不冲突；
第三步插入时出现红红冲突了；观察新插入的 0005 结点的叔叔结点是黑叔，所以采用黑叔的处理方式(旋转加 + 染色)，旋转类似平衡树解决冲突的方式，本次是LL冲突，所以进行右单旋，父换爷；再将父和爷结点分别颜色取反染色；

⭐ 注意这里 LL 单旋解决冲突的时候，好似是插入结点的父结点去向上旋！！！（所以是父换爷嘛）
在这里插入图片描述
2. 第四步

插入新结点 0030 非根，又出现了红红冲突；

看叔叔脸色， 0005 是红色，用红叔解决方式：先叔、父、爷三个结点自身颜色取反，然后爷结点当成新加入的结点去匹配规则；本此插入，爷结点作为根结点，直接染黑；

在这里插入图片描述
3. 第五步

插入一个新的结点 0040 非根结点，发生了红红冲突。

看叔叔结点为红叔，且类型为 RR类型，所以解决方式 —— 左单旋(父换爷)。父、爷结点自身颜色取反。

⭐ 注意这里 RR 单旋解决冲突的时候，好似是插入结点的父结点去向上旋！！！（父换爷）
在这里插入图片描述
4. 第六步

插入新结点0057 非根(红) 发生红红冲突。

新结点的叔叔是红结点，采用红叔解决方式，叔、父、爷颜色自取反，然后将爷结点当成新加入的结点去匹配规则，本题换完，爷爷是红结点，并且在非根位置不产生冲突！

在这里插入图片描述
5. 中间重复过程跳过

当 0022 非根插入时，发生红红冲突：

看0022 叔叔的为红叔：所以叔、父、爷结点自身颜色取反，爷结点(0020)当成新结点匹配规则
将爷结点0020 看出新加入的结点，发现出现红红冲突：
0020结点的叔叔为红叔，所以0020结点的叔、父、爷自身颜色取反，再将0020结点的爷爷结点当成新的结点插入匹配规则；
1. 0020的爷爷结点是根所以，根染黑即可；

在这里插入图片描述
6. 插入 0023结点（黑叔 LR调整）

我们发现出现红红冲突， 0023结点的叔为黑叔，本次插入是 LR冲突

采用先左旋，再右旋 (儿换爷，即新结点左旋换父亲，再右旋换到爷爷位置)，再将儿(自己)和爷结点颜色取反；

左旋后

右旋后

自己和曾经的爷结点颜色取反

本次插入0018结点（RL调整）

本次插入后出现红红冲突， 0018的叔叔是黑叔，本次插入时 RL冲突

所以先右旋，再左旋，儿换爷(本结点右旋换父，再左旋换爷结点) ，再儿、爷结点染色(自身颜色取反)；

在这里插入图片描述
先右旋

再左旋

儿、爷结点染色(自身颜色取反)

红黑树的知识点框架

在这里插入图片描述

红黑树的删除操作

重点预测
在这里插入图片描述

四、 B树与 B+树的基本概念

4.1 B树 (多路平衡查找树)

五叉查找树

最少有1个关键字，分两个叉；
最多有4个关键字，分五个叉；
失败结点指的是在一个范围的数据;
进行查找时，块内的元素可以通过折半查找的方式；

在这里插入图片描述

如何保证查找效率

保持每个块内的关键字和分叉数量
保证平衡

这就是B树

对于m叉B树满足

每块内的关键字（【m/2】向上取整 -1），分支数（【m/2】向上取整）
保证树为绝对平衡，就是每个子树都相同高度。

在这里插入图片描述

B树的高度问题

在这里插入图片描述
👆 最小高度
👇 最大高度

推算方法一：
在这里插入图片描述
推算方法二：

小的知识回顾

在这里插入图片描述

B树的插入 .

1 . 初始插入

当插入到非终端结点，关键字满了后会分叉，将最中间的关键字提到上层。

新元素一定是插入到终端结点的

在这里插入图片描述
3. 失败结点只能出现在最下一层

4. 非根结点出现关键字满的情况，将中间关键字上提

※ 应当放到指向该结点的指针右侧位置

※ 如果上层结点的关键字也满了，继续向上提

⭐ B树插入小总结

B树的删除

⭐ 非终端结点删除的讨论

可以选择

直接后继(删除关键字右孩子的左子树最左下位置的结点的第一个关键字)
直接前驱(删除关键字左孩子的右子树最右下位置的结点的最后一个关键字)

在这里插入图片描述

⭐ 删除终端结点情况分析

删除后不低于关键字下线，直接删除
若删除后低于每个结点的关键字下限【m / 2】向上取整 -1；

左右兄弟结点的关键字够，则借用左右兄弟结点；借用右兄弟的就是父关键字下来到最后一个位置，右兄弟第一个关键字到父关键字位置；借左兄弟的就是父关键字下来称为第一个位置，左兄弟最后一个关键字到父关键字位置；
如果左右兄弟结点的关键字都不够借，采用合并算法；（将双亲结点的父关键字拿下来和两个兄弟关键字合并，如果双亲结点的关键字少了，再采用删除情况分析，如果借到根结点了关键字直接没了，则直接删除）