当前课程知识点:Data Structures and Algorithm Design Part II >  07.Binary Search Tree >  D4.AVL : (3+4)-construction >  07D4-1

返回《Data Structures and Algorithm Design Part II》慕课在线视频课程列表

07D4-1在线视频

下一节:07D4-2

返回《Data Structures and Algorithm Design Part II》慕课在线视频列表

07D4-1课程教案、知识点、字幕

实际上 以上针对AVL树

插入操作和删除操作

所介绍的单旋式和双旋式调整技巧

无非是为了帮助你形成对算法的理解

而在真正的实现时

我们大可不必机械地如此理解

这样一个过程可以比喻为玩魔方

是的 你需要在规则的允许下

通过巧妙的旋转组合

使之转入某种特定的状态

比如六面各自同色

那么你是否去过魔方的组装车间?

你会发现那里的工人

可不是按照你这样的规则

在那儿进行这样的旋转

实际上 它们无非是将魔方的

一个又一个组件直接地拼接为一个魔方

工人们之所以这么做

是因为它们最大也是唯一的目标是

尽快地以最高的效率完成魔方的组装

我们这里呢 也不妨借助这一策略

因为对于AVL树的重平衡化而言

我们最终在乎的并不是所谓的技巧

而是在于这个过程的效率

我们来看一下

如何将魔方组装工人的那种策略

用到我们这个问题上

具体来说 我们依然假设g

就是当前最低的那个失衡祖先

并且同样地沿着那个最长的分支

去考察g p v这祖孙三代

以下我们并不急于对它们进行旋转

而是首先做重命名

也就是说

按照它们在中序遍历序列中的次序

自小到大

重新命名为a b以及c

对照我们此前所讲的各种情况

无论是Zig-zag zag-zig

Zig-zig或者是zag-zag

你会发现在它们以下

无非是最多4棵子树

那么我们也需要对这4棵子树做重命名

而且命名的规则

同样是参照中序遍历的次序

也就是T0至最小的那棵树

T1是次小的 T2是较大的 T3是最大

此时 如果我们依然按照中序遍历的次序

将这两个序列混合起来

就可以得到一个长度为7的序列

在这个序列中 三个节点a b c

必然是镶嵌于这4棵子树之间

实际上 无论是哪种具体的情况

经过这样的重命名之后

按照中序遍历的次序

必然是从T0到a 再从a到T1

再从T1到b 然后从b到T2

再从T2到c 最终由c到T3

你应该不会觉得奇怪

因为这恰恰就是BST所谓的单调性

在这样一棵局部子树的具体体现

在调整之前 即便这棵子树是失衡的

它也依然是一棵BST

所以这个单调性应该自然满足

而在调整之后 尽管它已经恢复了平衡

但是这个单调性也依然需要保持

因此 我们可以统一地将这三个顶点abc

以及这4棵子树

按照这样一个拓扑关系直接地拼接起来

具体来说 以a和c

分别作为b的左和右孩子

而T0和T1将作为a的左和右子树

T2和T3分别作为c的左和右子树

这样一种拼接是针对于三个节点

以及下属4棵子树而言的

所以也称作3+4重构

在此 你不妨稍作暂停

并对照此前所介绍的各种情况

以及相应的调整算法

应该会发现 无论是插入还是删除

无论是单旋 还是双旋

最终的效果都应该是这样一种形式

这也犹如无论魔方的最初状态如何

也无论你所设计的旋转方案具体如何

最终必然应该达到

你心目中早已设计好的一个结局

对于魔方而言 一般都是六面各自同色

而对于我们的BBST而言

则是在此局部地重新平衡

按照这样的一个思路

我们可以更为概括

而且更为深入地来理解并且记忆

以上各种情况的处理手法

而更好的消息是 按照这样一种理解

我们也可以更加简明 更加高效

而且更加安全鲁棒地来实现相应的重构算法

Data Structures and Algorithm Design Part II课程列表:

07.Binary Search Tree

-A.introduction

--07A-1

--07A-2

--07A-3

--07A-4

