当前课程知识点:数据结构(下) >  第七章 二叉搜索树 >  (d4)AVL树:(3+4)-重构 >  07D4-4 综合评价

返回《数据结构(下)》慕课在线视频课程列表

07D4-4 综合评价在线视频

07D4-4 综合评价

下一节:08A1-1 宽松平衡

返回《数据结构(下)》慕课在线视频列表

07D4-4 综合评价课程教案、知识点、字幕

最后 我们来对AVL树的性能和特点

做一个总体的评价

首先 我们注意到AVL树

具有极高的理论价值

因为它正面地告诉我们

的确存在这样一种数据结构

可以在渐近Logn的复杂度意义下

兼顾所有的静态和动态操作

而且为此 我们的存储负担

也不会有实质的增加

当然 AVL树的缺点也是非常明显的

这也将成为我们的动力

促使我们去不断地改进

并提出更好更高效的数据结构

那么 AVL树的第一个缺点就在于

它人为地引入了一个

所谓的平衡因子概念

并且要求在这个数据结构中

隐式地或者显式地存放

为此我们往往需要去改造

数据项原有的基本结构

或者再做额外的封装

无论如何这一要求都过于做作

显得不是那么自然

那么针对这一问题 在下一章

我们将首先引入所谓的伸展树

我们将会看到 伸展树

将无需记录和维护

任何诸如平衡因子式的指标

无论是显式的 还是隐式的

另外 AVL树的实测性能

与它的理论性能之间

存在着较大的差距

尤其是正如我们所看到的

它的删除操作要更为复杂

尽管knuth曾经指出

这种最坏的情况以及较坏的情况

出现的概率其实很低

平均而言 大致每五次操作

才会引起一次旋转

如果说以上的两个缺点

都属于鸡蛋里挑骨头

那么第三个缺点却的确是致命的

因为我们已经看到 对于AVL树而言

它的插入操作和删除操作是非常不对等的

这种不对等就集中体现在每次操作之后

所涉及的旋转调整次数

具体来说 每次插入操作之后

最多只需一轮调整 也就是常数次

而在删除操作之后

为了使得全树重新恢复平衡

正如我们已经看到的 在最坏的情况下

我们需要做多达Logn次旋转调整

因此就全树中各节点之间的

拓扑连接关系而言

在插入操作之后

可以保证变化量保持在常数的范围

而删除操作却未必能做到这样

实际上 在很多高级的数据结构和算法中

都对这种拓扑结构的变化量

有严格地要求

具体来说 我们这里高达Logn的变化量

绝对是不能满足要求的

我们希望将它们控制到更低

比如在下一章 我们将要介绍到红黑树

则可以将这个变化量严格地控制在

每次不超过常数

无论对于插入操作

还是删除操作都是如此

数据结构(下)课程列表:

第零章

-选课之前

--写在选课之前

--宣传片

-考核方式

--考核方式

-OJ系统说明

--关于OJ

--1-注册与登录

--2-界面与选课

--3-提交测试

-关于课程教材与讲义

--课程教材与讲义

-关于讨论区

--关于讨论区

-微信平台

--html

-PA晋级申请

--PA晋级

--MOOC --> THU 晋级申请专区

--THU --> CST 晋级申请专区

--编程作业不过瘾?且来清华试比高!

第七章 二叉搜索树

-(a)概述

--07A-1 纵览

--07A-2 循关键码访问

--07A-3 有序性

--07A-4 单调性

--07A-5 接口

-(a)概述--作业

-(b1)BST:查找

--07B1-1 概述

--07B1-2 查找:算法

--07B1-3 查找:理解

--07B1-4 查找:实现

--07B1-5 查找:语义

-第七章 二叉搜索树--(b1)BST:查找

-(b2)BST:插入

--07B2-1 插入:算法

--07B2-2 插入:实现

-(b2)BST:插入--作业

-(b3)BST:删除

--07B3-1 删除:框架

