数据结构与算法 8. 高级搜索树 2021-07-26 浏览量 536 暂无评论 [TOC] ## 8.1 伸展树:逐层伸展 ### 宽松平衡 更潇洒 ### 局部性 刚被访问过的数据,极有可能很快地再次被访问。 对于AVL数,连续m次访问的时间复杂度:$O(mlogn)$ ### 自适应调整 拿列表来说,每次访问完一个元素,就把它移到前端,方便下次访问。 ### 逐层伸展 通过zig和zag等价变化,将节点逐步移到树根。 一步一步往上爬:自下而上,逐层单旋。 ### 最坏情况 退化为单链,每一周期$\omiga (n^2)$ ## 8.2 伸展树:双层伸展 旋转两次 子孙异侧时与逐层伸展等效 子孙同侧时,有改进的地方,也就是先旋转祖父,而不是父亲。这样微小的变化在全局上有不同的结构,每次访问完最深点,树的高度都被优化为一半。 分摊复杂度:$log(n)$ ![在这里插入图片描述](https://img-blog.csdnimg.cn/a05ea2298c324747ac5a5fa31ef36776.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 8.4 伸展树:算法实现 ### 功能接口 ```cpp template class Splay : public BST { protected: BinNodePosi(T) splay(BinNodePosi(T) v); public: BinNodePosi(T) & search(const T & e); // 查找也会引起拓扑变化,动态 BinNodePosi(T) insert(const T & e); bool remove(const T & e); }; ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/cac8624a4920439c9a6f47ebcca20d29.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 查找算法 ```cpp template BinNodePosi(T) & Splay::search(const T & e) { BinNodePosi(T) p = searchIn(_root, e, _hot = NULL); _root = splay(p ? p : _hot); return _root; } ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/71f4eff30c68461383190cd6a390366a.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/2e5c8ec60ba44d6ab7099904202a1128.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/9168b2d0554e4e868e4a255ec0b47c0c.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/2af05a5820a0422b9912562071818be8.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 综合评价 优于AVL树 分摊复杂度$O(log(n))$--与AVL树相当 局部性强、缓存命中率极高时(即k << n << m) 效率甚至可以更高--自适应的$O(logk)$ ## 8.5 B树:动机 严格意义上,B树并不是二分查找树,因为节点可能包含多个分支,从逻辑意义上,仍等效于二分查找树。 弥合不同存储级别之间在访问速度上的巨大差异,即实现高效IO。 **640KB。** 物理上,存储器的容量与速度成反比。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/56f77422c0c64bf39805fa60d4de971a.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/66dde712631845738d62b9dd8ef2cb64.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 8.6 B树:结构 B树又宽又低。 平衡的多路搜索树。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/f19f53253de845549d610edb9dab0547.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 多级存储系统中使用B-树,可针对外部查找,大大减少I/O次数。 怎么说?批量访问,超级节点的规模视磁盘的数据块大小而定。 **有个重要的参数:阶数** ![在这里插入图片描述](https://img-blog.csdnimg.cn/738bee2bc57c4ab08d777efa46965042.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 在这里,外节点是叶节点的空子树。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/526c392fb31244a09fe70692b74e9d96.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 最大关键码的个数其实就是d代中节点的最大总数,2代3个,3代7个 最大分支数就是下一代的最大节点数,2代的下一代4个,3代8个,最小分支数就是最大分支数的一半,也就是保证上一代的每个节点至少有一个分支? (2, 4)树与红黑树渊源不小。 ### 结构定义 ![在这里插入图片描述](https://img-blog.csdnimg.cn/a62cd40a493b48f886407aee6560c27d.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/7bfa2c2424c14fa592a47371b2eea2fc.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 8.7 B树:查找 只将需要的节点载入内存。 在每一节点进行顺序查找(因为是中序的),成功则返回,失败则通过停留位置的引用前往下一层(进行一次I/O)。 ### 实现 ```cpp template BTNodePosi(T) BTree::search(const T & e) { BTNodePosi(T) = _root; _hot = NULL; while (v) { Rank r = v->key.search(e); if (0 <= r && e == v->key[r]) return v; _hot = v; v = v->child[r + 1]; } return NULL; } ``` **为了与I/O匹配,每个节点的规模大概xxKB,实验表明,在此规模的有序向量下,顺序查找效率要高于二分查找。** ### 最大树高 ![在这里插入图片描述](https://img-blog.csdnimg.cn/e3fca4b81cb349db9dafa0bd6e746866.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 最小树高 ![在这里插入图片描述](https://img-blog.csdnimg.cn/df1807f25de042c6b914e217c9ef2c06.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) B树高度变化有限,最高和最低接近。 ## 8.8 B树:插入 ```cpp template bool BTree::insert(const T & e) { BTNodePosi(T) v = search(e); if (v) return false; Rank r = _hot->key.search(e); _hot->key.insert(r + 1, e); _hot->child.insert(r + 2, NULL); _size++; solveOverflow(_hot); return true; } ``` 如发生上溢,需分裂。 发生上溢的情况:超过m个分支,即插入后有m + 1个分支,m个关键码 分裂步骤: - 设上溢节点中的关键码依次为$k_0, k_1, k_2, ..., k_{m-1}$ - 取中位数$s = \lfloor m/2 \rfloor$,以关键码$k_s$为界划分为$k_0, ..., k_{s-1}$,$k_s$,$k_{s+1}, ..., k_{m-1}$ - 关键码$k_s$上升一层,并分裂,以所得的两个节点作为左右孩子(为什么可以有左右呢?上升一层是指将该关键码插入到上一层超级节点还是单独作为一个节点,如果是插入到上一层的超级节点,那不是只多了一个分支吗?哦,没错,因为本身该关键码所在的超级节点也是一个分支,只要把分裂出的右半部分作为新孩子接入即可。) 时间复杂度:$O(h)$ ## 8.9 B树:删除 ![在这里插入图片描述](https://img-blog.csdnimg.cn/6e2478996e23403796f92f81cf28d5b7.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 发生下溢的情况:恰好包含$\lceil m/2 \rceil-2$个关键码 + $\lceil m/2 \rceil-1$个分支 当前节点左顾右盼,朝兄弟借一个关键码(但实际实施时是向父亲借,父亲再管儿子要),兄弟的关键码要不小于$\lceil m/2 \rceil$。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/979e38ad8ac446c4947c6fe9db65ca6a.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 如果左顾右盼不行的话$\lceil m/2 \rceil -1$,就要采用优先级低的合并。 将父亲的关键码拿下来,和两兄弟合并。 ## 8.10 红黑树:动机 先前的数据结构在经动态操作后,其之前的状态都转瞬即逝,没有记忆。 当然可以通过保存历史版本来记忆,但在时间和空间上均不如人意。 利用前后版本间的关联性。 如果想将前后版本之间的拓扑差异不超过$O(1)$,那么每次动态调整时,旋转操作不能超过常数次,AVL树的插入操作是满足的。 有没有一种树结构,任何动态操作都控制在$O(1)$。 有,红黑树! ## 8.11 红黑树:结构 ### 定义规则 由红黑两类节点组成的BST(统一增设外部节点NULL,使之成为真二叉树) - 树根:必为黑色 - 外部节点:均为黑色 - 其余节点:若为红,则只能有黑孩子 // 红之子、之父必黑 - 外部节点到根:途中黑节点数目相等 提升变化:将所有红节点提升至与其父亲齐平 红黑树经提升变换后即变为4阶B树,将黑节点与其红孩子视作超级节点。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/cf6bf3ec8e244b03a8afe31b0c7d5898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/ef412b3a79f14bfba7f6d25fd1e80a88.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 8.12 红黑树:插入 插入节点x时,将x染红(除非它是根节点),红黑树的规则124满足,但3未必满足,如果插入节点的父亲为红色,会出现“双红缺陷”,如何解决呢? ![在这里插入图片描述](https://img-blog.csdnimg.cn/80345f1af8254f5d81956107e58a1044.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 双红修正1:插入节点的叔父为黑 "3+4"重构后调整节点颜色 ![在这里插入图片描述](https://img-blog.csdnimg.cn/1d751f5f2015476e8f0d12038b016873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/5680e4d923b74f3a8c83c6195eb37109.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 双红修正2:插入节点的叔父为红 ![在这里插入图片描述](https://img-blog.csdnimg.cn/717a807cc6a04f22a5148b69fe35dcdb.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 8.13 红黑树:删除 时间复杂度不会超过$logn$ 但拓扑结构变化只有常数次,重染色可能进行多次。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/8fcdea33f1194d169f85b6e3949b7923.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 赞赏 微信支付 支付宝支付