当前课程知识点:数据结构(下) > 第七章 二叉搜索树 > (d4)AVL树:(3+4)-重构 > 07D4-4 综合评价
最后 我们来对AVL树的性能和特点
做一个总体的评价
首先 我们注意到AVL树
具有极高的理论价值
因为它正面地告诉我们
的确存在这样一种数据结构
可以在渐近Logn的复杂度意义下
兼顾所有的静态和动态操作
而且为此 我们的存储负担
也不会有实质的增加
当然 AVL树的缺点也是非常明显的
这也将成为我们的动力
促使我们去不断地改进
并提出更好更高效的数据结构
那么 AVL树的第一个缺点就在于
它人为地引入了一个
所谓的平衡因子概念
并且要求在这个数据结构中
隐式地或者显式地存放
为此我们往往需要去改造
数据项原有的基本结构
或者再做额外的封装
无论如何这一要求都过于做作
显得不是那么自然
那么针对这一问题 在下一章
我们将首先引入所谓的伸展树
我们将会看到 伸展树
将无需记录和维护
任何诸如平衡因子式的指标
无论是显式的 还是隐式的
另外 AVL树的实测性能
与它的理论性能之间
存在着较大的差距
尤其是正如我们所看到的
它的删除操作要更为复杂
尽管knuth曾经指出
这种最坏的情况以及较坏的情况
出现的概率其实很低
平均而言 大致每五次操作
才会引起一次旋转
如果说以上的两个缺点
都属于鸡蛋里挑骨头
那么第三个缺点却的确是致命的
因为我们已经看到 对于AVL树而言
它的插入操作和删除操作是非常不对等的
这种不对等就集中体现在每次操作之后
所涉及的旋转调整次数
具体来说 每次插入操作之后
最多只需一轮调整 也就是常数次
而在删除操作之后
为了使得全树重新恢复平衡
正如我们已经看到的 在最坏的情况下
我们需要做多达Logn次旋转调整
因此就全树中各节点之间的
拓扑连接关系而言
在插入操作之后
可以保证变化量保持在常数的范围
而删除操作却未必能做到这样
实际上 在很多高级的数据结构和算法中
都对这种拓扑结构的变化量
有严格地要求
具体来说 我们这里高达Logn的变化量
绝对是不能满足要求的
我们希望将它们控制到更低
比如在下一章 我们将要介绍到红黑树
则可以将这个变化量严格地控制在
每次不超过常数
无论对于插入操作
还是删除操作都是如此
-选课之前
--写在选课之前
--宣传片
-考核方式
--考核方式
-OJ系统说明
--关于OJ
--1-注册与登录
--2-界面与选课
--3-提交测试
-关于课程教材与讲义
--课程教材与讲义
-关于讨论区
--关于讨论区
-微信平台
--html
-PA晋级申请
--PA晋级
-(a)概述
--07A-1 纵览
--07A-5 接口
-(a)概述--作业
-(b1)BST:查找
-第七章 二叉搜索树--(b1)BST:查找
-(b2)BST:插入
-(b2)BST:插入--作业
-(b3)BST:删除
-第七章 二叉搜索树--(b3)BST:删除
-(c)平衡与等价
-(c)平衡与等价--作业
-(d1)AVL树:重平衡
-第七章 二叉搜索树--(d1)AVL树:重平衡
-(d2)AVL树:插入
-(d2)AVL树:插入--作业
-(d3)AVL树:删除
-(d3)AVL树:删除--作业
-(d4)AVL树:(3+4)-重构
-(d4)AVL树:(3+4)-重构--作业
-本章测验
--章节测验
-(a1)伸展树:逐层伸展
--习题
-(a2)伸展树:双层伸展
--习题
-(a3)伸展树:算法实现
--习题
-(b1)B-树:动机
--习题
-(b2)B-树:结构
--习题
-(b3)B-树:查找
--习题
-(b4)B-树: 插入
--习题
-(b5)B-树: 删除
--习题
-(xa1)红黑树:动机
--习题
-(xa2)红黑树:结构
--习题
-(xa3)红黑树:插入
--习题
-(xa4)红黑树:删除
-本章测验
--习题
-(b)散列:原理
--09B-3 数组
--09B-4 原理
--09B-5 散列
--09B-6 冲突
--习题
-(c)散列:散列函数
--习题
-(d1)散列:排解冲突(1)
--习题
-(d2)散列:排解冲突(2)
--习题
-(e)桶/计数排序
--习题
-本章测验
--本章测试
-(a1)需求与动机
--习题
-(a2)基本实现
--习题
-(b1)完全二叉堆:结构
--习题
-(b2)完全二叉堆:插入与上滤
--习题
-(b3)完全二叉堆:删除与下滤
--习题
-(b4)完全二叉堆:批量建堆
--习题
-(c)堆排序
--习题
-(xa1)左式堆:结构
--习题
-(xa2)左式堆:合并
--习题
-(xa3)左式堆:插入与删除
-本章测验
--本章测试
-(a)ADT
--习题
-(b1)串匹配
--习题
-(b2)蛮力匹配
--习题
-(c1)KMP算法:从记忆力到预知力
--习题
-(c2)KMP算法:查询表
--习题
-(c3)KMP算法:理解next[]表
--习题
-(c4)KMP算法:构造next[]表
--习题
-(c5)KMP算法:分摊分析
--习题
-(c6)KMP算法:再改进
-(d1)BM_BC算法:以终为始
-(d2)BM_BC算法:坏字符
-(d3)BM_BC算法:构造bc[]
-(d4)BM_BC算法:性能分析
-(e1)BM_GS算法:好后缀
-(e2)BM_GS算法:构造gs表
-(e3)BM_GS算法:综合性能
-(f1)Karp-Rabin算法:串即是数
-(f2)Karp-Rabin算法:散列
-本章测验
--本章测试
-(a1)快速排序:算法A
-- 12a1-5: 实例
--习题
-(a2)快速排序:性能分析
--习题
-(a4)快速排序:变种
-(b1)选取:众数
-(b3)选取:通用算法
--习题
-(c1) 希尔排序:Shell序列
--习题
-(c2)希尔排序:逆序对
-本章测验
--本章测试