--07B3-2 删除:单分支

--07B3-3 删除:双分支

--07B3-4 删除:复杂度

-第七章 二叉搜索树--(b3)BST:删除

-(c)平衡与等价

--07C-1 极端退化

--07C-2 平均高度

--07C-3 理想+适度

--07C-4 歧义=等价

--07C-5 等价变换

-(c)平衡与等价--作业

-(d1)AVL树:重平衡

--07D1-1 AVL=BBST

--07D1-2 平衡因子

--07D1-3 适度平衡

--07D1-4 接口

--07D1-5 失衡+复衡

-第七章 二叉搜索树--(d1)AVL树:重平衡

-(d2)AVL树:插入

--07D2-1 插入:单旋

--07D2-2 插入:双旋

--07D2-3 插入:实现

-(d2)AVL树:插入--作业

-(d3)AVL树:删除

--07D3-1 删除:单旋

--07D3-2 删除:双旋

--07D3-3 删除:实现

-(d3)AVL树:删除--作业

-(d4)AVL树:(3+4)-重构

--07D4-1 ”3+4“重构

--07D4-2 ”3+4“实现

--07D4-3 rotateAt()

--07D4-4 综合评价

-(d4)AVL树:(3+4)-重构--作业

-本章测验

--章节测验

第八章 高级搜索树(上)

-(a1)伸展树:逐层伸展

--08A1-1 宽松平衡

--08A1-2 局部性

--08A1-3 自适应调整

--08A1-4 逐层伸展

--08A1-5 实例

--08A1-6 一步一步往上爬

--08A1-7 最坏情况

--习题

-(a2)伸展树:双层伸展

--08A2-1 双层伸展

--08A2-2 子孙异侧

--08A2-3 子孙同侧

--08A2-4 点睛之笔

--08A2-5 折叠效果

--08A2-6 分摊性能

--08A2-7 最后一步

--习题

-(a3)伸展树:算法实现

--08A3-1 功能接口

--08A3-2 伸展算法

--08A3-3 四种情况

--08A3-4 查找算法

--08A3-5 插入算法

--08A3-6 删除算法

--08A3-7 综合评价

--习题

-(b1)B-树:动机

--08B1-1 640KB

--08B1-2 越来越大的数据

--08B1-3 越来越小的内存

--08B1-4 一秒与一天

--08B1-5 分级I/O

--08B1-6 1B = 1KB

--习题

-(b2)B-树:结构

--08B2-1 观察体验

--08B2-2 多路平衡

--08B2-3 还是I/O

--08B2-4 深度统一

--08B2-5 阶次含义

--08b2-6: 紧凑表示

--08B2-7 BTNode

--08B2-8 BTree

--习题

-(b3)B-树:查找

--08B3-1 算法过程

--08B3-2 操作实例

--08B3-3 算法实现

--08B3-4 主次成本

--08B3-5 最大高度

--08B3-6 最小高度

--习题

第八章 高级搜索树(下)

-(b4)B-树: 插入

--08B4-1 算法框架

--08B4-2 分裂

--08B4-3 再分裂

--08B4-4 分裂到根

--08B4-5: 实例演示

--习题

-(b5)B-树: 删除

--08B5-1 算法框架

--08B5-2 旋转

--08B5-3 合并

--08B5-4 实例演示

--08B5-5 道法自然

--习题

-(xa1)红黑树:动机

--08XA1-1 观察体验

--08XA1-2 持久性

--08XA1-3 关联性

--08XA1-4 O(1)重构

--习题

-(xa2)红黑树:结构

--08XA2-1 定义规则

--08XA2-2 实例验证

--08XA2-3 提升变换

--08XA2-4 末端节点

--08XA2-5 红黒树,即是B-树

--08XA2-6 平衡性

--08xa2-7: 接口定义

--习题

-(xa3)红黑树:插入

--08XA3-1 以曲为直

--08XA3-2 双红缺陷

