四种存储方式：顺序、链式、索引、散列

本章的线性表可以采用链式、顺序存储，其中二叉查找必须使用顺序的有序表

分块查找是索引存储与线性表（顺序、链式）的结合体

二叉排序树、二叉平衡树、红黑树基于链表实现，B树、B+树基于链表实现

散列表基于散列存储实现，也就是这一整章把所有的存储方式都给覆盖了，是查找结构

随机存取的存储结构：顺序表；散列存储的存储结构：散列表

顺序存取的存储结构：链表；索引存储的存储结构：索引表

顺序查找（链式或者顺序表均可）：

如果真的要分类其实可以分为带哨兵、不带哨兵、从前向后、从后向前、链表分类等

但个人觉得没必要了，直接从最本质的计算出发

失败的ASL在无序情况下是必然需要遍历全部元素的，而有序情况则可以好一些

成功时的ASL，不论有序还是无序都是一样的，每个位置对应需要查找的次数累加即可

具体按照题目给定的分类临场计算即可，这类一般不难

相对而言比较重要的也就是有序表的顺序查找的失败ASL计算了

折半查找（只能顺序表且元素必须有序）

统考命题重点：给定折半查找的数量和取整方式则可以唯一确定一棵折半的判定树

具体画法可以参考纸上面列的，向上取整和向下取整是有各自生长规律的

其他就是折半查找的手工模拟其实可以很简单，纸上面有列具体方法

一般只需要画出判定树，那么ASL的计算也就不在话下

分块索引（索引表+链表/顺序表）

索引表必然是顺序存储的，可以支持二分查找、顺序查找，这是ASLI

在表内进行查找一般采用顺序查找（因为表内往往无序，有序则可以用二分查找

这是ASLII

整体ASL的计算是需要列出方程计算的，不过方程一般不难，这个需要注意下

习题分析补充：

仍然是一句话，注意审题

2：顺序查找在有序表、无序表内查找成功的ASL是一样的，只有失败的时候不一样

这一点是极易错的点，要重视

3：默认查找第一个时的查找次数为一次，查找长度也是一，是包含在内的

注意审题，题设一定要划清楚：求的是成功还是失败的ASL

9、10、11：有更为简便的方法，或者说实际上是能够一眼看出来的，不必模拟运行

纸上已经给出了具体的例子，以后就没必要模拟，直接一眼就可以看出来结果

12：一般情况下建议记住结论，考场里面则更加注重以“举例”的方法解题

一时半会没有思路就不要再想下去，直接举例子能暴力解掉就一定要直接解掉的

这个是考场里面必要的技能

17：最理想表长是建立在顺序查找上面的，如果是二叉和顺序或者全二叉需要会列方程

18：依旧是审题，审题做题的时候一定要划清楚关键，再做题

19：审题，题设已经给出了整体序列是有序的，最好情况就是两次查找都是二分法

7、13、14、20、23、24：判定树的绘制，是统考的考察重点

当给定了结点数量和取整方法，则就唯一确定了一棵二分查找的判定树

其中向上取整则每层优先长左子树，向下取整则每层优先长右子树，随着结点增长来说

当且仅当判定树为完全二叉树的时候向上取整和向下取整的判定树是相同的

二叉排序树、平衡二叉树、红黑树：

二叉排序树的插入没有任何特色，只有删除略微分三种情况（叶或用中序前驱后继替代

平衡二叉树的插入略微有些特色但也就四种情况，只在子树调整不会回溯

删除与插入相对应，但可能会向上回溯

红黑树的插入略微有意思，前两种情况都不会回溯，第三种情况可能会产生回溯

习题补充：

6：注意这样一些细节，需要区分二叉排序树和二叉平衡树，实际做题中往往会混淆

本道题就是因为没有区分清楚，导致用平衡树算了半天没算出来结果

二叉排序树并不一定是平衡树，但二叉平衡时、红黑树基本都基于二叉排序树

做题的时候必须要划清楚考的到底是二叉平衡树还是二叉排序树，极易搞混

9：题目表述并不是特别好，但清楚二叉排序树、平衡二叉树、红黑树中序都是有序的

然后中序又可以和先序、后序、层序结合起来，分别对应入栈、出栈基本就可以了

11、12：本质原因是书上有一块内容没有看导致的，即是平衡二叉树的构建那一小块

本身是一个递归构建的树，所以一旦清楚了规律就会很容易画和计算