--07A-5

-A.introduction--Homework

-B1.BST : search

--07B1-1

--07B1-2 查找:算法

--07B1-3 查找:理解

--07B1-4 查找:实现

--07B1-5 查找:语义

-B1.BST : search--Homework

-B2.BST : insertion

--07B2-1

--07B2-2

-B2.BST : insertion--Homework

-B3.BST : removal

--07B3-1

--07B3-2

--07B3-3

--07B3-4

-B3.BST : reomval--Homework

-C.balance+equivalence

--07C-1

--07C-2

--07C-3

--07C-4

--07C-5

-C.balance+equivalence--Homework

-D1.AVL : rebalance

--07D1-1

--07D1-2

--07D1-3

--07D1-4

--07D1-5

-D1.AVL : rebalance--Homework

-D2.AVL : insertion

--07D2-1

--07D2-2

--07D2-3

-D2.AVL : insertion--Homework

-D3.AVL : removal

--07D3-1

--07D3-2 删除:双旋

--07D3-3 删除:实现

-D3.AVL : removal--Homework

-D4.AVL : (3+4)-construction

--07D4-1

--07D4-2

--07D4-3

--07D4-4

-D4.AVL : (3+4)-construction--Homework

-Homework

--Homework

08.ABST I

-A1.Splay_Tree.splay1

--08A1-1

--08A1-2

--08A1-3

--08A1-4

--08A1-5

--08A1-6

--08A1-7

--Homework

-A2.Splay_Tree.splay2

--08A2-1

--08A2-2

--08A2-3

--08A2-4

--08A2-5

--08A2-6

--08A2-7

--Homework

-A3.Splay_Tree.implementation

--08A3-1

--08A3-2

--08A3-3

--08A3-4

--08A3-5

--08A3-6

--08A3-7

--Homework

-B1.B-Tree.motivation

--08B1-1

--08B1-2

--08B1-3

--08B1-4

--08B1-5

--08B1-6

--Homework

-B2.B-Tree.structure

--08B2-1

--08B2-2

--08B2-3

--08B2-4

--08B2-5

--08b2-6

--08B2-7

--08B2-8

--Homework

-B3.B-Tree.search

--08B3-1

--08B3-2

--08B3-3

--08B3-4

--08B3-5

--08B3-6

--Homework

08.ABST II

-B4.B-Tree.insertion

--08B4-1

--08B4-2

--08B4-3

--08B4-4

--08B4-5

--Homework

-B5.B-Tree.removal

--08B5-1

--08B5-2

--08B5-3

--08B5-4

--08B5-5

--Homework

-XA1.Red-Black.motivation

--08XA1-1

--08XA1-2

--08XA1-3

--08XA1-4

--Homework

-XA2.Red-Black.structure

--08XA2-1

--08XA2-2

--08XA2-3

--08XA2-4

--08XA2-5

--08XA2-6

--08XA2-7

--Homework

-XA3.Red-Black.insertion

--08XA3-1

--08XA3-2

--08XA3-3

--08XA3-4

--08XA3-5

--08XA3-6

--Homework

-XA4.Red-Black.removal

--08XA4-1

--08XA4-2

--08XA4-3

--08XA4-4

--08XA4-5

--08XA4-6

--08XA4-7

--08XA4-8

--08XA4-9

-Homework

--Homework

09.Dictionary

-B.hashing.principle

--09B-1

--09B-2

--09B-3

--09B-4

--09B-5

--09B-6

--Homework

-C.Hashing.Hash-Function

--09C-1

--09C-2

--09C-3

--09C-4

--09C-5

--09C-6

--09C-7

--09C-8

--09C-9

--09C-A

--09C-B

--Homework

-D1.Hashing.Solving-Collision-1

--09D1-1

--09D1-2

--09D1-3

--09D1-4

--09D1-5

--Homework

-D2.Hashing.Solving-Collision-2

--09D2-1

--09D2-2

--09D2-3

--09D2-4

--09D2-5

--09D2-6

--09D2-7

--09D2-8

--Homework

