[TOC]
写在前面：这些内容是以考研的角度去学习和理解的，很多考试中需要用到的内容在实际应用中可能用不上，比如其中的计算问题，但是如果掌握这些东西会帮你更好的理解这些内容。
- 这篇关于查找的博客也只是用来记录以便于后续复习的，所以很多地方只是浅谈，并没有代码的实现
- 如果有缘发现这篇文章想要深入了解或者因为作者表达能力差而看不懂以及有错的地方，欢迎留言指出来，我会尽快去完善的，期待有缘人
- 内容多和杂，如果有机会我进一步进行梳理，将其重新梳理一片文章(会更注重于代码)
- 本来只是想简单写一下的，但是不小心就get不到重点了
- 本来打算等逐步完善和优化后再发出来的，但那样继续往前总感觉有所顾及，所以就先给这几天查找的复习暂时告一段落吧。
导学
(一)概念
- 查找：在数据集合中查找特定元素的过程
- 查找表(查找结构)：同一类型数据元素构成的集合
- 静态查找表:只涉及查找，不存在修改
- 适用：顺序查找，折半查找，散列查找等
- 动态查找表:动态插入和删除，对查找表进行修改
- 适用：二叉排序树，散列查找等
- 静态查找表:只涉及查找，不存在修改
所有数据结构都可以看作是查找表，对于折半查找和顺序查找这些都属于查找算法
- 关键字：数据元素中唯一标识该元素的某数据项的值
- 主关键字：此关键字能唯一表示一个数据元素
- 次关键字：此关键字用以识别若干记录(一对多)
说明：在查找表中每个数据元素就相当于一条记录，包含有不同的数据项，例如拿学生为例，一个学生作为数据元素，那么学号，身高，姓名就是这个元素中的数据项，每个学生都有特定的学号，因此学号可以作为关键字。(当然如果数据项包含身份证号，你用身份证号走位关键字也可以)
0x01平均查找长度(重点)
- 注意：作为查找算法效率衡量的主要指标，那么查找算法的性能分析肯定是重点分析平均查找长度的，因此必须熟练掌握。
提一嘴，算法效率的度量前面学过时间和空间复杂度，但是算法效率的度量不是只取决于时间和空间复杂度，针对不同的算法还可能会有其他一些辅助度量，如查找算法中的平均查找长度。(不过需要注意后面学排序算法时，其稳定性并不是用来衡量算法的优劣的，只是用来描述算法性质的)，下面开始说明平均查找长度
- 平均查找长度：所有查找过程中进行关键字比较次数的平均值
- 一次查找长度是指需要比较的关键字次数
- 成功平均查找长度：所有元素查找成功的情况
- 失败平均查找长度：所有元素查找失败的情况
- 数学公式定义：
没有特殊说明的情况下，默认每个数据元素的查找概率是相等的，记住就是每个元素查找时比较的次数乘以概率然后加起来
举个例子：
| 下标 | 0 | 1 | 2 |
|---|---|---|---|
| 查找集中的值 | 4 | 3 | 5 |
每个元素的查找概率是1/3,而查找成功时对应的比较次数依次是1，2，3，因此ASL=2（这是成功平均查找长度）
查找失败时对应的比较次数是4，4，4因此ASL=4
- 对于不同的概率计算方法是一样的
(成功)平均查找长度就是1/2*1 + 1/3 *2 + 1/6 * 3 = 5/3
(二)查找算法
- 算法的实现取决于数据结构的选取
- 数据结构三要素：逻辑结构，存储结构，数据的运算
- 下面的学习是以逻辑结构进行划分的
这里我有个疑惑，就是散列结构属不属于线性结构
线性结构：集合中数据元素之间只存在一对一的关系
非线性结构有更细的划分(集合—没关系，树形结构—一对多，图形结构—多对多)
那么散列结构中数据元素之间存不存在一对一的关系呢？
0x02线性结构
1.顺序查找(一般线性表)
- 思想：又称线性查找，从前往后或者从后往前依次对比进行查找
- 优点：对数据元素存储没有要求，顺序表、链表都可以
- 缺点：当n较大时，平均查找长度较大，效率低
- 重点注意：对于线性的链表，只能进行顺序查找
(1)实现代码
typedef struct { // 查找表的结构
Elemtype * elem; // 指针是采用动态分配，使用时分配
int TableLen; // 查找表长度
}Stable;
int Search_Seq(Stable S,Elemtype key) {
S.elem[0] = key; // 哨兵
for(i = S.TableLen;i != key;i--) {
return i;
}
}
- 代码不难，但是这里要介绍一个“哨兵”的概念，在这份代码中，S.elem[0]就是哨兵，引入“哨兵”可以避免许多不必要的判断语句，并且随着程序规模增大，效率提升也会越大
- “哨兵”需要额外分配一个空间，这里是将数组下标为0的位置留空作为”哨兵
- 注意：在查找时，元素若是查找失败是会和“哨兵”进行一次额外比较的，但是有些考题对于哨兵的这一次比较是不算在查找次数之内的，因此查找长度计算会有所不同，看学校
(2)平均查找长度
成功平均查找长度(这里与哨兵的比较是计算在内的)：
- 第i个数查找成功需要比较n-i+1次，如果是从前往后进行比较第i个数比较的次数就是i
- 每一个元素查找成功的概率是1/n，也就是说P为1/n
- 平均查找长度为
失败平均查找长度为：
(3)有序表的顺序查找
思想：略微特殊的线性表，其中的关键字是有序的，在查找失败时就不用继续往下查找了(比如升序序列，发现第4个元素大于查找的元素，那么后续的元素一定是都大于此元素的，就没有继续查找的必要了)，从而降低失败平均查找长度
成功平均查找长度和一般线性表一样
有序表的顺序查找和折半查找不一样，有序表的顺序查找一样适用于链表，而折半查找则无法用在链表的查询上
2.折半查找
- 又称二分查找
- 基本思想：以升序序列为例，将key值与表中间位置进行比较，相等则查找成功，若小于则在表的左边继续查找，大于则在右边继续查找，每次都是与中间位置进行对比
- 注意：只适用于有序的顺序表，同时折半查找需要方便的定位查找区域，所以要求线性表必须具有随机存取的特性，因此只适用于顺序存储结构，不适用于链式存储结构，同时要求元素按关键字有序排列
(1)代码实现
int BinarySearch(sqLList L, int data) {
int low = 0, high = L.length - 1, mid;
while (low <= high) {
mid = (low + high) / 2; // 取中间位置，向下取整
printf("%d\n", mid - 1);
if (L.data[mid - 1] == data) {
return mid;
}
else if (L.data[mid - 1] < data) {
low = mid + 1;
}
else
high = mid - 1;
}
}
(2)查找过程
- 设定一个mid值存储中间位置的值，这个中间位置mid的值为low和high的和除以2然后向下或者向上取整
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 7 | 10 | 13 | 16 | 19 | 29 |
查找29(这里采用向下取整)
第一次：low=0指向7，high=5指向29,此时mid=2指向13
13<29,此时范围缩小至[3,5]，(因为13已经比较过了，所以直接从下一个开始)
第二次：low=3指向16，high=5指向29,此时mid=(3+5)/2=4指向19
13<20,此时范围缩小至[5,5]
第三次：low=5指向29，high=5指向29,此时mid=5指向29
相等–>结束
- 解题注意：向上取整和向下取整生成的判定树是有区别的
- 向上取整：左子树节点数 >= 右子树节点数
- 向下取整：右子树节点数 >= 左子树节点数
- 也就是说：一颗判定树中要么左子树节点数全部大于等于右子树节点数，要么右子树节点数全部大于左子树节点数
(3)判定树(重点)
- 是折半查找过程生成的一棵二叉树，准确讲是用来折半查找过程的一种描述
- 判定树是一颗平衡二叉树同时也是一颗二叉排序树
注意：判定树描述的是折半查找过程中所有节点的查找过程，而折半查找中关键字比较序列指的是这个二叉排序树上的一条路径而已
看下面题目：
(4)判定树说明
例子：7 10 13 16 19 29 32 33 37 41 43
对应的判定树：
说明：
- 叶节点(方形节点)代表查找不成功的情况，但是注意：其方形节点是虚构的，它不计入比较的次数之中
计算ASL时，查找失败节点不适合放行节点，而是方形节点上层的圆形节点
- 有序序列有n个元素—>判定树有n个非叶节点和n+1个方形的叶节点
- 折半查找关键字的比较次数是和其关键字在判定树中的层数有关的，关键字在判定树的第i层，那么查找成功的比较次数就是i
(5)构建判定树(要会)
构建过程个人感觉就像告诉你先序遍历和中序遍历然后让你确定二叉树
不同的是这里每次需要的根节点不是通过先序遍历告诉你，而是通过low+high然后向下取整计算得到
扩展：什么样的情况下能确定一颗二叉树呢？
答案：知道先序遍历和中序遍历，或知道后序遍历和中序遍历，或知道层序遍历和中序遍历
(动图).ing—>尽快补上
(6)平均查找长度(重点)
平均查找长度公式：
- 失败查找长度也是根据此公式进行计算，不同的是在判定树上的高度和节点而已
- 而一般在计算时采用的公式是
此公式也是计算判定树树高的公式，关于这个，我的理解是：
使用第一个求和公式能够准确的计算平均查找长度，而这个一般计算公式求得的结果是比实际查找长度要大的，因为向上取整了，比如本来平均查找长度是5.00023，但是在题目中需要的是整数，因此向上取整就成了6,根据题目来
看个题目，这个题目虽然属于分块查找的，但是主要运算的是折半查找
(7)关于折半查找题目
很多就是给你一个长度已知的顺序表，然后让你求关键字比较次数或平均查找长度
解题最重要的思路就是构建判定树，不一定要全部画出来，但是给你一个元素个数要直到判定树的高度
这个题考的是判定树高度公式
选A,记住即可
- 求关键字比较次数的最值
思路：对于折半查找，关键字、节点数目什么的，第一反应就应该是构建判定树（不要真傻傻的画出来）关键字折半查找的比较次数是和判定树高度相关的的
求解：顺序表长度16，判定树高度是5，所以关键字最多的比较次数就等于树高5
- 求平均查找长度
思路：这种题目就需要画出判定树然后进行计算了，
取有序表元素为0 1 2 3 4 5 6 7 8 9 10 11
画出来是这个样子
查找成功平均查找长度(圆形节点)：判定树的每一层节点数*节点所在高度之和然后除以总个数
(1* 1 + 2 * 2 + 4 * 3 + 5 * 4)/12=37/12
查找失败平均查找长度(方型也就是叶子节点)：判定树的每一层节点数*(节点所在高度-1)之和然后除以叶子共个数
(3 * 3 + 10 * 4)/13 = 49/13
查找失败平均查找长度中与节点相乘的并不是节点所在高度，而是所在高度-1是因为方形节点在实际上是不存在的，当我们找到方形节点上一层的圆形节点时就已经知道是否查找失败了
- 判定树
思路：可能，前面知识点讲过，一棵折半查找判定树所有左子树要么全部大于等于右子树节点数，要么全部小于等于。因此选A
BCD中都同时存在左子树大于右子树节点数，右子树大于左子树节点数的子树
以D为例，根节点左子树有4个节点，右子树有5个节点，右子树大于左子树
而根节点的左子树那个节点的左子树有2个节点，右子树有1个节点，左子树大于右子树
因此不可能成为折半查找判定树
- 分块查找最值问题(分块问题不多，就与折半查找放到一起了)
思路：最好情况就是分块最理想，每个块中有根号n个元素，同时元素之间都是有序的，索引与块内都可以使用折半查找
求解：
- 折半查找中关键字比较序列
思路:这个题其实问的就是下面选项中那些关键字的序列不能构成二叉排序树的一条查找路径
3.分块查找
概念：又称索引顺序查找
特点：既有动态结构又便于快速查找，吸取了顺序查找和折半查找的优点
基本思想：将查找表分为若干子块，块内元素可以无序，但块之间必须是有序的(也就是说前一块中的最大关键字必须小于后一块中的最小关键字)，然后就是索引表，索引表中存放的是每个块之中最大的关键字和第一个元素的位置。索引表中的关键字是有序的
算法描述：先索引查找，然后在在块中查找。索引查找采用折半查找，块中查找则可以根据情况采用折半查找或者顺序查找
平均查找长度
- 分块查找平均长度一般求的是成功平均查找长度
- 由于块内查找和索引查找可以采用顺序查找或者折半查找，因此，平均查找长度计算有所不同，但整体思路是一样的，就是将折半查找和顺序查找的平均查找长度进行组合，公式：
注意：对n个记录的索引顺序表进行分块，最理想的块长是
$$
\sqrt{n}
$$
- 分块查找因为不同的查找组合会出现不同的平均查找长度，因此就有最理想，最好情况和最坏情况，看例题
0x03树形结构
1.二叉排序树(BST)
也称二叉查找树
是一种动态树表，特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的节点时进行插入。
性质：
- 左子树非空则左子树关键字值均不大于(不小于)右子树
- 右子树非空则右子树关键字值均不小于(不大于)左子树
- 左右子树又各是一颗二叉排序树
很多时候二叉排序树默认是左子树值小于右子树的值，但若有特殊说明则右子树小于左子树也是排序二叉树
如果对二叉排序树进行中序遍历就可以得到一个递增(递减)的有序序列
存储结构
typedef struct BTNode {
int data; // 节点存储的数据，这里代表关键字
struct BTNode *lchild;
struct BTNode *rchild;
}
(1)二叉排序树的查找
基本思想：(默认二叉排序树)并不复杂，从根节点开始进行比较，相等即返回，key值小于根节点关键字，进入左子树，反之进入右子树
递归算法
BTNode *BSTSearch(BTNode* bt,int key) {
if(bt == NULL) {
return NULL;
} else {
if(bt->data == key) {
return bt;
} else if(bt->data > key) {
return BSTSearch(bt->lchild,key);
} else {
return BSTSearch(bt->rchild,key);
}
}
}
- 非递归算法
BSTNode *BST_Search(BiNode T,ElemType key) {
while(T != NULL && T->data != key) {
if(T->data > key) {
T = T->lchild;
} else
T = T->rchild;
}
return T;
}
二叉排序树的查找并不难，难点和重点在于经过二叉排序树扩展过来的二叉平衡树等
(2)二叉排序树的插入
- 插入思路：
- 二叉树为空，直接插入节点
- 二叉树非空，则进行查找，插入的前提是查找，找到属于该节点的空位置，然后插入
- 二叉树插入的关键字一定是存储在新创建的叶子上、
int BSTInsert(BTNode *bt,int key) {
if(bt == NULL) { // 这里也是先找到空节点，然后进行插入
bt = (BTNode *)malloc(sizeof(BTNode)); // 因为非空所以先开辟空间
bt->lchild=bt->rchild=NULL;
bt->data = key;
return 1;
} else {
if(key == bt->data)
return 0; //关键字已存在树中，插入失败
else if(key < bt->data) {
return BSTInsert(bt->lchild,key);
} else
return BSTInsert(bt->rchild,key);
}
}
(3)二叉排序树的构造
- 二叉排序树的构造就是将关键字逐个插入到一颗空树中
void CreateBST(BSTNode *bt,int key[],int n) {
bt = NULL; // 一颗空树或者将树清空
for(int i = 0;i < n;i++) {
BSTInsert(bt,key[i]);
}
}
(4)二叉排序树的删除(略微复杂一点)
二叉排序树的节点删除要稍微复杂一点，因为需要 保证在删除节点后的树仍让是一颗二叉排序树
假设删除的是p节点，f节点为其双亲
p节点为叶子节点，可以直接删除，删除后不会破坏二叉排序树的特性
p节点只有右子树或者左子树，此时将p删除然后用p的子树代替p即可
若p节点既有右子树又有左子树，此时令p的直接后继(或直接前驱)替代p,然后将直接后继(或直接前驱)删除即可。重点在下面
什么？你说我怎么知道哪一个是直接后继或者直接前驱？
来，首先沿着p节点的右子树的根节点的左指针一直往左走，直到来到最左边的那个节点就是直接后继了，直接前驱就是沿着p节点的左子树的右指针一直往右走，直到来到最右边的那个节点就是直接前驱了，别看我放在这里，这是重点(敲黑板)
(5)平均查找长度
看到这个你想到了什么？ ———-对对对，就是那个，那个折半查找的判定树
需要说明的是二叉排序树和判定树还是有很大区别的，如果此时二叉排序树刚好是一棵二叉平衡树，那么此时平均查找长度和折半查找的判定树是一样的
关于不同：二分查找的判定树是唯一的，而二叉排序树是不唯一的，相同关键字因插入顺序可能生成不同的二叉排序树
要问为什么的话？
因为判定树是根据二分查找生成的，而二分查找的查找集是有序的，要么升序要么降序，然后从中间开始生成，因此生成顺序是唯一的，而对于一个相同元素的集合，二叉排序树的插入顺序可以是随意的，因此生成的二叉树也是不唯一的
当二叉排序树的平衡因子大于1时，平均查找长度就不一样了，极端情况下，二叉排序树的输入序列是有序的，此时是一颗倾斜的单枝树，平均查找长度就和顺序查找一样了，性能显著变坏(就像下图右边一样)
所以后面才出现了平衡二叉树，平衡二叉树里不会出现这种极端情况，因为其左右子树的高度差是被限制了的。(当人们发现二叉排序树越极端，效率越低时，就在想能不能通过控制二叉排序树的高度来保证二叉排序树的效率，因此平衡二叉树就出现了)
极端情况相关题目：
(6)二叉排序树相关题目
- 查找路径(序列)问题
- 插入删除相关题目
2.平衡二叉树
(1)知识点
已知平衡二叉树高度求最少节点==已知节点数求最大深度(高度)—>用平衡二叉树递推公式求解
以最少节点数构造平衡二叉树的递推公式：(这个公式在解题中很重要)—->
$$
N_h=N_{h-1}+N_{h-2}+1\ 如N_0=0，N_1=1;N_2=N_0+N_1+1=2 \其中N_2=2代表构造高度为2的平衡二叉树最少需要2个节点
$$
所有非叶节点的平衡因子均为1,即平衡二叉树满足平衡的最少节点的情况
答案解释在平衡二叉树相关题目模块中
(2)概念
好了，讲完了二叉排序树，接下来开始平衡二叉树(AVL树)，还记得平均查找长度的英文缩写吗？不记得就上去看(哼~)
又称AVL树，(也可简称为平衡树)，是一种特殊的二叉排序树，因此它具有二叉排序树的性质，同时其左右子树都是平衡二叉树
二叉平衡树是排序二叉树的改进
定义;所有树的左右子树高度之差不超过1，也就是平衡因子不大于1(只能为-1，0，1)
平衡因子：左子树和右子树的高度之差
下图中每个节点中的数据就是该树(以该节点为根)的平衡因子
(3)平衡二叉树的插入
这个就比较复杂了，复杂的地方在于如果因为插入节点导致树不再平衡就需要进行调整
那么，如何保证平衡呢？
基本思路：当删除或插入导致平衡树的平衡被打破，首先找到插入路径上离插入节点最近的平衡因子大于1的节点p，再对以p节点为根的树进行调整，使之重新达到平衡。调整规律分为(LL,RR,LR,RL)四种情况：
下面的调整描述是王道书上的，如果不好理解建议看一下天勤的描述，较之王道要更通俗一点，这里就不贴出来了
LL平衡旋转(右单旋转)
由于在结点A的左孩子(L)的左子树(L)上插入了新结点，导致
A平衡因子由1增至2，以A为根的子树失去平衡，因此需要一次向右旋转操作。具体操作过程是将A的左孩子B向右上旋转代替A成为根结点,将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。
RR平衡旋转（左单旋转)
由于在结点A的右孩子(R）的右子树(R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。
具体操作过程是：将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树，如图5.29所示。
LR平衡旋转（先左后右双旋转)
由于在A的左孩子(L)的右子树(R)上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。
具体操作过程：先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置，如图5.30所示。
RL平衡旋转（先右后左双旋转)
由于在A的右孩子(R)的左子树(L)上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。
具体操作过程：先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置，如图5.31所示。
在RL和LR平衡旋转中，新节点究竟是插入第二次子树后的左子树还是右子树不影响旋转过程。
这里说一下，平衡二叉树的构建和二叉排序树一样就是不断的将节点插入一棵空树，通过调整不断维持其平衡。
调整方式的命名：LL，RR，LR，RL并不是对调整过程的描述，而是对不平状态的描述，比如LL是在左子树(L)的左子树(L)上插入节点导致不平衡(调整就是向着反方向调整，因此是右单旋转，向右)，LR是指在其左子树(L)的右子树(R)上插入节点导致不平衡，调整因此是先向左后向右进行两次旋转，RR和RL同理。
(4)平均查找长度
- 和折半查找生成的判定树的平均查找长度是相同的
(5)平衡二叉树相关题目
- 给定节点求深度最值
思路：已知节点求最大深度—>递推公式
$$
N_{0}=0 \qquad N_1=1 \qquad N_2=N_0+N_1+1=2
\N_3=N_2+N_1=4 \qquad N_4=N_3+N_2+1=7
\N_5=N_4+N_3+1=12 \qquad N_6=N_5+N_4+1=20
$$
从递推公式可以看到20是大于13小于21,因此最大深度为6
- 给定高度求节点最值
思路：已知高度求最少节点
根据上面的公式：5层需要至少12个节点
- 节点总数问题
思路：重点是非叶子节点的平衡因子均为1代表此时平衡二叉树拥有最少的节点，题目就变成了已知高度求最少节点
根据上面的公式：6层知道需要20个节点
- 二叉树的构建问题
思路：此题考查的是平衡二叉树的构建，本质是考平衡二叉树插入时的平衡调整
- 综合选项
树中最大元素一定无左子树，但可能有右子树，不一定是叶子节点
- 对插入的理解
答案：A
注意最后一种平衡调整(这里是LR平衡旋转)，先以1为根节点进行左旋，然后以3为节点进行右旋
3.B树
B树(B-树)，是一种多路平衡查找树，也是由二叉树变换而来的
记住：B树不支持顺序查找(B+树是支持的)
B树中所有结点孩子节点个数最大的值称为B树的阶，通常用m表示
一棵m阶B树或空树性质：
- 每个节点最多有m棵子树，至多含有m-1个关键字
若根节点不是终端节点，则至少有两棵子树
- 除根节点之外所有非叶节点的子树至少有
除根节点之外所有非叶节点的关键字至少有
所有非叶节点结如下：
说明，K代表的是节点的关键字，且K1<K2<…Kn;P代表的是指向子树根节点的指针，注意P(i-1)指向的子树中的关键字都是小于Ki
所有叶节点都出现在同一层次上，并且不带信息(实际上这些节点并不存在，指向这些的节点指针为空)，这些也是查找失败到达的位置
虽然实际上并不存在，逻辑上是被当作存在的，因此说叶子节点的时候指的就是这一层节点
B树属于平衡m叉查找树，其左右子树的高度差不会超过1
B树的关键字树比子树数目要小一，就好像一个正方形，关键字是正方形中的内容，而指向子树的指针就是正方形下面的两个端点
如果已经规定或者知道了树是m阶B树，那么即使画出来的树的结构图中节点中没有m-1数目的关键字，其在空间分配中也还是占据了m-1个关键字应该占据的空间。
放在前面(理解)
B树的插入和删除操作后需要进行分裂和合并的目的是使得被修改节点的关键字数目n满足
(1)B树的查找
- B树的查找是二叉排序树的扩展，二叉排序树是二路查找，B树是多路
- 两个基本操作：查找节点和在节点中查找关键字
- 前一个操作时在磁盘上进行的，后一个操作是在内存中进行的(在找到目标节点后将节点信息读入内存，然后采用顺序查找或折半查找)
- 基本思路：(此处以升序为例)
- 先从根节点开始，相等即结束，关键字A比key大，就顺着关键字A前面的指针进入子树中，关键字A比key小就进入关键字A后面的指针进入子树中，重复上述过程，直到查找成功或者查找到叶节点时就查找失败(对应指针为空指针)。
(2)B树的插入
和所有树的构建一样B树的构建也是在一棵空树上不断插入关键字
B树比二叉排序树要稍微复杂一点
二叉排序树在找到终端节点后插入即可，而B树则需要做额外的处理以使得插入节点后的树满足B树的定义
过程：
1–>定位,首先利用上述的查找算法找出最底层的某个非叶节点(注意插入是插入至叶节点)，如果树中已存在该关键字就无法进行插入，不存在的话会找到查找失败的叶节点，则个时候指向查找失败叶节点的上层节点就是我们需要的非叶节点。
2–>插入，插入的时候就需要注意情况了，因为在插入一个关键字后可能该节点的关键字数量会超过每个节点允许的最大关键字数目，因此就需要进行调整。所以，两种情况
第一种就是插入一个关键字后节点的关键字数量不大于B树允许的每个节点的最大关键字数量m，直接插入即可(即找到的节点关键字数目小于m-1)
第二种就是进行插入后节点的关键字数大于m-1,这个时候就需要进行分裂
具体过程：
从中间位置[m/2(向上取整)]将节点关键字分为三部分，分别是中间位置的左边，中间位置的那个数，中间位置的右边，然后将中间位置那个关键字添加到父节点中去，如果此时父节点关键字溢出则将父节点进行分裂。
(3)B树的删除
B树的删除重点就是要掌握在删除最底层非叶节点时的不同情况下的合并操作
B树的删除要稍微复杂一点，分为几种处理情况
- 关键字k位于最底层非叶节点中时，用k的直接前驱(或直接后继)k2替代k,然后删除k2即可
删除最底层非叶节点就是不断的替换然后转换成删除最最曾非叶节点
直接前驱看删除关键字前一个指针下指向的节点的最大的关键字，后继看关键字后一个指针指向的节点的最小的关键字
- 重点：关键字k位于最底层非叶节点，有三种情况
(4)解题知识点
根节点为非终端节点时，最少的字节点数和关键书分别为2和1
已知B树中的关键字求最大高度和最小高度
公式推导不难，不用公式做题也不难，但这样就慢了
这种思想就是求最小高度，就是每棵树都有最大的孩子m
最大高度就是根节点有两个孩子节点，其他非叶节点都有m/2向上取整孩子节点数
具有n个关键字的B树有n+1个叶子节点
B树的叶节点对应的查找失败的情况，对n个关键字的查找集合进行查找，失败可能性有n+1种
理解的话：给你一批有序的数字，然后让你查找k，找不到无非就是三种情况，1落在了那一批数字中间的间隔之中(比如在5、7中找6，失败的原因就是6落在了5和7中间) 2所有数都大于k 3所有数都小于k
(5)B树相关问题
- 关于的B树和B+树，选择题一般考察的就是对B树概念的理解以及节点或者关键字的最值问题
其实关于树最多的计算问题就是知道树的深度求最多或者最少的节点数，知道节点数求树的最大深度或者最小深度
知识点中有，答案n+1
思路：给定高度求节点的最值，考的就是对于B树的特性，哪些节点至少和至多拥有的子树数目和关键字的数目
8—>至少：根节点含有两个子节点，其他非叶节点都含有3/2向上取整为2个节点，所以是一颗完全二叉树，个数为2的5次方-1=31
至多：所有非叶节点都含有3个子节点，1+3+9+27+81=121(此处是等比数列)，一般求至多需要用到等比求和公式
9—>至少：此处不再是节点而是关键字，但也是含有最少节点数，本质是一样的
至少：根节点含有2个子节点，其他非叶节点含有的子节点数为5/2向上取整-1为2，但此处高度只有2，都不需要考虑那么多
直接算，第一层一个节点，第二层2个节点，2*2+1=5，注意：根节点的关键字数可以为1
4.B+树
B+树是应数据库所需而生的一种B树的变形树
性质：
相同性质
每个分支节点最多有m棵子树(孩子节点)
非根叶节点至少有两棵子树
除根节点之外所有非叶节点的子树至少有
$$
\lceil{m/2}\rceil
$$
不同性质：
- 节点的子树个数和关键字个数相同
- 所有叶节点包含全部关键字及指向其相应记录的指针，叶节点中关键字按有序排列
- 所有非叶节点仅起到一个索引的作用，即节点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址，而在B-树中，每个关键字对应一个记录的存储地址。
通常在B+书中有两个头指针，一个指向根节点，另一个指向关键字最小的叶节点
B+树的应用方面从这个题的解析中就能了解
0x04散列结构
这一节主要还是将书上的内容内容放上来了，后面还是重点介绍一下题目
1.散列表
- 记录在表中的位置和关键字之间存在着确定的关系
敲黑板：对于考研这一部分要求记住一句话—根据给定的关键字计算出关键字在表中的位置
(1)概念介绍
- 散列表:根据关键字进行直接访问的数据结构
散列表建立了关键字和存储地址之间的一种映射关系
散列函数：把查找表中关键字映射成该关键字对应地址的函数，(这里的地址可以是数组下标、索引或内存地址等)记为
$$
Hash(key)=Addr
$$冲突：散列函数将两个或两个以上的不同关键字映射到同一地址上
同义词：发生碰撞(冲突)的不同关键字之间称为同义词
(2)散列表的建立
- 散列表的建立分为两部分，首先是通过散列函数将关键字插入表中，然后如果产生冲突就进行冲突处理，然后将数据插入其中
下面实际中常用的散列函数：
- 一个好的散列函数应该尽可能的避免产生冲突，但是任何散列函数都会产生冲突，我们所能做的就是尽量降低产生冲突的可能性。
处理冲突的方法：
- 取定某一增量序列后，对应的处理方法就是确定的，一般有下面四种取法：
在采用开放定址的情形下，删除元素只能进行逻辑删除，就是在想要删除的元素位置做一个删除标记,不能进行物理删除。
因为若进行物理删除元素就会截断其他具有相同散列地址元素的查找地址。这样做的副作用就是进行多次删除之后，表面上看散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，将删除标记的元素进行物理删除。
另一种冲突处理方法：
(3)散列表的查找
- 散列表的查找与构造基本一致
- 首先根据散列函数查找关键字对应地址是否有记录，若无记录则查找失败，有记录则进行比较，若相等就返回查找成功标志，失败则执行接下来的步骤
- 用给定的冲突处理方法计算“下一个散列地址”
- 散列表的查找效率取决于三个因素：散列函数，冲突处理的方法和装填因子
- 散列表的平均查找长度依赖于散列表的装填因子，而不依赖于散列表的长度m和表中记录数n
(4)平均查找长度
平均查找长度会因为散列函数和冲突处理的不同而不同
下面的例子：散列函数–H(key)=key%13 冲突处理–线性探测
散列表
查找成功关键字比较次数：
计算方法：首先14%13=1(地址),而1地址存放的刚好就是14，因此比较次数为1
01%13=1(地址),1地址存放的是14，发生冲突因此采用线性探测(从2位置从前往后查找)继续查找，发现第二个位置是01，因此比较次数为2
看27%13=1(地址)，1地址存放的非27，开始使用冲突处理继续查找，依次往后找，发现在第四个位置，从前往后依次比较过1，2，3，4，比较次数为4
依次类推
- 至于查找失败平均查找长度：在后续题目中会进行讲解(emmmm，主要是不晓得咋个说)
- 散列查找的平均查找长度的计算有些细节东西是需要注意的，不然很容易出错，具体看最后的题目
(5)其他
散列表的装填因子(定义为一个表的装满程度)：
- 装填因子越大，发生冲突的可能性越大。
(6)散列表相关题目
这里答案是D，但我还是觉得是(K-1)K/2,因为第一个是没有发生冲突的，也就是说进行线性探测的只有K-1个数
这种题就是比较简单的了，依次将关键字带入散列函数然后看结果为1的个数即可，有4个
会借着这个题目详细记录一下散列查找的平均查找长度的计算
首先拿到题目先将散列表画出来，先将所有关键字带入散列函数中得到
关键字 87 40 30 6 11 22 98 20 散列计算 3 5 2 6 4 1 0 6 计算过后发现只有6和20发生了冲突，因为6计算在前，因此对20进行冲突处理得到最终的散列地址
散列地址 0 1 2 3 4 5 6 7 8 关键字 98 22 30 87 11 40 6 20 NULL 每个关键字的查找失败长度就是从该关键字的散列地址出发依次往后对比(数),直到找到为空结束
以关键字98为例，依次往后找，空的散列地址是8，那么一共比较了9次（0~8）
其他依次类推，散列地址从0
8的关键字对应比较的是 (93次) 然后将所有关键字的查找失败的查找长度相加除以m即可，这里的m是7并不是表长8最后结果就是:(9+8+7+6+5+4+3)/7=6
需要注意的是：你只能将从0-6地址的关键字的比较次数加起来然后除以7，第7个地址的关键字没有算进来的
这里很容易出错，很多人都以为是除以表长，其实不然，因为你的散列函数中模长是小于表长的，对于超过模长的关键字比如散列地址为7的关键字散列函数是找不到的
- 总结一下：平均查找长度的计算是如果模长小于表长，是只算到模长的
- 说一下线性探测再散列就是线性探测法
因为王道书上的开放定址法有四种，其中第三个的名字叫再散列法，搞得我以为线性探测再散列法是先线性探测再进行再散列法
然后发现数据结构教材上开放定址法只写了三个，分别是线性探测再散列，二次探测再散列，伪随机探测再散列，是没有的再散列法的，不过有个再哈希法，这个再哈希法和王道书上的再散列法是不一样的，()这个哈希法采用的是另一种哈希函数)而且不属于开放定址法
一些无关的话题
个人认为最好的学习状态是以实际应用或考试为驱动的学习
算法最核心的就是思想，其次就是数据结构，不同的数据结构搭配上算法组成各种各样的程序
$$
\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j1
$$