--08XA3-3 算法框架

--08XA3-4 RR-1

--08XA3-5 RR-2

--08XA3-6 归纳回味

--习题

-(xa4)红黑树:删除

--08XA4-1 以曲为直

--08XA4-2 算法框架

--08XA4-3 双黑缺陷

--08XA4-4 BB-1

--08XA4-5 反观回味

--08XA4-6 BB-2R

--08XA4-7 BB-2B

--08XA4-8 BB-3

--08xa4-9: 归纳体味

-本章测验

--习题

第九章 词典

-(b)散列:原理

--09B-1 从服务到电话

--09B-2 循值访问

--09B-3 数组

--09B-4 原理

--09B-5 散列

--09B-6 冲突

--习题

-(c)散列:散列函数

--09C-1 冲突难免

--09C-2 何谓优劣

--09C-3 整除留余

--09C-4 以蝉为师

--09C-5 M+A+D

--09C-6 平方取中

--09C-7 折叠汇总

--09C-8 伪随机数

--09C-9 多项式

--09C-A Vorldmort

--09C-B DSA@THU

--习题

-(d1)散列:排解冲突(1)

--09D1-1 一山二虎

--09D1-2 泾渭分明

--09D1-3 开放定址

--09D1-4 线性试探

--09D1-5 懒惰删除

--习题

-(d2)散列:排解冲突(2)

--09D2-1 平方试探

--09D2-2 一利一弊

--09D2-3 至多半载

--09D2-4 M + Lemda

--09D2-5 双蜓点水

--09D2-6 4k + 3

--09D2-7 双平方定理

--09D2-8 泾渭分明

--习题

-(e)桶/计数排序

--09E-1 大数据 + 小范围

--09E-2 桶排序

--09E-3 计数排序

--习题

-本章测验

--本章测试

第十章 优先级队列

-(a1)需求与动机

--10a1-1: 应用需求

--10a1-2: 计算模式

--10a1-3: 功能接口

--习题

-(a2)基本实现

--10a2-1: 向量

--10a2-2: 有序向量

--10a2-3: BBST

--习题

-(b1)完全二叉堆:结构

--10b1-1: 完全二叉树

--10b1-2: 结构性

--10b1-3: 形具神备

--10b1-4: 堆序性

--习题

-(b2)完全二叉堆:插入与上滤

--10b2-1: 上滤

--10b2-2: 实例

--10b2-3: 实现

--10b2-4: 效率

--习题

-(b3)完全二叉堆:删除与下滤

--10b3-1: 算法

--10b3-2: 实例

--10b3-3: 实现

--10b3-4: 效率

--习题

-(b4)完全二叉堆:批量建堆

--10b4-1 : 自上而下的上滤:算法

--10b4-2: 自上而下的上滤:效率

--10b4-3: 自下而上的下滤:算法

--10b4-4 : 自下而上的下滤:实例

--10B4-5: 自下而上的下滤:效率

--习题

-(c)堆排序

--10c-1: 算法

--10c-2: 就地

--10c-3: 实现

--10c-4: 实例

--习题

-(xa1)左式堆:结构

--10xa-1: 第一印象

--10xa1-2: 堆之合并

--10xa1-3: 奇中求正

--10xa1-4: NPL

--10xa1-5: 左倾性

--10xa1-6: 左展右敛

--习题

-(xa2)左式堆:合并

--10xa2-1: LeftHeap模板类

--10xa2-2: 算法

--10xa2-3: 实现

--10xa2-4: 实例

--习题

-(xa3)左式堆:插入与删除

--10xa3-1: 插入即是合并

--10xa3-2: 删除亦是合并

-本章测验

--本章测试

第十一章 串(上)

-(a)ADT

--11a-1: 定义+特点

--11a-2: 术语

--11a-3: ADT

--习题

-(b1)串匹配

--11b1-1: 问题与需求

--11b1-2 算法测评

--习题