-E.Bucketsort

--09E-1

--09E-2

--09E-3

--Homework

-Homework

--Homework

10.Priority Queue

-A1.motivation

--10A1-1

--10A1-2

--10A1-3

--Homework

-A2.Basic_Implementations

--10A2-1

--10A2-2

--10A2-3

--Homework

-B1.Complete_Binary_Heap.structure

--10B1-1

--10B1-2

--10B1-3

--10B1-4

--Homework

-B2.Complete_Binary_Heap.insertion

--10B2-1

--10B2-2

--10B2-3

--10B2-4

--Homework

-B3.Complete_Binary_Heap.removal

--10B3-1

--10B3-2

--10B3-3

--10B3-4

--Homework

-B4.Complete_Binary_Heap.heapification

--10B4-1

--10B4-2

--10B4-3

--10B4-4

--10B4-5

--Homework

-C.Heapsort

--10C-1

--10C-2

--10C-3

--10C-4

--Homework

-XA1.Leftist_Heap.structure

--10XA-1

--10XA1-2

--10XA1-3

--10XA1-4

--10XA1-5

--10XA1-6

--Homework

-XA2.Leftist_Heap.merge

--10XA2-1

--10XA2-2

--10XA2-3

--10XA2-4

--Homework

-XA3.Leftist_Heap.insertion+removal

--10XA3-1

--10XA3-2

-Homework

--Homework

11.String I

-A.ADT

--11A-1

--11A-2

--11A-3

--Homework

-B1.Pm

--11B1-1

--11B1-2

--Homework

-B2.brute-force

--11B2-1

--11B2-2

--11B2-3

--11B2-4

--Homework

-C1.Kmp.memorization

--11C1-1

--11C1-2

--11C1-3

--11C1-4

--Homework

-C2.Kmp.lookup-table

--11C2-1

--11C2-2

--11C2-3

--Homework

-C3.Kmp.understanding_next[]

--11C3-1

--11C3-2

--11C3-3

--Homework

-C4.Kmp.constructing_next[]

--11C4-1

--11C4-2

--11C4-3

--Homework

-C5.Kmp.amortization

--11C5-1

--11C5-2

--Homework

-C6.Kmp.improvement

--11C6-1

--11C6-2

--11C6-3

--11C6-4

--11C6-5

11.String II

-D1.BM_BC.begin_with_the_end

--11D1-1

--11D1-2

--11D1-3

--11D1-4

-D2.BM_BC.bad_character

--11D2-1

--11D2-2

-D3.BM_BC.constructing_bc[]

--11D3

-D4.Bm_BC.performance

--11D4-1

--11D4-2

-E1.Bm_GS.good-suffix

--11E1-1

--11E1-2

--11E1-3

-E2.Bm_GS.constructing_gs[]

--11E2

-E3.Bm_GS.performance

--11E3-1

--11E3-2

-F1.KR.fingerprint

--11F1-1

--11F1-2

--11F1-3

-F2.KR.hashing

--11F2-1

--11F2-2

--11F2-3

--11F2-4

-Homework

--Homework

12.Sorting

-A1.Quicksort.algorithm

--12A1-1

--12A1-2

--12A1-3

--12A1-4

-- 12A1-5

--Homework

-A2.Quicksort.performance

--12A2-1

--12A2-2

--12A2-3

--Homework

-A4.Quicksort.Variation

--12A4-1

--12A4-2

--12A4-3

--12A4-4

--12A4-5

-B1.Selection.mode

--12B1-1

--12B1-2

--12B1-3

--12B1-4

--12B1-5

-B2.Selection.Median

--12B3-1

--12B3-2

--12B3-3

--12B3-4

--12B3-5

--12B3-6

--Homework

-C1.Shellsort.Shell's sequence

--12C1-1

--12C1-2

--12C1-3

--12C1-4

--12C1-5

--Homework

-C2.Shellsort.Inversion

--12C2-1

--12C2-2

--12C2-3

-Homework

--Homework

07D4-1笔记与讨论

也许你还感兴趣的课程:

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