1.基本概念
只有查找称之为静态-比如成绩单
但又增删改称之为动态-外卖订单
平均查找长度概念ASL(计算的重点)
分为查找成功和查找失败两种情况
顺序查找
依次查找
哨兵位
ASL分析
当查找最后一个元素时，查找的次数是1，而概率是1/n
对于查找倒数第二个元素，查找的次数是2，而概率是1/n
所以将每个位置的计算进行累加即可得到查找成功的asl
而对于失败的情况则查找n+1个元素，因为还有一个哨兵位置
有序表的查找优化和ASL计算
整体有序时，可以通过判断查找元素和目前元素的大小对比判断是否成功
其中可以将这些元素分成如下的区间
共有n+1个区间，而落在这n+1种区间的概率都一样
而最后两个区间时，对比的次数肯定是n次，跟所有的元素都进行了对比，所以他的次数会是两个n
还有一种是当每个元素被查概率不等时需要考虑的
查找判定树
左小右大
折半查找
只能是顺序表
查找判定树性质和ASL分析
### 基本原则：一次比较就是一次“决策”
在二叉搜索树中，每访问一个**节点（绿色圆圈）**，我们都会拿要查找的数和这个节点里的数进行一次比较。这次比较会产生三种结果之一：
1. **等于 (`=`)**：找到了！查找成功，过程结束。
2. **小于 (`<`)**：目标在左边，移动到左子树继续查找。
3. **大于 (`>`)**：目标在右边，移动到右子树继续查找。**核心法则：查找一个元素（无论成功或失败）的比较次数，就等于从根节点开始，到查找结束时所经过的节点（绿色圆圈）总数。**
---
### 1. 成功查找的比较次数
我们以查找 `41` 为例，它的查找次数是 3 次。为什么？
* **目标：41**
1. **第1次比较**：从根节点 `29` 开始。`41 > 29`，所以向右走。
2. **第2次比较**：来到节点 `37`。`41 > 37`，所以继续向右走。
3. **第3次比较**：来到节点 `41`。`41 = 41`，找到了！我们一共访问了 `29`, `37`, `41` 这三个节点，所以比较了 **3次**。
这正好是节点 `41` 所在的**层数**（或深度，当根节点为第1层时）。你可以用同样的方法验证：
* 查找 `29`：只访问节点 `29`，比较1次。
* 查找 `10`：访问路径是 `29 -> 13 -> 7 -> 10`，访问了4个节点，所以比较4次。---
### 2. 失败查找的比较次数 (重点)
失败查找的逻辑稍微复杂一点，但遵循同样的原则。当查找路径走到了一个“尽头”（一个本该有节点但实际没有的地方），查找就失败了。
我们以你圈出的 `(7, 10)` 这个失败区间为例。为什么落入这个区间的查找需要 **4次** 比较？
* **目标：8** (因为 8 在 7 和 10 之间)
1. **第1次比较**：从根节点 `29` 开始。`8 < 29`，向左走。
2. **第2次比较**：来到节点 `13`。`8 < 13`，继续向左走。
3. **第3次比较**：来到节点 `7`。`8 > 7`，向右走。
4. **第4次比较**：来到节点 `10`。`8 < 10`，我们试图向 `10` 的**左边**走。此时，我们发现节点 `10` 没有左孩子。查找路径中断，宣告**失败**。
我们一共访问了 `29, 13, 7, 10` 这四个节点，所以比较了 **4次**。
#### 现在我们来解释 `ASL_失败` 公式中的 `(3*4 + 4*8)`
**`4*8` 这一项：**
* **第一个 `4`**：代表需要 **4次比较**才能确定失败。
* **第二个 `8`**：代表有 **8个** 失败区间是需要4次比较的。为什么是这8个？因为它们的“父节点”（也就是查找失败前访问的最后一个绿色节点）都在**第4层**。第4层的节点是 `10, 19, 33, 43`。
每个这样的节点都对应两个失败的“岔路口”：
* 从节点 `10` 失败：`(<10)` 或 `(>10)`，对应区间 `(7, 10)` 和 `(10, 13)`。
* 从节点 `19` 失败：对应区间 `(16, 19)` 和 `(19, 29)`。
* 从节点 `33` 失败：对应区间 `(32, 33)` 和 `(33, 37)`。
* 从节点 `43` 失败：对应区间 `(41, 43)` 和 `(43, +∞)`。总计 `2 + 2 + 2 + 2 = 8` 个区间。要到达这些失败区间，都必须先经过4个节点，因此比较次数都是4。
**`3*4` 这一项：**
* **第一个 `3`**：代表需要 **3次比较**才能确定失败。
* **第二个 `4`**：代表有 **4个** 失败区间是需要3次比较的。为什么是这4个？因为它们的“父节点”都在**第3层**。第3层的节点是 `7, 16, 32, 41`。
但是，这些节点还有一个孩子是**内部节点**（绿色圆圈），所以它们只对应一个失败的“岔路口”：
* 从节点 `7` 失败：`(<7)`，对应区间 `(-∞, 7)`。（它的右孩子是内部节点10）
* 从节点 `16` 失败：`(<16)`，对应区间 `(13, 16)`。（它的右孩子是内部节点19）
* 从节点 `32` 失败：`(<32)`，对应区间 `(29, 32)`。（它的右孩子是内部节点33）
* 从节点 `41` 失败：`(<41)`，对应区间 `(37, 41)`。（它的右孩子是内部节点43）总计 `1 + 1 + 1 + 1 = 4` 个区间。要到达这些失败区间，都必须先经过3个节点，因此比较次数都是3。
### 总结
| 查找类型 | 比较次数的计算方法 | 示例 |
| :--- | :--- | :--- |
| **成功** | 从根节点到**目标节点**的路径上，经过的**节点总数**。 | 查找 `13`，路径 `29 -> 13`，经过2个节点，比较2次。 |
| **失败** | 从根节点到**查找路径中断处**的路径上，经过的**节点总数**。 | 查找 `8`，路径 `29 -> 13 -> 7 -> 10`，在 `10` 处失败，经过4个节点，比较4次。 |希望这个详细的步骤能帮你彻底搞清楚比较次数的计算方式！
在编程语言中，int型变量向下取整，当结果位偶数个时，比如0-3，那么min就会等于1，取到序列中第二个元素，所以mid的左边只有一个，右边有两个
即右子树-左子树节点必定=0或者1
判定树的高度计算
根据右子树只可能比左子树多1或者0个元素推导
向上取整
结点之间的关系
符合二叉排序树的定义
查找效率分析
对比次数肯定不会超过h次
分块查找
关键字递增排序
其中low指的是区间的下界，high指的是区间的上界
查找方式
假定我们查找23这个元素
我们现在索引表中进行比较，比较23>10,23>20
然后我们发现23<30所以22可能存在于30这个块里面
在这个块进行顺序搜索
三次比较都没有成功，当指针指向9时，我们发现指针超出了30这个块的上界，判定为查找失败
折半查找索引表
因为块间整体有序，所以我们可以采用折半查找现在索引中进行搜查
我们以19举例，查找次序如下
我们可以发现，折半查找失败但是并不意味着分块失败了
如果在索引表中折半失败了，那么我们就会进入low指针所指的位置进行查找
为什么？
这样分析，当折半查找失败前的最后一步时，一定有high=low=mid
那么假设我们要查找的元素是>mid元素的，那么根据折半查找，low=mid+1
而又根据分块查找性质，mid所指向的块的最大元素<target
所以只有可能是出现在low这个指针的指向中
若taget<index[mid]
则hight=mid-1
则此时low指针没变，指向mid指针所指，而target<index[mid]
所以target有可能出现在mid指针所指的块中
所以我们固定在low所指向的分块进行查找
若块内元素个数均匀分布
asl分析如下
其中注意s=根号n时，ASLmin=根号n+1
若动态查找表，即能够即时的插入和查找元素的表采用链式存储更方便，如下图所示
反正块间都是顺序查找，链式和顺序不影响快慢
二叉排序树
空间复杂度讨论
二叉排序树的插入
二叉排序树的删除
1.叶节点删除
2.非叶节点删除
3.具有左右子树的结点删除
选择其中序遍历序列中删除节点右子树的第一个结点，即该结点后面的第一个结点替代删除节点
因为该节点一定是右子树中最小的，根据二叉排序树的特性，右子树中没有比他小的，左子树中没有比他大的，所以能够作为根节点
同理推导过程也可以用于删除右下结点
查找效率分析和查找树的最好最坏情况的高度
失败情况
平衡二叉树（删除节点后如何保持树的平衡，考试重点）
只要二叉排序树保持平衡其查找效率就可以达到log2n的数量级
插入结点后如何保持平衡
1.先找到第一个不平衡子树
2.调整最小子树
LL平衡
RR平衡
总之就是要遵循
AL<A<BL<B<BR
这种排序特性
即当B成为根节点，并且其左指针指向A后，其原本的左指针指向的树BL子树要大于A又要小于B
所以挂载到A结点的右子树最合适
左右旋代码思路
LR平衡
把最小非平衡树的左孩子的右孩子
先左旋转C再右旋转C即可构造平衡树
RL平衡
把最不平衡树的右孩子的左孩子进行右旋左旋操作
查找效率分析
递推公式（考试重点）
nh=nh-1+nh-2+1
所以可以推出来n3=n2+n1+1=4一直往下递推
平衡二叉树的删除
具体过程
不平衡向上传导的实例
发现不平衡后重复2的过程
红黑树
红黑树的叶子结点都是如图所示的结点，即空结点和外部结点
红黑树特性4
查找路径中不会出现连续的父子都是红色结点
红黑树特性5
图中有写
特性总结
性质1：因为红黑树最短路径的情况是路径上全黑，最长路径的情况是，每一个黑结点中间都夹杂着红色结点，因为红节点不能连续出现在父子上，且又因为到达每一个叶节点的黑色节点数量都相同，所以推导出该性质
红黑树的操作
1.查找，同二叉树
2.插入
举例子
旋转操作同平衡二叉树
原本的谁被换走了就染色谁，看图中父换爷就染父和爷
黑叔情况
红叔情况
若经历几轮旋转和染色，根节点被涂成了红色，则直接涂黑即可
考点（重点）
为什么结点最少的情况是全部都是满二的黑节点？
因为要符合“黑路同”的特性，即到达任意一个叶子节点的黑节点数量相同，若非满树，则肯定存在某一叶子节点的长度与其他的不符合
3.删除
性质
如下图所示情况就是最少节点实现最长长度的红黑树，所以性质二的证明是这样证明的
B树
m叉查找树
m叉查找树也需要对平衡问题进行优化
定义
同时满足以上两种性质的m叉查找树也叫做m阶B树
B树的平衡是绝对平衡的
结点的结构
性质（考点）
B树的高度
因为一层最多有m-1个关键字
每个结点最多m个分叉
而m个分叉又会每个结点有m个分叉诞生m*m个结点
以此类推得到以下式子
其中m-1是每个结点的关键字个数
1+m+......m的n次方是每一层结点的个数
最终可算出结论
总结和考点
B树的操作
插入
当一个结点超出结点上限时以[m/2]向上取整为基准分为两个部分
插入一定是插入到最底层的终端结点当中
因为若插入的不是终端结点，会在上面出现一个非同一层的失败节点，不满足b树的特性
若出现子结点溢出，则将子节点拆分
即将原本的88放入到父节点中，然后用右指针指向原本在他右边的角色
(83)是后面加入的
若存在某一个结点因为溢出需要放入父节点中，那么他放入的位置应该是其当前所在节点被父节点所指向的指针的右边的那个位置，可以保证b树的特性
父节点溢出的分裂
总结
删除
若删除的结点元素删除后导致原本结点为空，那么采用寻找直接前驱和直接后继来顶替
即左子树的最右元素，因为这里的元素一定是大于所有左子树元素小于所有右子树元素
以及右子树的最左结点，同理可得原因
删除终端结点元素导致结点个数不足[m/2]
处理方法
右兄弟够借
左兄弟够借
兄弟不够借时
将元素做出如下合并
但我们发现合并后原本的父节点也不满足要求了，并且其父节点的兄弟也不够借
所以我们再次重复操作进行合并，根节点为空时直接删除即可
B+树
类似于分块查找，每个结点中包含其子节点的最大值
其中“记录”的意思是：每一个叶子节点都是一个关键字
以学生举例，每一个叶子节点都是学号，每一个学好下面对应的记录都是一个数据项，每一个数据项都对应着一个学生的信息。
叶子结点都有对应的指针指向，所以可以沿着指针遍历把所有的叶子结点遍历完毕
查找
也可以顺序查找
总结和类比
散列表（哈希表）
基本概念
冲突处理
散列函数的构造
因为中间的数字会被所有数字影响，更具有平均性
拉链法
插入
默认是头插法
查找
计算散列地址然后遍历链表
其中查找次数代表着比较数字多少次，默认空指针不算次数，除非特殊说明
删除
同链表删除同样的操作
优化
开放定址法
线性探测法
平方探测法
双散列法
主要是构造第二个散列函数
伪随机序列法
删除操作
如果进行物理删除，那么当我们删除3这个位置的元素的时候，如果还想再删除1这个元素，那么从1开始按照散列函数的规则进行遍历，那么当遍历到3为空的时候直接退出，而没有删除掉1这个元素，从而导致错误，所以我们采用逻辑删除
探测覆盖率
散列查找性能分析（ASL计算，考试重点）
ASL计算是通过比较次数×概率得到，二比较次数和构造散列表时便宜的次数是一样样的，直接如图所示数数即可
查找成功
查找失败
其中13这个概率的的来是因为根据散列函数的构造，我们发现，散列函数的构造中，关键字只有可能落在0-12这个区间的所有的位置，而落在任何一个位置都是等可能的所以概率为1/13
而假设查找的关键字是0那么只需要对比一次就知道为空，停止查找
但若查找的关键字定位到1这个位置，那么会一直向下查找直到为空位置，查找次数如计算算式所示
存在逻辑删除时
成功时关键字的个数要减去逻辑删除的个数
失败时同以前一样
装填因子
堆积现象
优化堆积现象
总结
错题
采用递归dp分析即可，一直往下拆分小问题
我的答案：A
正确答案：B
因为折半查找树一定是一个平衡二叉树，而二叉排序树不一定是平衡的，可能出现图中的情况导致时间复杂度上升到n的数量级
这类题目主要在于构造出他的折半查找树
折半查找树的一个重要性质就是高度为h则前h-1层一定是满二叉树
已知长度为16即有16个元素，而高度为4的满二叉树元素只有15个，所以该树高度为5并且只有一个第五层元素
而查找一个不存在的元素，即图中蓝色框框所示的地方就是失败的结点，前面的节点数就是比较次数
答案选择：A
二分树的性质，左-右=1 | 0
或者 右-左=1|0
而一棵树只能具备上述的一种性质
所以对于D选项的错误排查来说，最大的左右两个子树不符合其子树的子树的性质
答案选择：D
实际上等同于问五个结点打的二叉树有多少种形状，到时候在任意填写数字就行了
运用卡特兰数
以及递归和DP的思想
答案选择：C
存在Nh=Nh-2+Nh-1+1这样的斐波那契数列
如图所示即可看出推导过程找出深度为n的平衡二叉树的最少节点数量
同样可通过递归计算得到
比如高度为4的平衡树我们发现
其左子树是高度为2的最小二叉平衡树，右子树为高度为3的最小平衡二叉树
答案选择5
同样也可以通过递归dp进行查找，将一个大规模问题分解为小规模问题
重点题目：
答案选择：D
因为红黑树的性质，黑红交替出现是红节点最多的情况，那么如果算上外部节点，那么黑色一定多，如果不算上，那也会出现红色大于黑色的情况，比如一个根节点链接两个红节点
