算法设计与分析6课件

第6章变治法变治策略预排序平衡查找树

AVL树2-3树（扩展B、B+、B*树）堆与优先队列堆排序（堆分类）问题化简本章习题第6章变治法变治策略第6章变治法变治策略预排序平衡查找树

AVL树2-3树（扩展B、B+、B*树）堆与优先队列堆排序（堆分类）问题化简本章习题第6章变治法变治策略第6章变治法变治策略预排序平衡查找树

AVL树2-3树（扩展B、B+、B*树）堆与优先队列堆排序（堆分类）问题化简本章习题第6章变治法变治策略变治策略变治策略通用的算法设计方法，基于变换的思想变：变换问题更容易求解治：对变换后的问题求解3种主要类型实例化简：问题求解变得更简单，如预排序改变表现：改变问题的表现形式，如AVL树，2-3树，堆问题化简：问题变为另一个问题。如数学建模，将具体应用问题用变量、函数、方程等数学对象表达求解问题更简单方便另一种表现另一个问题变治策略变治策略求解问题更简单方便预排序：元素唯一性检验预排序古老思想：若列表有序，一些与列表有关的问题更容易求解。

——依赖于排序算法的时间效率【例1】检验数组中元素的唯一性蛮力：逐个比较数组元素，直到找到两个相等元素或全部元素比较完毕为止。时间效率O

(n2)变治：预排序化简问题后求解。即：数组排序后检查连续元素。排序后等值元素（重复元素）一定相邻

算法

PresortElementUniqueness

(A[0...n-1])

对数组A排序//选nlogn型算法

fori←0ton-2do

if

A[i]=A[i+1]

returnfalse

returntrue预排序：元素唯一性检验预排序预排序：模式统计【例2】模式统计模式：列表中出现频率最高的元素。如{5,1,5,7,6,5,7}的模式为5，模式可能不止一个

问题：在列表中找出模式

蛮力策略：扫描列表，统计每个元素的频率，找出频率最高的元素

蛮力实现：（方法之一）设一个辅助列表，扫描元素与辅助列表中的元素一一比较，结果：若匹配（辅助列表中已有），该元素频率加1.不匹配（辅助列表中没有），新元素加入辅助列表，其频率置1.本例最终的辅助列表：{5(3),1(1),7(2),6(1)}括号内为频率。——扫描辅助列表，找出最大频率（3）的元素（5）

最坏情况：扫描原始列表时，每个元素在辅助列表中都没有匹配，作为新元素加入辅助列表，原列表的第k个元素加入辅助列表时，需要与辅助列表中已加入的k-1个元素比较，共k-1次。预排序：模式统计【例2】模式统计预排序：模式统计（续）

最差效率：

变治法——预排序（nlogn型），排序后等值元素一定相邻

扫描统计：模式具有最多的相邻元素，需比较

n

-1次。PresortMode_1(A[0...n-1])//行程算法

对数组A排序//排序结果{1,5,5,5,6,7,7}i←0，ModeFrequency←0

//最大频率，最大行程长度

while(i≤n-1)

runlength←1，runvalue←A[i]

//行程长度=等值元素个数

while(i+runlength≤n-1and

A[i+runlength]=runvalue

)runlength++//与下一个元素相等则行程长度+1

if(runlength>ModeFrequency)ModeFrequency←runlength，modeValue←runvalue

i←i+runlength

//跳过本行程，i始终指向行程的第一个元素

return(ModeValue,ModeFrequency)预排序：模式统计（续）最差效率：预排序：模式统计（续）非行程算法（比较次数n-1）PresortMode_2(A[0...n-1])数组A排序//结果

{1,5,5,5,6,7,7}ModeFrequency←1

//模式频率

ModeValue←A[0]

//模式值for(i←0ton-2)Current_F←1//当前频率

if

A[

i

]=A[

i+1]Current_F++

if

Current_F>ModeFrequencyModeFrequency←Current_FModeValue←A[

i

]return(ModeValue,ModeFrequency)【思考】1.A元素全部唯一2.A元素全部相等预排序：模式统计（续）非行程算法（比较次数n-1）【思考】预排序：查找问题【例3】查找问题

——在n元列表中查找给定键蛮力法：顺序查找，最差情况需n次比较，O(n)变治法：预排序+折半查找，时间效率：

可见预排序比顺序查找的时间效率更差。对于在同一个列表中查找次数很少的问题，不如顺序查找。若对同一个列表需要很多次查找，效率将超过顺序查找。（分摊效率）预排序的其他应用

——许多处理点集的计算几何算法例如：点集的排序可根据它们的坐标，或者到某特定直线的距离，或者某种角度等等。如在最近对、凸包问题的分治算法中，都曾采用了预排序技术。预排序：查找问题【例3】查找问题——在n元列表中查找平衡查找树平衡查找树二叉查找树BST是一种重要的数据结构，是集合的一种描述方式。集合用BST描述是改变表现形式的一种变治技术。BST与线性表相比，查找、插入和删除操作的时间效率较好，属于logn型（平均），最坏O(n)——退化为一棵完全不平衡树（链）保持BST的好特性，避免退化的两种方案——

【实例化简】

对不平衡BST进行各种变换，重新构造平衡树。不同算法对BST的平衡要求不同。如AVL树平衡：每个节点左右子树高度差≤1.

