没有合适的资源?快使用搜索试试~ 我知道了~
首页探索高级搜索树:伸展树、B-树与红黑树详解
探索高级搜索树:伸展树、B-树与红黑树详解
需积分: 0 0 下载量 22 浏览量
更新于2024-06-30
收藏 3.97MB PDF 举报
第8章-高级搜索树2深入探讨了数据结构中的多种高级二叉搜索树,旨在提升数据访问效率和适应不同场景。首先,我们重点关注伸展树(Splay Tree),这是一种基于局部性原则设计的数据结构,它采用“最常用者优先”策略,虽然在最坏情况下单次操作可能达到O(n),但在实际操作中,其平均性能仍然保持在O(logn)范围内。伸展树的特点在于其简洁的实现和广泛的适用性,无需严格的平衡约束,但在长期使用中能保持高效的性能。 接着,平衡多路搜索树(如B-树)被引入,尤其以4阶B-树为例,这种结构能够有效地平衡不同存储层次间的访问速度差距。B-树的平衡性和高效性使其在存储系统中扮演重要角色。红黑树在此部分也得到了讨论,它是另一种平衡二叉搜索树,通过常数次数的结构调整来维持平衡,提高了操作效率,同时也为实现高级数据结构如持久性结构提供了便利。 最后,kd-树被介绍用于平面范围查询,它是基于子区域正交划分的四叉树和八叉树的扩展,特别适用于计算几何问题。kd-树以其基本的模式和有效性,成为解决这类问题的标准工具。 总结来说,本章通过伸展树、B-树和红黑树等高级搜索树,展示了如何利用不同的平衡策略和数据组织方式,优化数据访问性能,适应不同应用场景的需求。这些数据结构不仅在理论上有深度,也在实际应用中有广泛的价值。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/86328352/bg8.jpg)
§8.1 伸展树 第8章 高级搜索树
210
查找算法的实现
在伸展树中查找任一关键码e的过程,可实现如代码8.3所示。
1 template <typename T> BinNodePosi(T) & Splay<T>::search ( const T& e ) { //在伸展树中查找e
2 BinNodePosi(T) p = searchIn ( _root, e, _hot = NULL );
3 _root = splay ( ( p ? p : _hot ) ); //将最后一个被讵问癿节点伸展至根
4 return _root;
5 } //不其它BST丌同,无讳查找成功不否,_root都指向最后被讵问癿节点
代码8.3 伸展树节点癿查找
首先,调用二叉搜索树的通用算法searchIn()(代码7.3)尝试查找具有关键码e的节点。
无论查找是否成功,都继而调用splay()算法,将查找终止位置处的节点伸展到树根。
插入算法的实现
为将节点插至伸展树中,固然可以调用二叉搜索树的标准插入算法BST::insert()(188页
代码7.5),再通过双层伸展,将新插入的节点提升至树根。
然而,以上接口Splay::search()已集成了splay()伸展功能,故查找返回后,树根节点
要么等于查找目标(查找成功),要么就是_hot,而且恰为拟插入节点的直接前驱或直接后继
(查找失败)。因此,不妨改用如下方法实现Splay::insert()接口。
图8.8 伸展树癿节点揑入
如图8.8所示,为将关键码e插至伸展树T中,首先调用伸展树查找接口Splay::search(e),
查找该关键码(图(a))。于是,其中最后被访问的节点t,将通过伸展被提升为树根,其左、
右子树分别记作T
L
和T
R
(图(b))。
接下来,根据e与t的大小关系(不妨排除二者相等的情况),以t为界将T分裂为两棵子树。
比如,不失一般性地设e大于t。于是,可切断t与其右孩子之间的联系(图(c)),再将以e为关
键码的新节点v作为树根,并以t作为其左孩子,以T
R
作为其右子树(图(d))。
v小于t的情况与此完全对称,请读者独立做出分析。
上述算法过程,可具体实现如代码8.4所示。
1 template <typename T> BinNodePosi(T) Splay<T>::insert ( const T& e ) { //将兲键码e揑入伸展树中
2 if ( !_root ) { _size++; return _root = new BinNode<T> ( e ); } //处理原树为空癿退化情冴
3 if ( e == search ( e )->data ) return _root; //确讣目标节点丌存在
4 _size++; BinNodePosi(T) t = _root; //创建新节点。以下调整<=7个指针以完成尿部重极
![](https://csdnimg.cn/release/download_crawler_static/86328352/bg9.jpg)
第8章 高级搜索树 §8.1 伸展树
211
5 if ( _root->data < e ) { //揑入新根,以t和t->rc为左、右孩子
6 t->parent = _root = new BinNode<T> ( e, NULL, t, t->rc ); //2 + 3个
7 if ( HasRChild ( *t ) ) { t->rc->parent = _root; t->rc = NULL; } //<= 2个
8 } else { //揑入新根,以t->lc和t为左、右孩子
9 t->parent = _root = new BinNode<T> ( e, NULL, t->lc, t ); //2 + 3个
10 if ( HasLChild ( *t ) ) { t->lc->parent = _root; t->lc = NULL; } //<= 2个
11 }
12 updateHeightAbove ( t ); //更新t及其祖先(实际上叧有_root一个)癿高度
13 return _root; //新节点必然置亍树根,迒回乀
14 } //无讳e是否存在亍原树中,迒回时总有_root->data == e
代码8.4 伸展树节点癿揑入
尽管伸展树并不需要记录和维护节点高度,为与其它平衡二叉搜索树的实现保持统一,这里
还是对节点的高度做了及时的更新。出于效率的考虑,实际应用中可视情况,省略这类更新。
删除算法的实现
为从伸展树中删除节点,固然也可以调用二叉搜索树标准的节点删除算法BST::remove()
(190页代码7.6),再通过双层伸展,将该节点此前的父节点提升至树根。
然而同样地,在实施删除操作之前,通常都需要调用Splay::search()定位目标节点,而
该接口已经集成了splay()伸展功能,从而使得在成功返回后,树根节点恰好就是待删除节点。
因此,亦不妨改用如下策略,以实现Splay::remove()接口。
图8.9 伸展树癿节点初除
如图8.9所示,为从伸展树T中删除关键码为e的节点,首先亦调用接口Splay::search(e),
查找该关键码,且不妨设命中节点为v(图(a))。于是,v将随即通过伸展被提升为树根,其左、
右子树分别记作T
L
和T
R
(图(b))。接下来,将v摘除(图(c))。然后,在T
R
中再次查找关键码e。
尽管这一查找注定失败,却可以将T
R
中的最小节点m,伸展提升为该子树的根。
得益于二叉搜索树的顺序性,此时节点m的左子树必然为空;同时,T
L
中所有节点都应小于m
(图(d))。于是,只需将T
L
作为左子树与m相互联接,即 可得到一棵完整的二叉搜索树(图(e))。
如此不仅删除了v,而且既然新树根m在原树中是v的直接后继,故数据局部性也得到了利用。
剩余41页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/1df4be369e0c40ac84f65317982f6f63_weixin_35801828.jpg!1)
白羊的羊
- 粉丝: 39
- 资源: 280
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 贵州煤矿矿井水分类与处理策略:悬浮物、酸性与非酸性
- 醛固酮增多症肾上腺静脉采样对比:ACTH后LR-CAV的最优评估
- 开源云连接传感器监控平台:农业土壤湿度远程监测
- 母婴用品企业年度生产计划线性规划优化模型:实证与应用
- 井下智能变电站:Rogowski线圈电流检测系统的研发与性能验证
- 霍州矿区煤巷稳定性分析及支护策略
- ARM嵌入式系统远程软件更新方案:基于TFTP协议
- 煤炭选煤中汞分布规律与洗选脱汞效果
- 提升码垛机器人性能:拉格朗日动力学模型与滑模模糊控制的应用
- 增强现实技术提升学前手写教学:设计与开发案例
- 不规则工作面沉陷三角剖分算法提升与应用
- 卡尔曼滤波在瞬变电磁干扰压制中的应用研究
- 煤矿安全能力研究:理论与系统构建
- LonWorks总线技术在斜巷运输车辆定位与跑车防护中的应用
- 神东煤炭集团高效煤粉锅炉系统:节能环保新实践
- Ti/SnO2+Sb2Ox/PbO2电极分形维数与电催化性能研究
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)