C++(数据结构与算法):49---平衡搜索树总体概述
发布日期:2021-06-29 22:33:22
浏览次数:2
分类:技术文章
本文共 866 字,大约阅读时间需要 2 分钟。
一、平衡树概述
- 接下来几篇文章将会介绍平衡树结构:
- 树的高度为O()
- 其中有两种平衡二叉树结构:AVL和红黑树。它们适合内部存储的引用
- 一个树结构:B-树,它的度大于2。其适合外部存储的引用(例如,存储在磁盘上的大型字典)
- 上面这些平衡树结构可以在最坏情况下用时O(logn)实现字典操作和按名次的操作。当用索引平衡树表示线性表时,操作get、insert、erase的用时为O(logn)
- 分裂树:高度为O(n),而且在分裂树上的单个字典操作用时为O(n),但是每一个含有u个操作票的序列,其用时仅为O(ulogu)
二、各种字典结构的渐近时间新能比较
- 下面用到的函数都是Θ的
三、总结
- STL的map和multimap使用的是红黑树结构,以保证查找、插入、删除操作都具有对数级的时间性能
- 关于实际的运行时间性能,AVL和红黑树是相似的;相比之下,分裂树在实施一个含有u个操作的序列时,用时比较少。另外,分裂树的实现方法比较简单
- AVL和红黑树都是用“旋转”来保持平衡:
- AVL树对每个插入操作最多需要一次旋转,对每个删除操作最多需要O(logn)次旋转
- 红黑树对每次插入和删除操作,都只需要一次旋转
- 这种差别在大多数应用中无关紧要,因为一次旋转仅需用时Θ(1)。但是对那些需要平衡的应用,一次旋转不能在常量时间内完成,这种差别就非常重要了。例如,平衡优先搜索树(McCreight)就是这样一种应用。平衡优先搜索树用于描述具有二维关键字的元素,此时,每个关键字是一数对(x,y)。它是关于y的优先队列,同时又是关于x的搜索树。在这样的树中,每一次旋转都需要耗时O(logn)。如果用红黑树来描述平衡优先搜索树,则因为每一次插入或杀出仅需要一次旋转,所欲插入或删除操作的总时间仍然为O(logn)。当使用AVL树时,则删除操作的时间将变为O()
- 虽然对比较小的可以在内存中处理的字典,AVL树、红黑树和分裂树均能提供比较高的性能,但是对大型字典,它们就不适合了。当字典存储在磁盘上时,需要使用度数更大、高度更小的搜索树,例如B-树
转载地址:https://dongshao.blog.csdn.net/article/details/104077107 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年05月02日 17时29分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
docker安装mysql
2019-04-30
jfinal排查过滤拦截相关请求
2019-04-30
java文件管道拷贝工具类
2019-04-30
mysql连接信息jdbcUrl的常用写法
2019-04-30
HTML页面meta标签内容详解
2019-04-30
oracle之decode
2019-04-30
oracle列转换成行
2019-04-30
nginx设置开启启动
2019-04-30
linux中设置tomcat自启动
2019-04-30
mysql错误:Row size too large (> 8126).
2019-04-30
umount时目标忙解决办法
2019-04-30
java 判断一个url是否可以访问的方法
2019-04-30
Table 'mysql.user' doesn't exist
2019-04-30
mysql通过frm文件查找表结构定义
2019-04-30
如何在删除ibdata1和ib_logfile的情况下恢复MySQL数据库
2019-04-30
oracle随机数的产生
2019-04-30
oracle分级汇总rollup
2019-04-30
oracle数据库translate函数
2019-04-30
oracle修改日期的显示方式
2019-04-30