【改变表现】BST每个节点仅允许有1个键（查找的属性）。

允许每个节点可包含不止一个键。典型例子：

2-3树、2-3-4树，更一般的B树（B+树、B*树）平衡查找树平衡查找树AVL树AVL树（1962，前苏联科学家G.M.Adelson-Velsky,E.M.Landis）AVL树是BST.树高：根到叶的最长路径的边数。设根为0层，树高=最底层编号节点平衡因子：左子树高-右子树高AVL树：每个节点的平衡因子均为0、-1、+110520427812AVL树105204278非AVL树，BSTAVL树AVL树（1962，前苏联科学家G.M.AdeAVL树的4种变换AVL树生成（插入）算法AVL树是BST，用BST插入算法生成。插入新节点后，若AVL树失去平衡，进行旋转，重新平衡它。节点有4种插入位置，对应4种旋转变换：

1.最近不平衡节点的左子树的左节点

——右单转，R旋转2.最近不平衡节点的右子树的右节点

——左单转，L旋转3.最近不平衡节点的左子树的右节点

——左右双转，LR旋转4.最近不平衡节点的右子树的左节点

——右左双转，RL旋转1R(3)32321左子树的左节点AVL树的4种变换AVL树生成（插入）算法1R(3)3232AVL树生成算法的4种旋转变换（续1）123L(1)321右子树的右节点321L(1)312左子树的右节点321R(3)AVL树生成算法的4种旋转变换（续1）123L(1)321右AVL树生成算法的4种旋转变换（续2）1右子树的左节点23R(3)132321L(1)右单转的一般情况（左子树左节点）R(w)1weT1T2T31ewT3T2T1AVL树生成算法的4种旋转变换（续2）1右子树的左节点23RAVL树生成算法的4种旋转变换（续3）wkT4T3T1eT21左右双转的一般情况（左子树右节点）（先左单转，后右单转）L(e)wkT4T3T1eT21AVL树生成算法的4种旋转变换（续3）wkT4T3T1eT2AVL树生成算法的4种旋转变换（续4）wkT4T3T1eT21wkT4T3T1eT2R(w)AVL树效率：它是BST，效率与BST一样取决于树高：AVL树缺点：频繁的旋转、维护树节点平衡，设计上较复杂，尤其是删除操作，妨碍了其应用。但蕴涵的思想使人们发现了

BST的其他变种。AVL树生成算法的4种旋转变换（续4）wkT4T3T1eT22-3树：定义2-3树——BST的变体2-3树的特性（定义）1.每个节点包含1个或2个键2.每个内部节点有2种类型：

2节点

——1个键K，2个子女

3节点

——2个键K1<K2，3个子女（键值关系如下图）3.所有叶节点在树的同一层，树高平衡2-3树的两种节点类型K＜K≥K2节点K1,K2＜K1≥K2[K1,K2)K1<K23节点2-3树：定义2-3树——BST的变体2-3树的两2-3树插入算法过程图示举例说明：2-3树生成（插入）算法的过程图示将序列{9,5,8,3,2,4,7}构造一棵2-3树95,95,8,9895893,5分裂，提升892,3,53,89253,8924,53,8924,5,783524793,5,892472-3树插入算法过程图示举例说明：2-3树生成（插入）算法2-3树插入算法2-3树插入算法（3阶B树）

——注意保持2-3树的性质1.用查找算法找到恰当的叶节点位置，插入新节点2.若插入节点溢出，分裂该节点，中间键（键值大小）加入父结点

——若父结点溢出，继续分裂父节点——若分裂过程向上传递到根节点，树加高一层2-3树查找算法（类似BST）从2-3树的根节点开始：1.查找当前节点——若找到关键码（键），查找成功返回——若未找到，且当前节点已是叶节点，查找失败返回

2.确定查找分支，转12-3树插入算法2-3树插入算法（3阶B树）2-3树删除算法2-3树删除算法——删除键而非删除节点——删除一个键时，2节点情况与BST相同。——对于3节点情况，分3种情况：1.叶节点，有2个键：删除右图“4

”键——简单删除“4”，2-3树性质不变2.叶节点，仅1个键：删除右图“2”键简单删除2，不符合2-3树性质。

若相邻兄弟无多余键（仅1个，如去掉“4”），将该相邻兄弟和父节点中、它俩的分界键并入已删除键的空节点中。

若相邻兄弟有多余键（如“4”、“5”）借码——把该兄弟的2个键和父节点中的分界键并入该空节点，再作分裂3.内部节点（非叶节点）：如删除右上图“3”键

删除仅在叶节点进行，替换后再删除替换键（图略）

替换键——比该键大的子树中的最小键3,8924,593,584,89532-3树删除算法2-3树删除算法——删除键而非删除节点2-3树的时间效率2-3树时间效率时间效率取决于树高（h），下面考察2-3树的两种极端的树高

树高：从根到叶最长路径的边数=最大层号（根为0层）2-3树全部由2节点构成：当前层节点数=2×上一层节点数一棵满的完全二叉树（n个节点，高度h），节点总数：n=20+21+22+...+2h=

2h+1–1一般的2-3树（既有2节点又有3节点），节点总数：