13：不多说了，排列组合里面少算了一个满二叉树的情况

14：旋转，平衡二叉树的插入和删除、红黑树的插入（两种情况）和删除都算是旋转的

二叉排序树的删除不能算是旋转，只能算是补树

其中需要注意，旋转的话需要清楚各自的名词含义是哪种旋转类型，容易对不上号

16：红黑树的查询效率是低于平衡二叉和二叉排序的（二叉排序平均也是logn

但插入和删除等动态操作优于以上两者

对于IV这种，考场上就要学会举例来证明，这种一般都只需要举反例就可以

17：回溯的情况：红黑树的插入第三种情况、平衡二叉树的删除情况（回溯条件是什么

18：最普遍的举例题

19：红黑树的定义题里面需要注意这样一些细节：

首先根必须是黑的，从每个结点向下面的叶子结点出发其黑结点一定是数量一样的

红黑树一定满足是一棵二叉排序树的特征、红结点不相互连接

20、21红黑树的插入画图，其实最重要的就是第三种情况可能需要回溯会比较麻烦一些

26：可以猜测题意说的就是最少结点的平衡二叉树情况

31：审题，基本是被曾经的统考题目骗过去了，以为是以前的题目再现

到底是考察平衡二叉，还是二叉排序，一定要看清楚，这是非常容易错的地方

综合题：

2：又是被二叉排序骗过去了，画了个平衡二叉出来

4：最佳的二叉排序树是折半查找的判断树，即高度最小的平衡二叉树，需要注意

B树：

根结点分为两种情况，一种非叶，一种叶情况，两种书上写的并不是特别明确

叶子情况根结点最少可以是零个关键词零个子树，这时候也称B树为空树（虽然不太妙

非叶子情况根结点最少可以一个关键词，两个子树，最多则是M-1个关键词，M子树

至于其他节点，都是按下限、上限来定最少和最多的

叶子结点，书上对叶子结点的定义实际上是基于最底部一层的Null结点，不是终端节点

所以书上说的非叶结点实际上就是在说B树里面所有的结点，这一块算是个漏洞

B树计算相关

计算结点最多、结点最少情况用累加即可，计算关键词最多最少用最后一层反推

毕竟一个比较核心的特征就是N个关键词有N+1个失败可能性

计算高度直接套关键词与高度公式就行，若是给定结点那么也照样用累加公式逆推即可

公式还是得记住的，多抄几遍就够了

注：截止目前没考过B树的ASL计算，因为别的考ASL就行

B树一个磁盘块一般就是对应一个结点（结点内包含：关键词、指针、信息存储地址

先进行一次I/O读入磁盘块，然后读入内存进行访存操作（顺序查找或者二叉查找

B树一个结点内关键词是有序排序的，所以读入内存后支持二叉查找

读到关键词，则直接访问对应的存储地址，没读到继续向下的指针走下去直到叶结点

所以B树查找的话成功肯定在半路上，查找失败一定在叶子上（NULL结点上

所以查找成功和该节点的深度有关，查找失败和树整体的深度有关，ASL也易于计算

后面有一道结合操作系统的题目，建议多加思索，这种交叉学科的内容很容易考

B树的插入比较简单，先查找到叶结点去插入，然后根据具体的情况决定分裂与否就行

分裂可能会向上回溯，总体比较简单，没有太多可以说的，练几下就懂了

B树的删除补充网站，基本包含了所有情况，书上列举的其实很不够详细，容易漏错

其实也主要就是在说合并这件事，书上不够详细，这里面的是完整包含所有情况的