-(b2)蛮力匹配

--11b2-1: 构思

--11b2-2: 版本一

--11b2-3: 版本二

--11b2-4: 性能

--习题

-(c1)KMP算法:从记忆力到预知力

--11c1-1: 重复匹配的前缀

--11c1-2: 不变性

--11c1-3 : 记忆力

--11c1-4: 预知力

--习题

-(c2)KMP算法:查询表

--11c2-1: 制表备查

--11c2-2: 主算法

--11c2-3: 实例

--习题

-(c3)KMP算法:理解next[]表

--11c3-1: 快速移动

--11c3-2: 避免回溯

--11C3-3: 通配哨兵

--习题

-(c4)KMP算法:构造next[]表

--11c4-1: 递推

--11c4-2: 算法

--11c4-3: 实现

--习题

-(c5)KMP算法:分摊分析

--11c5-1: 失之粗糙

--11c5-2: 精准估计

--习题

-(c6)KMP算法:再改进

--11c6-1: 美中不足

--11c6-2: 以卵击石

--11c6-3: 前车之覆

--11c6-4 后车之鉴

--11c6-5 : 可视对比

第十一章 串(下)

-(d1)BM_BC算法:以终为始

--11d1-1: 不对称性

--11d1-2: 善待教训

--11d1-3: 前轻后重

--11d1-4: 以终为始

-(d2)BM_BC算法:坏字符

--11d2-1: 坏字符

--11d2-2: 特殊情况

-(d3)BM_BC算法:构造bc[]

--11d3: 画家策略

-(d4)BM_BC算法:性能分析

--11d4-1: 最好情况

--11d4-2: 最坏情况

-(e1)BM_GS算法:好后缀

--11e1-1: 兼顾经验

--11e1-2: 好后缀策略

--11e1-3: 实例体验

-(e2)BM_GS算法:构造gs表

--11e2: 构造gs表

-(e3)BM_GS算法:综合性能

--11e3-1: BM之性能

--11e3-2: 各算法纵览

-(f1)Karp-Rabin算法:串即是数

--11f1-1: 化串为数

--11f1-2: 凡物皆数

--11f1-3: 串亦是数

-(f2)Karp-Rabin算法:散列

--11f2-1: 数位溢出

--11f2-2: 散列压缩

--11f2-3: 应对冲突

--11f2-4: 指纹更新

-本章测验

--本章测试

第十二章 排序

-(a1)快速排序:算法A

--12a1-1: 分而治之

--12a1-2: 轴点

--12a1-3: 构造轴点

--12a1-4: 单调性 + 不变性

-- 12a1-5: 实例

--习题

-(a2)快速排序:性能分析

--12a2-1: 不稳定 + 就地

--12a2-2: 最好情况 + 最坏情况

--12a2-3: 平均情况

--习题

-(a4)快速排序:变种

--12a4-1: 不变性

--12a4-2: 单调性

--12a4-3: 实现

--12a4-4: 实例

--12a4-5: 时间 + 空间 + 稳定性

-(b1)选取:众数

--12b1-1: 选取 + 中位数

--12b1-2: 从中位数到众数

--12b1-3: 从频繁数到众数

--12b1-4: 减而治之

--12b1-5: 算法实现

-(b3)选取:通用算法

--12b3-1: 尝试

--12b3-2: quickSelect

--12b3-3: linearSelect:算法

--12b3-4: linearSelect:性能分析A

--12b3-5 : linearSelect:性能分析B

--12b3-6 : linearSelect:性能分析C

--习题

-(c1) 希尔排序:Shell序列

--12c1-1: 策略

--12c1-2: 实例

--12c1-3: 循秩访问

--12c1-4: 插入排序

--12c1-5: Shell序列

--习题

-(c2)希尔排序:逆序对

--12c2-1: 邮资问题

--12c2-2: 定理K

--12c2-3: 逆序对

-本章测验

--本章测试

07D4-4 综合评价笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。