当前课程知识点:数据结构(下) >  第八章 高级搜索树(上) >  (a2)伸展树:双层伸展 >  08A2-3 子孙同侧

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

08A2-3 子孙同侧在线视频

08A2-3 子孙同侧

下一节:08A2-4 点睛之笔

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

08A2-3 子孙同侧课程教案、知识点、字幕

实际上 那另一只神奇的眼睛

只有在zig-zig或zag-zag的情况下才会发光

不妨只考虑其中的一种 比如zig-zig情况

也就是节点v和他的父亲p都是左孩子的情况

在这里为了便于对比

我们不妨将这祖孙三代逐层伸展调整结果先画出来

也就是v首先经过父节点p的一次zig旋转上升一层

进而在通过祖父节点g的一次zig旋转再上升一层

我们已经对此非常熟悉 整个过程平淡无奇

我们刚才也讲过 它会导致最坏情况

我们再来看看 Tarjan所点出的那只眼睛

或者说他所建议的调整方法

这里关键中的关键是 我们需要首先越级

从祖父而不是父节点来开始旋转

具体来说 经过祖父节点的一次顺时针zig旋转

节点p以及v 都会上升一层

接下来呢 进而对这棵局部子树新的树根

也就是p再做一次zig顺时针旋转

从而使得v能够继续上升一层

成为这棵局部子树的树根

将新的这种调整方法的结果

与此前的逐层调整方法结果做一对比

坦诚的讲第一次看到Tarjan

为这条龙所点上的这只眼睛的时候

我并没有察觉到它有什么与众不同之处

现在的你 或许也是这样

没错 各种的奥妙的确不易察觉 因为从效果来看

二者无非都是将v这个节点提升了两层而已

然而他们毕竟在局部拓扑结构上 还是有微妙的差异

更重要的是 这种局部的微妙差异 将导致全局的不同

而且那种不同将是根本性的 颠覆性的

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

第零章

-选课之前

--写在选课之前

--宣传片

-考核方式

--考核方式

-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: 逆序对

-本章测验

--本章测试

08A2-3 子孙同侧笔记与讨论

也许你还感兴趣的课程:

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