数据结构与算法之高级搜索树（连载中~）

继续邓俊辉老师的数据结构和算法课程，这篇博客记录的是高级搜索树的相关内容，视频资源如下：https://www.bilibili.com/video/av25421628

如果是没有接触过二叉树或者二叉搜索树的话，可以先看看邓俊辉老师第五章和第七章的内容，第七章的内容我做了一些笔记，相关博客链接：
https://blog.****.net/hongpei9627/article/details/81840397

接下来进入正题，这章的内容很多，我计划先将整章的内容写在一起再考虑分P~

第八章 高级搜索树

伸展树（splaytree），局部性：

自适应调整，将某些经常被访问到的元素移动到接近树根的位置，相当于降低它们的深度：

逐层伸展，使用zag和zig旋转：

一步一步往上爬的最坏情况：

伸展树的双层伸展：

子孙异侧的情况，这种情况下和AVL树双旋还有伸展树逐层伸展没有区别：

到了子孙同侧的情况下，就有了改善，即双层伸展：

上述情况的点睛之笔：

根据双层伸展后的效果：

可以看出，树高减少了一半~

折叠效果：

伸展树相关算法的实现：
（有待补充~）

B树

B树的多路平衡：

为何要引入B树呢：

深度统一，在下图中，external nodes为叶节点中数值为空的并不存在的孩子节点：

紧凑表示：

B树的代码定义和实现（BTNode）：

使用了向量的方式表示~

B树的代码接口：

B树的查找函数过程与实现，若查找失败必终止于外部节点：

B树最大高度h，要推算最大高度，即每个超级节点里关键码的数量要足够少，但是不能小于m/2，其中m为B树的阶次：

B树的最小高度：

从B树的最大高度和最小高度推算可以分析出，B树的高度变化幅度有限~

B树的插入算法实现：

当插入后出现上溢（overflow），需要进行分裂处理：

分裂后若仍然上溢，便进行再分裂：

第46集为B树插入后分裂，再分裂，分裂到根的实例演示，可以看看~

B树删除：

删除节点后会出现下溢情况~

若出现下溢情况，可以考虑使用旋转的方式，如下图右子树出现下溢情况，而其左兄弟中的关键码数量满足不小于m/2取上限，则可以补充右子树中得关键码数量，但实现这方式条件比较苛刻~可能其左兄弟不存在或者根本无法借出关键码~

采取合并的方式~

第50集是B树删除操作的实例演示，有旋转与合并操作~

B树设计成比较矮且宽的结构，是因为让外存操作的代价和内存操作的代价大致相等~在水平方向是内存操作，而在垂直方向做磁盘操作，每下降一层都要付出一次I/O代价

红黑树
终于到了揭开红黑树的面纱了~

红黑树特性：持久性

为了让任何一次的动态操作引发的结构变化量不至于超过O(1)，引入了红黑树~

红黑树的结构，红黑树是一种BBST：

提升变换，变换前：

变换后，红色节点提升到和其父亲节点同样的高度：

红黑树为（2，4）B树：

红黑树接口定义：

红黑树的插入算法之双红缺陷：

双红缺陷根据插入节点的uncle节点（即其祖父节点的另一个孩子节点）的颜色，分两种情况分析，下图为若uncle节点为黑，考虑zagzag和zigzag情况：


以上的调整是一蹴而就的，不用进行进一步的调整~

若uncle节点为红，则：

出现了上溢的情况，因此先以修复上溢问题的方法做处理~

在理解下图的过程中，老师在此前也讲过将红黑树看作B树去对待，转化完成后再看成红黑树，在理解上更加简明~

双红修正复杂度的分析：

红黑树的删除算法，关注重构操作的次数（reconstruction），其不会超过常数：

双黑缺陷：

分四种情况处理~情况一：

为何会有这种操作呢，接下来反观这情况：

情况二，三：

情况四：

红黑树删除总结：