n≥2h+1–1即h≤log2(n+1)–12-3树全部由3节点构成：当前层节点数=3×上一层节点数

n=30+31+32+...+3h=3h+1–1一般的2-3树（既有2节点又有3节点），节点总数：

n≤3h+1–1即h≥log3(n+1)–1综合1、2：log3(n+1)–1≤h≤log2(n+1)–1

无论最差或平均情况，2-3树字典操作（插入、删除、查找）的时间效率都属于Θ(logn)型。2-3树有重要的扩展形式B、B+、B*树2-3树的时间效率2-3树时间效率堆与优先队列堆(Heap)与优先队列(Priorityqueue)堆是一种数据结构，尤其适合用来实现优先队列。优先队列——按对象的优先级属性排序的对象集合。优先队列应用例多任务操作系统对执行程序进行调度。某时刻，可能有多个程序已经准备好可以执行。当一个任务已经准备好可以执行时，被插入到优先队列。当系统允许执行新任务时，从优先队列中挑选具有最高优先级的任务执行。有些应用要求能改变对象的优先级。堆的概念堆，在逻辑上是一棵二叉树，必须满足两个条件：

1.树的形状：完全二叉树，可用数组实现（存储结构）。

2.父母优势：每个父节点值≥子节点值（即堆中元素值局部有序），本节介绍最大值堆(max-heap)。另外还有最小值堆(min-heap)，此条件刚好相反。堆与优先队列堆(Heap)与优先队列(Priorit满二叉树与完全二叉树满二叉树(FullBinaryTree)每个内部节点都有两个非空子节点。完全二叉树(CompleteBinaryTree)——从二叉树的构形判断1.最底层叶节点可以从右向左连续缺若干个，其他层必须满。

2.叶节点只可以出现在最底两层上。满二叉树，非完全完全二叉树，非满问：在逻辑上，堆为什么是一棵完全二叉树？满二叉树与完全二叉树满二叉树(FullBinaryTr完全二叉树的数组实现完全二叉树的存储结构——数组

所有节点按从上向下、从左至右存入数组。节点数一定，完全二叉树就确定了即仅一种形状。任一节点的父节点、兄弟节点、子女节点等均可由数组下标计算出来。因此，不必用指针，而用数组实现。1k=23456789101112H[k],k=0123456789101112父节点——11223344556左子节点—24681012——————右子节点—357911———————左兄弟———2—4—6—8—10—右兄弟——3—5—7—9—11——k奇数k偶数完全二叉树的数组实现完全二叉树的存储结构——数组1k=2堆与数组实现堆的存储结构（数组）10754211075411075481【判断】上面三棵树那些是堆，那些不是堆？非完全二叉树不满足父母优势

k=0123456

H[k]—10752411.树高2.H[0]为空，或放置最大限位器3.父母优势（兄弟节点没有关系）1075421堆与数组实现堆的存储结构（数组）10754211075411堆的构造算法过程图解堆的构造算法——构造一棵满足父母优势的完全二叉树值交换算法：构造列表{2,9,7,6,5,8}的堆按列表元素的顺序将列表存入数组，逻辑结构是完全二叉树。

从最后的父母节点开始，检查是否满足父母优势。若不满足，它与

最大子节点交换，继续下推至合适位置。继续检查下一个父母节点，此过程持续到根节点止。不同的值交换算法生成的堆不唯一。297568298567298567298567928567968527堆的构造算法过程图解堆的构造算法——构造一棵满足父母优值交换的堆构造算法堆构造的值交换算法//父节点i循环，最后父节点开始//不满足父母优势//满足父母优势，退出while循环//较大子节点下标→j//若有右子节点，则必有左子节点//j=2k是左子节点下标，j+1是右子节点下标//检查父母优势条件，父节点值为v//v是当前父节点值，k是它的下标//无左子节点：叶节点//不满足父母优势，值覆盖//k←j，父节点向下推后，//继续while循环//当前父节点值还原注释：父节点下推过程中值不变。把它理解为空节点，与较大子节点交换键值，直到空节点到达它的最后位置，再把抹去的值还给它。值交换的堆构造算法堆构造的值交换算法//父节点i循环，值交换的堆构造算法时间效率堆构造值交换算法的时间效率输入规模：节点数n.基本操作：键值比较效率类别：最差、最佳、平均效率。最优情况：已是最大值堆最差效率：设n=2h+1–1，满的完全二叉树，h为最大层号（根为0）下层节点数=上层节点数×2,h=log2(n+1)–1.最坏情况是最小值堆——每个父母节点都要下推至叶节点。每次下推，都要作两次比较：1.左右子节点比较，找较大者；2.父子比较确定当前父节点是否下推。第k层上的父节点，需作2×(h–k)次比较。k=0→h需要下推h–1层，总比较次数：结论：构造规模为n的堆，少于2n次比较即可完成。思考：2k项何意？值交换的堆构造算法时间效率堆构造值交换算法的时间效率结论：构堆构造的插入算法堆构造的插入算法（效率较差）

算法策略：把元素（节点）一个接一个地插入堆中。

算法步骤：如图，插入键值=10的一个节点1.把节点值V=10插入堆的末尾（最后叶节点，数组末尾）

2.V在堆中的位置可能不正确，需要上推到合适位置：（1）若V≤父母，满足父母优势条件，位置合适；（2）若V＞父母，则交换它们。然后，与其新父母比较。此过程一直持续到满足条件（1）或将它上推至根节点为止。

算法效率：最坏情况，插入键值从堆底层上推至根，比较次数等于堆的高度约log2n，插入n个元素的最差时间效率为

nlogn型。968527109610527810695278堆构造的插入算法堆构造的插入算法（效率较差）96852710堆的删除算法堆的删除算法：删除根键（最大值）【思考题】删除任意键情况

算法步骤：1.把堆的最后一个叶节点键值（数组最后一个元素）与根键值交换，该节点代替了原来的根节点，成为新的根节点。删除了一个元素，堆的规模减1。问：为什么选最后一个节点，而不选根的子节点？

答：删除最后一个节点，不影响完全二叉树的性质。

2.新根节点的键值可能不满足父母优势条件，用下推算法，将它下推到堆中的正确位置。

算法效率：最坏情况，新根键要下推至最底层的叶节点上。键值比较次数为树高，因此效率属于logn型。986521186529816529856129堆的删除算法堆的删除算法：删除根键（最大值）【思考题】删除堆排序（堆分类）堆排序（heapsort）或称堆分类堆的数组实现，空间利用率很高（无指针的结构性开销），平均情况下比快速排序慢常数因子，适合于外排序（使用外存），处理大数据集。两步算法（在位算法，得非降序的有序列表）1.构造堆：对给定n个元素构造一个max-heap（规模n）2.删除根键：对删除后的新堆（规模n-1）执行n–1次根删除操作，一共执行n次根删除，共删除n个元素按照根键的删除顺序，可得n元素的非升序列表，完成排序。解释：结果数组是元素的非降序排列根键删除是把堆顶元素（值最大）与数组的最后一个元素交换，然后，对剩下元素再构造堆，再删除根键，……，如此继续，直到堆空为止。结束时，原数组元素经过重排位置，得到的是一个非降序的数组。下图，用数组形式表示堆排序过程。堆排序（堆分类）堆排序（heapsort）或称堆分类数组描述堆排序过程数组

H[k]描述堆排序过程（构造堆+删除根键）297568完全二叉树的数组H[k]={2,9,7,6,5,8}—————0752869756829756892756892856792H[k]654321k=内部节点叶节点第1步：构造堆（值交换算法）968275第2步：删除根键过程987652—987652—987625—987625—987526—987562——————0982567982765952768952867752869H[k]654321k=结果数组为升序数组描述堆排序过程数组H[k]描述堆排序过程（构造堆问题化简问题化简问题化简策略数学家的笑话X教授是一个著名数学家，他注意到每当他妻子烧开水泡茶时，先把水壶从厨柜里拿出来，装上水后放在炉子上。一次，他妻子外出了，他只能自己烧开水。他看到水壶已经在炉台上，X教授怎么做呢？

做法：先把水壶放进橱柜里，然后，遵循他妻子的烧开水程序。策略：把问题转化为另一个算法已知的问题。问题化简策略问题1问题2问题2的解待解问题已知求解算法A化简算法A【关键】如何转化为问题2，以化简原问题问题化简问题化简问题1问题2问题2的解待解问题已知求解算法问题化简：解析几何问题化简：解析几何解析几何的一个实例若平面上三个点按逆时针编号为

——面积行列式的值大于0.

化简：把三个点的相对位置几何关系转化为关于行列式符号的问题。解析几何的思想基础就是把几何问题化简为代数问题求解。解析几何是问题化简策略的一个大的应用领域。

本节将给出基于问题化简策略的几个实例。问题化简：解析几何问题化简：解析几何问题化简：求最小公倍数问题化简：求最小公倍数最小公倍数：lcm(m,n)能被m、n整除的最小整数。例如：lcm(24,60)=120经典算法

1.找出m、n的全部质因数（质因数分解式，第1章）2.把m、n所有公共质因数相乘（公共质因数限乘1次）3.公共质因数的积再乘以m和n的非公共质因数

【例】求lcm(24,60)=？

lcm(24,60)=2×2×3×2×5=120问题化简：避免求质因数，将此问题转化为另一个问题求解。观察gcd(24,60)=2×2×3与lcm(24,60)发现：24×60=(2×2×3)×(2×2×3)×2×5=gcd(24,60)×lcm(24,60)

gcd(m,n)用高效的欧氏算法求出。24=

2×2×2×3，60=2×2×3×5问题化简：求最小公倍数问题化简：求最小公倍数24=2×问题化简：计算图的路径数问题化简：最优化问题最大值问题：求目标函数的最大值Maxf(x)最小值问题：求目标函数的最小值Minf(x)若具体问题为最大值问题，已知最小值问题的解法，如何设计最大值问题的解法呢？——最优化理论书籍讨论的是最小化问题解法问题化简：问题化简：计算图的路径数问题化简：最优化问题问题化简：线性规划问题问题化简：线性规划问题（最优化问题之一）数学建模——将问题用数学模型描述，采用已知的数学解法求解【例1】投资问题→收益最大化某基金需要投资1亿美元，分3种类型投资：股票、债券、现金。

年收益：股票10％，债券7％，现金3％.考虑到股票比债券风险高，

故要求股票投资不超过债券投资的1/3.还要求现金投资不低于股票

和债券投资总额的25％

.

问题：如何投资？（投资种类的额度）

建模：设x、y、z分别为股票、债券、现金的投资额度（百万）

目标函数

maxf(x)=0.10x+0.07y+0.03z（线性规划）

约束条件

x+y+z=100（等式约束）x≤y/3（不等式约束）z≥0.25(x+y)x＞0,y＞0,z＞0（变量的部分定义域）解法：单纯形法是最著名的求解算法。如果限定变量只能取整数时，成为整数规划问题，求解难度较大。问题化简：线性规划问题问题化简：线性规划问题（最优化问题问题化简：数学建模（续）【例2】背包问题化简为线性规划问题背包问题：给定承重W的背包，n个重量为w1...wn、价值v1...vn的物品。求：能装入背包中的最有价值的子集1.连续背包——物品可按任意比例拆分，物品价值与其重量成正比设实变量xk(0≤xk≤1)表示物品k(k=1,...,n)放入背包的比例系数目标函数：约束条件：2.离散背包（0-1背包）——物品不能被拆分整数规划问题。似乎更简单，实际上比连续问题的求解复杂得多。对于本例的特殊整数规划问题，可用特定算法求解。——所选物品的总价值——所选物品的总重量问题化简：数学建模（续）【例2】背包问题化简为线性规划问问题化简：状态空间图问题化简：状态空间图问题的求解过程用图描述，相应地用图算法求解问题。状态空间图：反映了问题的求解过程（状态变化）。

顶点：描述问题当时的状态。一个顶点表示一个状态。

——初始状态和目标状态都是一个顶点

边：描述状态之间的转变，一条边表示一次转变。状态参数：描述状态的参数，它的变化引起状态变化。如：水温和气压，描述水的三态（液态、气态、故态）如：棋子在棋盘上的行列坐标值，描述棋局状态。

每走动一个棋子，当前棋局状态就发生一次变化。如：人在迷宫格的横竖坐标值，描述迷宫状态。

人每走一格，当前迷宫状态就发生一次变化。问题化简：化为计算初始状态到目标状态之间的路径问题。（给定初始状态，目标状态可能不止一个）问题化简：状态空间图问题化简：状态空间图6.1——1,3,46.3——2,4,5,86.4——1,56.1——1,3,4第6章变治法变治策略预排序平衡查找树

AVL树2-3树（扩展B、B+、B*树）堆与优先队列堆排序（堆分类）问题化简本章习题第6章变治法变治策略第6章变治法变治策略预排序平衡查找树

AVL树2-3树（扩展B、B+、B*树）堆与优先队列堆排序（堆分类）问题化简本章习题第6章变治法变治策略第6章变治法变治策略预排序平衡查找树

AVL树2-3树（扩展B、B+、B*树）堆与优先队列堆排序（堆分类）问题化简本章习题第6章变治法变治策略变治策略变治策略通用的算法设计方法，基于变换的思想变：变换问题更容易求解治：对变换后的问题求解3种主要类型实例化简：问题求解变得更简单，如预排序改变表现：改变问题的表现形式，如AVL树，2-3树，堆问题化简：问题变为另一个问题。如数学建模，将具体应用问题用变量、函数、方程等数学对象表达求解问题更简单方便另一种表现另一个问题变治策略变治策略求解问题更简单方便预排序：元素唯一性检验预排序古老思想：若列表有序，一些与列表有关的问题更容易求解。

——依赖于排序算法的时间效率【例1】检验数组中元素的唯一性蛮力：逐个比较数组元素，直到找到两个相等元素或全部元素比较完毕为止。时间效率O

(n2)变治：预排序化简问题后求解。即：数组排序后检查连续元素。排序后等值元素（重复元素）一定相邻

算法

PresortElementUniqueness

(A[0...n-1])

对数组A排序//选nlogn型算法

fori←0ton-2do

if

A[i]=A[i+1]

returnfalse

returntrue预排序：元素唯一性检验预排序预排序：模式统计【例2】模式统计模式：列表中出现频率最高的元素。如{5,1,5,7,6,5,7}的模式为5，模式可能不止一个

问题：在列表中找出模式

蛮力策略：扫描列表，统计每个元素的频率，找出频率最高的元素

蛮力实现：（方法之一）设一个辅助列表，扫描元素与辅助列表中的元素一一比较，结果：若匹配（辅助列表中已有），该元素频率加1.不匹配（辅助列表中没有），新元素加入辅助列表，其频率置1.本例最终的辅助列表：{5(3),1(1),7(2),6(1)}括号内为频率。——扫描辅助列表，找出最大频率（3）的元素（5）

最坏情况：扫描原始列表时，每个元素在辅助列表中都没有匹配，作为新元素加入辅助列表，原列表的第k个元素加入辅助列表时，需要与辅助列表中已加入的k-1个元素比较，共k-1次。预排序：模式统计【例2】模式统计预排序：模式统计（续）

最差效率：

变治法——预排序（nlogn型），排序后等值元素一定相邻

扫描统计：模式具有最多的相邻元素，需比较

n

-1次。PresortMode_1(A[0...n-1])//行程算法

对数组A排序//排序结果{1,5,5,5,6,7,7}i←0，ModeFrequency←0

//最大频率，最大行程长度

while(i≤n-1)

runlength←1，runvalue←A[i]

//行程长度=等值元素个数

while(i+runlength≤n-1and

A[i+runlength]=runvalue

)runlength++//与下一个元素相等则行程长度+1

if(runlength>ModeFrequency)ModeFrequency←runlength，modeValue←runvalue

i←i+runlength

//跳过本行程，i始终指向行程的第一个元素

return(ModeValue,ModeFrequency)预排序：模式统计（续）最差效率：预排序：模式统计（续）非行程算法（比较次数n-1）PresortMode_2(A[0...n-1])数组A排序//结果

{1,5,5,5,6,7,7}ModeFrequency←1

//模式频率

ModeValue←A[0]

//模式值for(i←0ton-2)Current_F←1//当前频率

if

A[

i

]=A[

i+1]Current_F++

if

Current_F>ModeFrequencyModeFrequency←Current_FModeValue←A[

i

]return(ModeValue,ModeFrequency)【思考】1.A元素全部唯一2.A元素全部相等预排序：模式统计（续）非行程算法（比较次数n-1）【思考】预排序：查找问题【例3】查找问题

——在n元列表中查找给定键蛮力法：顺序查找，最差情况需n次比较，O(n)变治法：预排序+折半查找，时间效率：

可见预排序比顺序查找的时间效率更差。对于在同一个列表中查找次数很少的问题，不如顺序查找。若对同一个列表需要很多次查找，效率将超过顺序查找。（分摊效率）预排序的其他应用

——许多处理点集的计算几何算法例如：点集的排序可根据它们的坐标，或者到某特定直线的距离，或者某种角度等等。如在最近对、凸包问题的分治算法中，都曾采用了预排序技术。预排序：查找问题【例3】查找问题——在n元列表中查找平衡查找树平衡查找树二叉查找树BST是一种重要的数据结构，是集合的一种描述方式。集合用BST描述是改变表现形式的一种变治技术。BST与线性表相比，查找、插入和删除操作的时间效率较好，属于logn型（平均），最坏O(n)——退化为一棵完全不平衡树（链）保持BST的好特性，避免退化的两种方案——

【实例化简】

对不平衡BST进行各种变换，重新构造平衡树。不同算法对BST的平衡要求不同。如AVL树平衡：每个节点左右子树高度差≤1.

【改变表现】BST每个节点仅允许有1个键（查找的属性）。

允许每个节点可包含不止一个键。典型例子：

2-3树、2-3-4树，更一般的B树（B+树、B*树）平衡查找树平衡查找树AVL树AVL树（1962，前苏联科学家G.M.Adelson-Velsky,E.M.Landis）AVL树是BST.树高：根到叶的最长路径的边数。设根为0层，树高=最底层编号节点平衡因子：左子树高-右子树高AVL树：每个节点的平衡因子均为0、-1、+110520427812AVL树105204278非AVL树，BSTAVL树AVL树（1962，前苏联科学家G.M.AdeAVL树的4种变换AVL树生成（插入）算法AVL树是BST，用BST插入算法生成。插入新节点后，若AVL树失去平衡，进行旋转，重新平衡它。节点有4种插入位置，对应4种旋转变换：

1.最近不平衡节点的左子树的左节点

——右单转，R旋转2.最近不平衡节点的右子树的右节点

——左单转，L旋转3.最近不平衡节点的左子树的右节点

——左右双转，LR旋转4.最近不平衡节点的右子树的左节点

——右左双转，RL旋转1R(3)32321左子树的左节点AVL树的4种变换AVL树生成（插入）算法1R(3)3232AVL树生成算法的4种旋转变换（续1）123L(1)321右子树的右节点321L(1)312左子树的右节点321R(3)AVL树生成算法的4种旋转变换（续1）123L(1)321右AVL树生成算法的4种旋转变换（续2）1右子树的左节点23R(3)132321L(1)右单转的一般情况（左子树左节点）R(w)1weT1T2T31ewT3T2T1AVL树生成算法的4种旋转变换（续2）1右子树的左节点23RAVL树生成算法的4种旋转变换（续3）wkT4T3T1eT21左右双转的一般情况（左子树右节点）（先左单转，后右单转）L(e)wkT4T3T1eT21AVL树生成算法的4种旋转变换（续3）wkT4T3T1eT2AVL树生成算法的4种旋转变换（续4）wkT4T3T1eT21wkT4T3T1eT2R(w)AVL树效率：它是BST，效率与BST一样取决于树高：AVL树缺点：频繁的旋转、维护树节点平衡，设计上较复杂，尤其是删除操作，妨碍了其应用。但蕴涵的思想使人们发现了

BST的其他变种。AVL树生成算法的4种旋转变换（续4）wkT4T3T1eT22-3树：定义2-3树——BST的变体2-3树的特性（定义）1.每个节点包含1个或2个键2.每个内部节点有2种类型：

2节点

——1个键K，2个子女

3节点

——2个键K1<K2，3个子女（键值关系如下图）3.所有叶节点在树的同一层，树高平衡2-3树的两种节点类型K＜K≥K2节点K1,K2＜K1≥K2[K1,K2)K1<K23节点2-3树：定义2-3树——BST的变体2-3树的两2-3树插入算法过程图示举例说明：2-3树生成（插入）算法的过程图示将序列{9,5,8,3,2,4,7}构造一棵2-3树95,95,8,9895893,5分裂，提升892,3,53,89253,8924,53,8924,5,783524793,5,892472-3树插入算法过程图示举例说明：2-3树生成（插入）算法2-3树插入算法2-3树插入算法（3阶B树）

——注意保持2-3树的性质1.用查找算法找到恰当的叶节点位置，插入新节点2.若插入节点溢出，分裂该节点，中间键（键值大小）加入父结点

——若父结点溢出，继续分裂父节点——若分裂过程向上传递到根节点，树加高一层2-3树查找算法（类似BST）从2-3树的根节点开始：1.查找当前节点——若找到关键码（键），查找成功返回——若未找到，且当前节点已是叶节点，查找失败返回

2.确定查找分支，转12-3树插入算法2-3树插入算法（3阶B树）2-3树删除算法2-3树删除算法——删除键而非删除节点——删除一个键时，2节点情况与BST相同。——对于3节点情况，分3种情况：1.叶节点，有2个键：删除右图“4

”键——简单删除“4”，2-3树性质不变2.叶节点，仅1个键：删除右图“2”键简单删除2，不符合2-3树性质。

若相邻兄弟无多余键（仅1个，如去掉“4”），将该相邻兄弟和父节点中、它俩的分界键并入已删除键的空节点中。

若相邻兄弟有多余键（如“4”、“5”）借码——把该兄弟的2个键和父节点中的分界键并入该空节点，再作分裂3.内部节点（非叶节点）：如删除右上图“3”键

删除仅在叶节点进行，替换后再删除替换键（图略）

替换键——比该键大的子树中的最小键3,8924,593,584,89532-3树删除算法2-3树删除算法——删除键而非删除节点2-3树的时间效率2-3树时间效率时间效率取决于树高（h），下面考察2-3树的两种极端的树高

树高：从根到叶最长路径的边数=最大层号（根为0层）2-3树全部由2节点构成：当前层节点数=2×上一层节点数一棵满的完全二叉树（n个节点，高度h），节点总数：n=20+21+22+...+2h=

2h+1–1一般的2-3树（既有2节点又有3节点），节点总数：

n≥2h+1–1即h≤log2(n+1)–12-3树全部由3节点构成：当前层节点数=3×上一层节点数

n=30+31+32+...+3h=3h+1–1一般的2-3树（既有2节点又有3节点），节点总数：

n≤3h+1–1即h≥log3(n+1)–1综合1、2：log3(n+1)–1≤h≤log2(n+1)–1

无论最差或平均情况，2-3树字典操作（插入、删除、查找）的时间效率都属于Θ(logn)型。2-3树有重要的扩展形式B、B+、B*树2-3树的时间效率2-3树时间效率堆与优先队列堆(Heap)与优先队列(Priorityqueue)堆是一种数据结构，尤其适合用来实现优先队列。优先队列——按对象的优先级属性排序的对象集合。优先队列应用例多任务操作系统对执行程序进行调度。某时刻，可能有多个程序已经准备好可以执行。当一个任务已经准备好可以执行时，被插入到优先队列。当系统允许执行新任务时，从优先队列中挑选具有最高优先级的任务执行。有些应用要求能改变对象的优先级。堆的概念堆，在逻辑上是一棵二叉树，必须满足两个条件：

1.树的形状：完全二叉树，可用数组实现（存储结构）。

2.父母优势：每个父节点值≥子节点值（即堆中元素值局部有序），本节介绍最大值堆(max-heap)。另外还有最小值堆(min-heap)，此条件刚好相反。堆与优先队列堆(Heap)与优先队列(Priorit满二叉树与完全二叉树满二叉树(FullBinaryTree)每个内部节点都有两个非空子节点。完全二叉树(CompleteBinaryTree)——从二叉树的构形判断1.最底层叶节点可以从右向左连续缺若干个，其他层必须满。

2.叶节点只可以出现在最底两层上。满二叉树，非完全完全二叉树，非满问：在逻辑上，堆为什么是一棵完全二叉树？满二叉树与完全二叉树满二叉树(FullBinaryTr完全二叉树的数组实现完全二叉树的存储结构——数组

所有节点按从上向下、从左至右存入数组。节点数一定，完全二叉树就确定了即仅一种形状。任一节点的父节点、兄弟节点、子女节点等均可由数组下标计算出来。因此，不必用指针，而用数组实现。1k=23456789101112H[k],k=0123456789101112父节点——11223344556左子节点—24681012——————右子节点—357911———————左兄弟———2—4—6—8—10—右兄弟——3—5—7—9—11——k奇数k偶数完全二叉树的数组实现完全二叉树的存储结构——数组1k=2堆与数组实现堆的存储结构（数组）10754211075411075481【判断】上面三棵树那些是堆，那些不是堆？非完全二叉树不满足父母优势

k=0123456

H[k]—10752411.树高2.H[0]为空，或放置最大限位器3.父母优势（兄弟节点没有关系）1075421堆与数组实现堆的存储结构（数组）10754211075411堆的构造算法过程图解堆的构造算法——构造一棵满足父母优势的完全二叉树值交换算法：构造列表{2,9,7,6,5,8}的堆按列表元素的顺序将列表存入数组，逻辑结构是完全二叉树。

从最后的父母节点开始，检查是否满足父母优势。若不满足，它与

最大子节点交换，继续下推至合适位置。继续检查下一个父母节点，此过程持续到根节点止。不同的值交换算法生成的堆不唯一。297568298567298567298567928567968527堆的构造算法过程图解堆的构造算法——构造一棵满足父母优值交换的堆构造算法堆构造的值交换算法//父节点i循环，最后父节点开始//不满足父母优势//满足父母优势，退出while循环//较大子节点下标→j//若有右子节点，则必有左子节点//j=2k是左子节点下标，j+1是右子节点下标//检查父母优势条件，父节点值为v//v是当前父节点值，k是它的下标//无左子节点：叶节点//不满足父母优势，值覆盖//k←j，父节点向下推后，//继续while循环//当前父节点值还原注释：父节点下推过程中值不变。把它理解为空节点，与较大子节点交换键值，直到空节点到达它的最后位置，再把抹去的值还给它。值交换的堆构造算法堆构造的值交换算法//父节点i循环，值交换的堆构造算法时间效率堆构造值交换算法的时间效率输入规模：节点数n.基本操作：键值比较效率类别：最差、最佳、平均效率。最优情况：已是最大值堆最差效率：设n=2h+1–1，满的完全二叉树，h为最大层号（根为0）下层节点数=上层节点数×2,h=log2(n+1)–1.最坏情况是最小值堆——每个父母节点都要下推至叶节点。每次下推，都要作两次比较：1.左右子节点比较，找较大者；2.父子比较确定当前父节点是否下推。第k层上的父节点，需作2×(h–k)次比较。k=0→h需要下推h–1层，总比较次数：结论：构造规模为n的堆，少于2n次比较即可完成。思考：2k项何意？值交换的堆构造算法时间效率堆构造值交换算法的时间效率结论：构堆构造的插入算法堆构造的插入算法（效率较差）

算法策略：把元素（节点）一个接一个地插入堆中。

算法步骤：如图，插入键值=10的一个节点1.把节点值V=10插入堆的末尾（最后叶节点，数组末尾）

2.V在堆中的位置可能不正确，需要上推到合适位置：（1）若V≤父母，满足父母优势条件，位置合适；（2）若V＞父母，则交换它们。然后，与其新父母比较。此过程一直持续到满足条件（1）或将它上推至根节点为止。

算法效率：最坏情况，插入键值从堆底层上推至根，比较次数等于堆的高度约log2n，插入n个元素的最差时间效率为

nlogn型。968527109610527810695278堆构造的插入算法堆构造的插入算法（效率较差）96852710堆的删除算法堆的删除算法：删除根键（最大值）【思考题】删除任意键情况

算法步骤：1.把堆的最后一个叶节点键值（数组最后一个元素）与根键值交换，该节点代替了原来的根节点，成为新的根节点。删除了一个元素，堆的规模减1。问：为什么选最后一个节点，而不选根的子节点？

答：删除最后一个节点，不影响完全二叉树的性质。

2.新根节点的键值可能不满足父母优势条件，用下推算法，将它下推到堆中的正确位置。

算法效率：最坏情况，新根键要下推至最底层的叶节点上。键值比较次数为树高，因此效率属于logn型。986521186529816529856129堆的删除算法堆的删除算法：删除根键（最大值）【思考题】删除堆排序（堆分类）堆排序（heapsort）或称堆分类堆的数组实现，空间利用率很高（无指针的结构性开销），平均情况下比快速排序慢常数因子，适合于外排序（使用外存），处理大数据集。两步算法（在位算法，得非降序的有序列表）1.构造堆：对给定n个元素构造一个max-heap（规模n）2.删除根键：对删除后的新堆（规模n-1）执行n–1次根删除操作，一共执行n次根删除，共删除n个元素按照根键的删除顺序，可得n元素的非升序列表，完成排序。解释：结果数组是元素的非降序排列根键删除是把堆顶元素（值最大）与数组的最后一个元素交换，然后，对剩下元素再构造堆，再删除根键，……，如此继续，直到堆空为止。结束时，原数组元素经过重排位置，得到的是一个非降序的数组。下图，用数组形式表示堆排序过程。堆排序（堆分类）堆排序（heapsort）或称堆分类数组描述堆排序过程数组

H[k]描述堆排序过程（构造堆+删除根键）297568完全二叉树的数组H[k]={2,9,7,6,5,8}—————0752869756829756892756892856792H[k]654321k=内部节点叶节点第1步：构造堆（值交换算法）968275第2步：删除根键过程987652—987652—987625—987625—987526—987562——————0982567982765952768952867752869H[k]654321k=结果数组为升序数组描述堆排序过程数组H[k]描述堆排序过程（构造堆问题化简问题化简问题化简策略数学家的笑话X教授是一个著名数学家，他注意到每当他妻子烧开水泡茶时，先把水壶从厨柜里拿出来，装上水后放在炉子上。一次，他妻子外出了，他只能自己烧开水。他看到水壶已经在炉台上，X教授怎么做呢？

做法：先把水壶放进橱柜里，然后，遵循他妻子的烧开水程序。策略：把问题转化为另一个算法已知的问题。问题化简策略