当前课程知识点:数据结构(下) > 第八章 高级搜索树(上) > (a2)伸展树:双层伸展 > 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晋级
-(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)希尔排序:逆序对
-本章测验
--本章测试