(https://blog.csdn.net/qq_43290883/article/details/126437596)

B+树

（一般只考相关概念）

根结点依旧是两种情况，一种是叶，一种是非叶，叶对应最少是零，非叶最少是两个

这里关键词和子树数量是一样的，其他也顺便有所改变

B+树更加适合于文件系统、数据库的索引，其本质就是为这些服务的

其结点内的原子内容只有这些：关键词、指针；B树则有：关键词、指针、存储地址

因而一个同样的磁盘存储块，B+树能够存储更多的关键词索引，磁盘I/O代价更低

两个指针，分别对应可以顺序查找和随机查找

需要注意区别：随机存取、随机查找，这个是两码事，顺序查找和顺序存储也是两回事

B树支持随机查找或者说多路查找但不支持顺序查找

B+则顺序、随机查找均支持，因为最后叶节点有一个指针指向

B+查找失败、成功均在最终的叶节点，B则失败在叶，成功在中间半路结点

B树习题补充：

做题前说一句，这一轮的目标是全对，中间错了就要好好反思问题，追根溯源

该划的关键词都不要少，一道道题当作考试做下去

第一题作为一种潜在的考法需要注意，B树的形态很难推测出其是几阶的

4：一个潜在考点：插入前有多少个，插入后有多少个（需要引起重视，不要忽视考点

10：随机查找不是随机存取，B树和B+树均是以链表作为其存储结构，树为逻辑结构

不过反正只有B+能够支持顺序查找

11：最简单的方法就是直接套公式即可，都不用算，就是根结点已经读入内存…

17：答案写的是很好的，结合了多学科知识，还是比较建议多看几遍，总结很精辟

18：关键词最多、最少和相应高度的求法要么是套公式，要么是反求解

这道题是反向求解，这样会明显更快一些

20：注意，根结点不可能出现三个关键词，所以不会有四个子树，一开始还疑惑了半天

本质还是对于下限比较熟悉，对上限的观察太少的缘故，仍然是两边都需要注意的

22：其表达略微不太好，“最终”这个词实际上描述并不够准确

综合：

其中的B树插入、删除是重点，一定要把握，后续复习的重点也一定从综合题开始

如果综合题的插入、删除都还会画，那么自然没有问题

另注：B树一般也会称B-树，B+树就是B+树，不存在B+树属于B树的情况

判断散列函数：定义域、值域是否覆盖，是否稳定可实现查询

其他都是“好”的散列函数的目标

散列函数目前后两者未考察过，但熟悉相应的应用场景即可，网上搜索

前面两者的核心是取余位置需要清楚是一个素数，以及对应的适用场景也要清楚

处理冲突的方法里面，开放定址是顺序存储，拉链法必然是链式+顺序存储

开放定址法的取余是表长，平方探测法其实还有一个比较容易忽略的要求就是表长要求

以及对应的是先正后负，这个容易记错

开放定址法的比较位置可能是没有内容的（逻辑上删除）

习题补充：

依旧是提醒一句：注意审题，要当作考试一样去做的

逻辑结构、存储结构，永远没有搞清楚的一个地方

3：装填因子本身就是一个特有的属性，本身表示装满的程度，和N或者M没有直接关系

关于开放定址法中的探测位置，探测位置上面到底是同义词还是非同义词是不确定的

因为这个位置既可以是原来就被该关键词对应的所占用，也可以是探测后的同义词占用

自然也就不存在同关键词相邻一回事，他们的位置都是随机的

5：更何况因为取余的原因，同义词可能一个在首一个在末，这样怎么可能相邻？

13：散列存储的数组元素位置是从零开始的，因为是取余的原因

散列过程：

先由散列函数计算出对应的关键词位置，然后再尝试放入，放入失败则采用冲突函数

散列函数取余是一个素数，而冲突函数取余是表长！是完全不一样的概念，值域不相同

处理冲突采用冲突函数计算下一个位置，直到能够放进去为止

散列查找过程与上面是一样的，第一次没找到则用冲突函数去查找，直到查找到的是空

所以采用开放定址法的是不能随意删除一个数组内内容的，否则就会导致查找为空

后面的也就全部丢失

15：查找过程，比较关键词的一些叙述

比较成功的路上一路比较的都是关键词，所以比较一个关键词就算一次或者一个长度

比较失败则目前还有争议，但以统考为标准则是空也要比较一次

对应拉链法就是有内容的结点比较一次，后面的空指针也比较一次（容易漏

对应开放定址法则是有内容的比较一次，没有内容的也去比较一次失败的

20：查找成功的ASL与失败的ASL计算相关问题

查找成功计算的内容是：每个已存储的关键词所对应的查找次数累加/总关键词数量

无非就是要注意不要算错，查找到一个关键词也算一个查找长度

然后开放定址法删除的位置也是不截断需要计入在内的、移动的位数需要算清楚吧

拉链法也删除就是直接删除不需要保留就行

查找失败的计算内容是：散列函数值域内每个查找到空的查找次数累加/值域数

查找到空，意味着至少是查找到一个空的而不是一个删除的被标记的位置

开放定址法找到空位置为止，比较空算一次，拉链法找到空指针为止，空指针算一次

对应的习题有：20、21、23、综合3、4、5、6（算是一个比较重要的重点，需要重点算