算法设计与分析课件

第第 6 章章 变治法变治法 变治策略变治策略变治策略变治策略 预排序预排序预排序预排序 平衡查找树平衡查找树平衡查找树平衡查找树 AVLAVL树树树树 2-3 2-3树（扩展树（扩展树（扩展树（扩展B B、B B+、B*B*树）树）树）树）堆与优先队列堆与优先队列堆与优先队列堆与优先队列 堆排序（堆分类）堆排序（堆分类）堆排序（堆分类）堆排序（堆分类）问题化简问题化简问题化简问题化简 本章习题本章习题本章习题本章习题第第 6 章章 变治法变治法 变治策略变治策略第第 6 章章 变治法变治法 变治策略变治策略变治策略变治策略 预排序预排序预排序预排序 平衡查找树平衡查找树平衡查找树平衡查找树 AVLAVL树树树树 2-3 2-3树（扩展树（扩展树（扩展树（扩展B B、B B+、B*B*树）树）树）树）堆与优先队列堆与优先队列堆与优先队列堆与优先队列 堆排序（堆分类）堆排序（堆分类）堆排序（堆分类）堆排序（堆分类）问题化简问题化简问题化简问题化简 本章习题本章习题本章习题本章习题第第 6 章章 变治法变治法 变治策略变治策略第第 6 章章 变治法变治法 变治策略变治策略变治策略变治策略 预排序预排序预排序预排序 平衡查找树平衡查找树平衡查找树平衡查找树 AVLAVL树树树树 2-3 2-3树（扩展树（扩展树（扩展树（扩展B B、B B+、B*B*树）树）树）树）堆与优先队列堆与优先队列堆与优先队列堆与优先队列 堆排序（堆分类）堆排序（堆分类）堆排序（堆分类）堆排序（堆分类）问题化简问题化简问题化简问题化简 本章习题本章习题本章习题本章习题第第 6 章章 变治法变治法 变治策略变治策略变治策略 变治策略变治策略变治策略变治策略 通用的算法设计方法，基于变换的思想通用的算法设计方法，基于变换的思想通用的算法设计方法，基于变换的思想通用的算法设计方法，基于变换的思想变：变换问题更容易求解变：变换问题更容易求解变：变换问题更容易求解变：变换问题更容易求解治：对变换后的问题求解治：对变换后的问题求解治：对变换后的问题求解治：对变换后的问题求解 3 3 种主要类型种主要类型种主要类型种主要类型实例化简：问题求解变得更简单，如预排序实例化简：问题求解变得更简单，如预排序实例化简：问题求解变得更简单，如预排序实例化简：问题求解变得更简单，如预排序改变表现：改变问题的表现形式，如改变表现：改变问题的表现形式，如改变表现：改变问题的表现形式，如改变表现：改变问题的表现形式，如AVLAVL树，树，树，树，2-32-3树，堆树，堆树，堆树，堆问题化简：问题变为另一个问题。如数学建模，将具体应用问题用问题化简：问题变为另一个问题。如数学建模，将具体应用问题用问题化简：问题变为另一个问题。如数学建模，将具体应用问题用问题化简：问题变为另一个问题。如数学建模，将具体应用问题用 变量、函数、方程等数学对象表达变量、函数、方程等数学对象表达变量、函数、方程等数学对象表达变量、函数、方程等数学对象表达求解求解求解求解问题问题问题问题更简单方便更简单方便更简单方便更简单方便另一种表现另一种表现另一种表现另一种表现另一个问题另一个问题另一个问题另一个问题变治策略变治策略 变治策略求解问题更简单方便变治策略求解问题更简单方便预排序：元素唯一性检验 预排序预排序预排序预排序古老思想：古老思想：古老思想：古老思想：若列表有序，一些与列表有关的问题更容易求解。若列表有序，一些与列表有关的问题更容易求解。若列表有序，一些与列表有关的问题更容易求解。若列表有序，一些与列表有关的问题更容易求解。依赖于排序算法的时间效率依赖于排序算法的时间效率依赖于排序算法的时间效率依赖于排序算法的时间效率【例【例【例【例1 1 1 1】检验数组中元素的唯一性】检验数组中元素的唯一性】检验数组中元素的唯一性】检验数组中元素的唯一性 蛮力：逐个比较数组元素，直到找到两个相等元素或全部元素比较蛮力：逐个比较数组元素，直到找到两个相等元素或全部元素比较蛮力：逐个比较数组元素，直到找到两个相等元素或全部元素比较蛮力：逐个比较数组元素，直到找到两个相等元素或全部元素比较 完毕为止。时间效率完毕为止。时间效率完毕为止。时间效率完毕为止。时间效率 OO (n(n2 2)变治：预排序化简问题后求解。即：数组排序后检查连续元素。变治：预排序化简问题后求解。即：数组排序后检查连续元素。变治：预排序化简问题后求解。即：数组排序后检查连续元素。变治：预排序化简问题后求解。即：数组排序后检查连续元素。排序后等值元素（重复元素）一定相邻排序后等值元素（重复元素）一定相邻排序后等值元素（重复元素）一定相邻排序后等值元素（重复元素）一定相邻 算法算法算法算法 PresortElementUniquenessPresortElementUniqueness (A0.n-1A0.n-1)对数组对数组对数组对数组A A排序排序排序排序 /选选选选nlognnlogn型算法型算法型算法型算法 forfor i0 i0 toto n-2 n-2 do do if if Ai=Ai+1 Ai=Ai+1 returnreturn false false returnreturn true true预排序：元素唯一性检验预排序：元素唯一性检验 预排序预排序预排序：模式统计【例【例【例【例2 2 2 2】模式统计】模式统计】模式统计】模式统计 模式：列表中出现频率最高的元素。模式：列表中出现频率最高的元素。模式：列表中出现频率最高的元素。模式：列表中出现频率最高的元素。如如如如 5,1,5,7,6,5,7 5,1,5,7,6,5,7 的模式为的模式为的模式为的模式为 5 5，模式可能不止一个，模式可能不止一个，模式可能不止一个，模式可能不止一个 问题：在列表中找出模式问题：在列表中找出模式问题：在列表中找出模式问题：在列表中找出模式 蛮力策略：蛮力策略：蛮力策略：蛮力策略：扫描列表，统计每个元素的频率，找出频率最高的元素扫描列表，统计每个元素的频率，找出频率最高的元素扫描列表，统计每个元素的频率，找出频率最高的元素扫描列表，统计每个元素的频率，找出频率最高的元素 蛮力实现：（方法之一）蛮力实现：（方法之一）蛮力实现：（方法之一）蛮力实现：（方法之一）设一个设一个设一个设一个辅助列表，辅助列表，辅助列表，辅助列表，扫描元素与辅助列表中的元素一一比较，结果：扫描元素与辅助列表中的元素一一比较，结果：扫描元素与辅助列表中的元素一一比较，结果：扫描元素与辅助列表中的元素一一比较，结果：若匹配（辅助列表中已有），该元素频率加若匹配（辅助列表中已有），该元素频率加若匹配（辅助列表中已有），该元素频率加若匹配（辅助列表中已有），该元素频率加1.1.不匹配（辅助列表中没有），新元素加入辅助列表，其频率置不匹配（辅助列表中没有），新元素加入辅助列表，其频率置不匹配（辅助列表中没有），新元素加入辅助列表，其频率置不匹配（辅助列表中没有），新元素加入辅助列表，其频率置1.1.本例最终的辅助列表：本例最终的辅助列表：本例最终的辅助列表：本例最终的辅助列表：5(3),1(1),7(2),6(1)5(3),1(1),7(2),6(1)括号内为频率。括号内为频率。括号内为频率。括号内为频率。扫描辅助列表，找出最大频率（扫描辅助列表，找出最大频率（扫描辅助列表，找出最大频率（扫描辅助列表，找出最大频率（3 3）的元素（）的元素（）的元素（）的元素（5 5）最坏情况：最坏情况：最坏情况：最坏情况：扫描原始列表时，扫描原始列表时，扫描原始列表时，扫描原始列表时，每个元素在辅助列表中都没有匹配每个元素在辅助列表中都没有匹配每个元素在辅助列表中都没有匹配每个元素在辅助列表中都没有匹配，作为新元素加入辅助列表，原列表的第作为新元素加入辅助列表，原列表的第作为新元素加入辅助列表，原列表的第作为新元素加入辅助列表，原列表的第 k k 个元素加入辅助列表时，个元素加入辅助列表时，个元素加入辅助列表时，个元素加入辅助列表时，需要与辅助列表中已加入的需要与辅助列表中已加入的需要与辅助列表中已加入的需要与辅助列表中已加入的 k-1 k-1个元素比较，共个元素比较，共个元素比较，共个元素比较，共 k-1 k-1 次。次。次。次。预排序：模式统计【例预排序：模式统计【例2】模式统计】模式统计预排序：模式统计（续）最差效率：最差效率：最差效率：最差效率：变治法变治法变治法变治法 预排序（预排序（预排序（预排序（nlognnlogn型），型），型），型），排序后排序后排序后排序后 等值元素一定相邻等值元素一定相邻等值元素一定相邻等值元素一定相邻 扫描统计：模式具有最多的相邻元素，需比较扫描统计：模式具有最多的相邻元素，需比较扫描统计：模式具有最多的相邻元素，需比较扫描统计：模式具有最多的相邻元素，需比较 n n -1-1 次。次。次。次。PresortMode_1(PresortMode_1(A0.n-1A0.n-1)/行程算法行程算法行程算法行程算法 对数组对数组对数组对数组A A排序排序排序排序 /排序结果排序结果排序结果排序结果 1,1,5,5,55,5,5,6,6,7,77,7 i0 i0，ModeFrequencyModeFrequency0 0 /最大频率，最大行程长度最大频率，最大行程长度最大频率，最大行程长度最大频率，最大行程长度 whilewhile(in-1)(in-1)runlength1runlength1，runvalueAi runvalueAi /行程长度行程长度行程长度行程长度=等值元素个数等值元素个数等值元素个数等值元素个数 whilewhile(i+runlengthn-1 (i+runlengthn-1 andand Ai+runlength=runvalueAi+runlength=runvalue )runlength+runlength+/与下一个元素相等则行程长度与下一个元素相等则行程长度与下一个元素相等则行程长度与下一个元素相等则行程长度+1+1 if if(runlength ModeFrequency)(runlength ModeFrequency)ModeFrequencyrunlength ModeFrequencyrunlength，modeValuerunvaluemodeValuerunvalue ii+runlengthii+runlength /跳过本行程，跳过本行程，跳过本行程，跳过本行程，i i 始终指向行程的第一个元素始终指向行程的第一个元素始终指向行程的第一个元素始终指向行程的第一个元素 returnreturn(ModeValue,ModeFrequency)(ModeValue,ModeFrequency)预排序：模式统计（续）预排序：模式统计（续）最差效率：最差效率：预排序：模式统计（续）非行程算法非行程算法非行程算法非行程算法（比较次数（比较次数（比较次数（比较次数 n-1n-1）PresortMode_2(PresortMode_2(A0.n-1A0.n-1)数组数组数组数组A A排序排序排序排序 /结果结果结果结果 1,1,5,5,55,5,5,6,6,7,77,7 ModeFrequency ModeFrequency1 1 /模式频率模式频率模式频率模式频率 ModeValueA0 ModeValueA0 /模式值模式值模式值模式值 for for(i0 (i0 toto n-2)n-2)Current_F Current_F1 1 /当前频率当前频率当前频率当前频率 if if AA i i =A=A i+1i+1 Current_F+Current_F+if if Current_F ModeFrequencyCurrent_F ModeFrequency ModeFrequency Current_F ModeFrequency Current_F ModeValue A ModeValue A i i return return(ModeValue,ModeFrequency)(ModeValue,ModeFrequency)【思考】【思考】【思考】【思考】1.A 1.A 元素全部唯一元素全部唯一元素全部唯一元素全部唯一 2.A 2.A 元素全部相等元素全部相等元素全部相等元素全部相等预排序：模式统计（续）非行程算法（比较次数预排序：模式统计（续）非行程算法（比较次数 n-1）【思考】）【思考】预排序：查找问题【例【例【例【例3 3 3 3】查找问题】查找问题】查找问题】查找问题 在在在在 n n 元列表中查找给定键元列表中查找给定键元列表中查找给定键元列表中查找给定键 蛮力法：顺序查找，最差情况需蛮力法：顺序查找，最差情况需蛮力法：顺序查找，最差情况需蛮力法：顺序查找，最差情况需 n n 次比较，次比较，次比较，次比较，O(n)O(n)变治法：变治法：变治法：变治法：预排序预排序预排序预排序 +折半查找折半查找折半查找折半查找，时间效率：，时间效率：，时间效率：，时间效率：可见预排序比顺序查找的时间效率更差。对于在同一个列表中查找可见预排序比顺序查找的时间效率更差。对于在同一个列表中查找可见预排序比顺序查找的时间效率更差。对于在同一个列表中查找可见预排序比顺序查找的时间效率更差。对于在同一个列表中查找 次数很少的问题，不如顺序查找。若对同一个列表需要很多次查找，次数很少的问题，不如顺序查找。若对同一个列表需要很多次查找，次数很少的问题，不如顺序查找。若对同一个列表需要很多次查找，次数很少的问题，不如顺序查找。若对同一个列表需要很多次查找，效率将超过顺序查找。（分摊效率）效率将超过顺序查找。（分摊效率）效率将超过顺序查找。（分摊效率）效率将超过顺序查找。（分摊效率）预排序的其他应用预排序的其他应用预排序的其他应用预排序的其他应用 许多处理点集的计算几何算法许多处理点集的计算几何算法许多处理点集的计算几何算法许多处理点集的计算几何算法 例如：点集的排序例如：点集的排序例如：点集的排序例如：点集的排序 可根据它们的坐标，或者到某特定直线的距离，或者某种角度等等。可根据它们的坐标，或者到某特定直线的距离，或者某种角度等等。可根据它们的坐标，或者到某特定直线的距离，或者某种角度等等。可根据它们的坐标，或者到某特定直线的距离，或者某种角度等等。如在最近对、凸包问题的分治算法中，都曾采用了预排序技术。如在最近对、凸包问题的分治算法中，都曾采用了预排序技术。如在最近对、凸包问题的分治算法中，都曾采用了预排序技术。如在最近对、凸包问题的分治算法中，都曾采用了预排序技术。预排序：查找问题【例预排序：查找问题【例3】查找问题】查找问题 在在 n 元列表中查找元列表中查找平衡查找树 平衡查找树平衡查找树平衡查找树平衡查找树二叉查找树二叉查找树二叉查找树二叉查找树 BST BST 是一种重要的数据结构，是集合的一种描述方式。是一种重要的数据结构，是集合的一种描述方式。是一种重要的数据结构，是集合的一种描述方式。是一种重要的数据结构，是集合的一种描述方式。集合用集合用集合用集合用 BST BST 描述是改变表现形式的一种变治技术。描述是改变表现形式的一种变治技术。描述是改变表现形式的一种变治技术。描述是改变表现形式的一种变治技术。BST BST 与线性表相比，查找、插入和删除操作的时间效率较好，属于与线性表相比，查找、插入和删除操作的时间效率较好，属于与线性表相比，查找、插入和删除操作的时间效率较好，属于与线性表相比，查找、插入和删除操作的时间效率较好，属于 logn logn 型（平均），最坏型（平均），最坏型（平均），最坏型（平均），最坏 O(n)O(n)退化为一棵完全不平衡树（链）退化为一棵完全不平衡树（链）退化为一棵完全不平衡树（链）退化为一棵完全不平衡树（链）保持保持保持保持 BST BST 的好特性，避免退化的两种方案的好特性，避免退化的两种方案的好特性，避免退化的两种方案的好特性，避免退化的两种方案 【实例化简】【实例化简】【实例化简】【实例化简】对不平衡对不平衡对不平衡对不平衡 BST BST 进行各种变换，重新构造平衡树。进行各种变换，重新构造平衡树。进行各种变换，重新构造平衡树。进行各种变换，重新构造平衡树。不同算法对不同算法对不同算法对不同算法对BSTBST的的的的 平衡要求不同。如平衡要求不同。如平衡要求不同。如平衡要求不同。如AVLAVL树平衡：每个节点左右子树高度差树平衡：每个节点左右子树高度差树平衡：每个节点左右子树高度差树平衡：每个节点左右子树高度差1.1.【改变表现】【改变表现】【改变表现】【改变表现】BST BST 每个节点仅允许有每个节点仅允许有每个节点仅允许有每个节点仅允许有 1 1 个键（查找的属性）。个键（查找的属性）。个键（查找的属性）。个键（查找的属性）。允许每个节点可包含不止一个键。典型例子：允许每个节点可包含不止一个键。典型例子：允许每个节点可包含不止一个键。典型例子：允许每个节点可包含不止一个键。典型例子：2-3 2-3 树、树、树、树、2-3-4 2-3-4 树，更一般的树，更一般的树，更一般的树，更一般的 B B 树（树（树（树（B B+树、树、树、树、B*B*树）树）树）树）平衡查找树平衡查找树 平衡查找树平衡查找树AVL树 AVL AVL 树树树树 （19621962，前苏联科学家，前苏联科学家，前苏联科学家，前苏联科学家G.M.Adelson-Velsky,G.M.Adelson-Velsky,E.M.LandisE.M.Landis）AVL AVL 树是树是树是树是 BST.BST.树高：根到叶的最长路径的边数。设根为树高：根到叶的最长路径的边数。设根为树高：根到叶的最长路径的边数。设根为树高：根到叶的最长路径的边数。设根为 0 0 层，树高层，树高层，树高层，树高=最底层编号最底层编号最底层编号最底层编号节点平衡因子：左子树高节点平衡因子：左子树高节点平衡因子：左子树高节点平衡因子：左子树高-右子树高右子树高右子树高右子树高AVL AVL 树：每个节点的平衡因子均为树：每个节点的平衡因子均为树：每个节点的平衡因子均为树：每个节点的平衡因子均为 0 0、-1-1、+1+110105 520204 42 27 78 81212AVLAVL树树树树10105 520204 42 27 78 8非非非非AVLAVL树，树，树，树，BSTBSTAVL树树 AVL 树树（1962，前苏联科学家，前苏联科学家G.M.AdeAVL树的4种变换AVLAVL树生成（插入）算法树生成（插入）算法树生成（插入）算法树生成（插入）算法 AVL AVL树是树是树是树是BSTBST，用，用，用，用BSTBST插入算法生成。插入算法生成。插入算法生成。插入算法生成。插入新节点后，插入新节点后，插入新节点后，插入新节点后，若若若若 AVL AVL 树失去平衡，进行旋转，树失去平衡，进行旋转，树失去平衡，进行旋转，树失去平衡，进行旋转，重新平衡它。重新平衡它。重新平衡它。重新平衡它。节点有节点有节点有节点有 4 4 种插入位置，对应种插入位置，对应种插入位置，对应种插入位置，对应 4 4 种旋转变换：种旋转变换：种旋转变换：种旋转变换：1.1.最近不平衡节点的最近不平衡节点的最近不平衡节点的最近不平衡节点的左子树的左节点左子树的左节点左子树的左节点左子树的左节点 右单转，右单转，右单转，右单转，R R旋转旋转旋转旋转 2.2.最近不平衡节点的最近不平衡节点的最近不平衡节点的最近不平衡节点的右子树的右节点右子树的右节点右子树的右节点右子树的右节点 左单转，左单转，左单转，左单转，L L旋转旋转旋转旋转 3.3.最近不平衡节点的最近不平衡节点的最近不平衡节点的最近不平衡节点的左子树的右节点左子树的右节点左子树的右节点左子树的右节点 左右双转，左右双转，左右双转，左右双转，LRLR旋转旋转旋转旋转 4.4.最近不平衡节点的最近不平衡节点的最近不平衡节点的最近不平衡节点的右子树的左节点右子树的左节点右子树的左节点右子树的左节点 右左双转，右左双转，右左双转，右左双转，RLRL旋转旋转旋转旋转1 1R(3)R(3)3 32 23 32 21 1左子树的左节点左子树的左节点左子树的左节点左子树的左节点AVL树的树的4种变换种变换AVL树生成（插入）算法树生成（插入）算法1R(3)3232AVL树生成算法的4种旋转变换（续1）1 12 23 3L(1)L(1)3 32 21 1右子树的右节点右子树的右节点右子树的右节点右子树的右节点3 32 21 1L(1)L(1)3 31 12 2左子树的右节点左子树的右节点左子树的右节点左子树的右节点3 32 21 1R(3)R(3)AVL树生成算法的树生成算法的4种旋转变换（续种旋转变换（续1）123L(1)321右右AVL树生成算法的4种旋转变换（续2）1 1右子树的左节点右子树的左节点右子树的左节点右子树的左节点2 23 3R(3)R(3)1 13 32 23 32 21 1L(1)L(1)右单转的一般情况（左子树左节点）右单转的一般情况（左子树左节点）右单转的一般情况（左子树左节点）右单转的一般情况（左子树左节点）R(wR(w)1 1wwe eT T1 1T T2 2T T3 31 1e ewwT T3 3T T2 2T T1 1AVL树生成算法的树生成算法的4种旋转变换（续种旋转变换（续2）1右子树的左节点右子树的左节点23RAVL树生成算法的4种旋转变换（续3）wwk kT T4 4T T3 3T T1 1e eT T2 21 1左右双转的一般情况（左子树右节点）左右双转的一般情况（左子树右节点）左右双转的一般情况（左子树右节点）左右双转的一般情况（左子树右节点）（先左单转，后右单转）（先左单转，后右单转）（先左单转，后右单转）（先左单转，后右单转）L(e)L(e)wwk kT T4 4T T3 3T T1 1e eT T2 21 1AVL树生成算法的树生成算法的4种旋转变换（续种旋转变换（续3）wkT4T3T1eT2AVL树生成算法的4种旋转变换（续4）wwk kT T4 4T T3 3T T1 1e eT T2 21 1wwk kT T4 4T T3 3T T1 1e eT T2 2R(wR(w)AVLAVL树效率：树效率：树效率：树效率：它是它是BST，效率与，效率与BST一样取决于树高：一样取决于树高：AVLAVL树缺点：树缺点：树缺点：树缺点：频繁的旋转、维护树节点平衡，设计上较复杂，尤其是频繁的旋转、维护树节点平衡，设计上较复杂，尤其是 删除操作，妨碍了其应用。但蕴涵的思想使人们发现了删除操作，妨碍了其应用。但蕴涵的思想使人们发现了 BST 的其他变种。的其他变种。AVL树生成算法的树生成算法的4种旋转变换（续种旋转变换（续4）wkT4T3T1eT22-3树：定义 2-3 2-3 树树树树 BST BST的变体的变体的变体的变体2-3 2-3 树的特性（定义）树的特性（定义）树的特性（定义）树的特性（定义）1.1.每个节点包含每个节点包含每个节点包含每个节点包含 1 1 个或个或个或个或 2 2 个键个键个键个键2.2.每个内部节点有每个内部节点有每个内部节点有每个内部节点有 2 2 种类型：种类型：种类型：种类型：2 2 节点节点节点节点 1 1 个键个键个键个键 K K，2 2 个子女个子女个子女个子女 3 3 节点节点节点节点 2 2 个键个键个键个键 K K1 1 K K2 2，3 3 个子女个子女个子女个子女（键值关系如下图）（键值关系如下图）（键值关系如下图）（键值关系如下图）3.3.所有叶节点在树的同一层，树高平衡所有叶节点在树的同一层，树高平衡所有叶节点在树的同一层，树高平衡所有叶节点在树的同一层，树高平衡2-3 2-3 树的两种节点类型树的两种节点类型树的两种节点类型树的两种节点类型K KK K K K 2 2节点节点节点节点K K1 1,K,K2 2K K1 1 KK2 2 K1,K2)K K1 1 K K2 23 3节点节点节点节点2-3树：定义树：定义 2-3 树树 BST的变体的变体2-3 树的两树的两2-3树插入算法过程图示举例说明：举例说明：举例说明：举例说明：2-3 2-3 树生成（插入）算法的过程图示树生成（插入）算法的过程图示树生成（插入）算法的过程图示树生成（插入）算法的过程图示 将序列将序列将序列将序列 9,5,8,3,2,4,7 9,5,8,3,2,4,7 构造一棵构造一棵构造一棵构造一棵 2-3 2-3 树树树树9 95 5,95,8 8,98 89 95 58 89 93 3,5分裂，提升分裂，提升分裂，提升分裂，提升8 89 92,2,3 3,5,53 3,89 92 25 53,83,89 92 24 4,53,83,89 92 24,5 5,7 78 83 35 52 24 47 79 93,5 5,89 92 24 47 72-3树插入算法过程图示举例说明：树插入算法过程图示举例说明：2-3 树生成（插入）算法树生成（插入）算法2-3树插入算法2-3 2-3 树插入算法（树插入算法（树插入算法（树插入算法（3 3 阶阶阶阶B B 树）树）树）树）注意保持注意保持注意保持注意保持 2-3 2-3 树的性质树的性质树的性质树的性质 1.1.用查找算法找到恰当的叶节点位置，插入新节点用查找算法找到恰当的叶节点位置，插入新节点用查找算法找到恰当的叶节点位置，插入新节点用查找算法找到恰当的叶节点位置，插入新节点 2.2.若插入节点溢出，分裂该节点，中间键（键值大小）加入父结点若插入节点溢出，分裂该节点，中间键（键值大小）加入父结点若插入节点溢出，分裂该节点，中间键（键值大小）加入父结点若插入节点溢出，分裂该节点，中间键（键值大小）加入父结点 若父结点溢出，继续分裂父节点若父结点溢出，继续分裂父节点若父结点溢出，继续分裂父节点若父结点溢出，继续分裂父节点 若分裂过程向上传递到根节点，树加高一层若分裂过程向上传递到根节点，树加高一层若分裂过程向上传递到根节点，树加高一层若分裂过程向上传递到根节点，树加高一层2-3 2-3 树查找算法（类似树查找算法（类似树查找算法（类似树查找算法（类似 BST BST）从从从从 2-3 2-3 树的根节点开始：树的根节点开始：树的根节点开始：树的根节点开始：1.1.查找当前节点查找当前节点查找当前节点查找当前节点 若找到关键码（键），查找成功返回若找到关键码（键），查找成功返回若找到关键码（键），查找成功返回若找到关键码（键），查找成功返回 若未找到，且当前节点已是叶节点，查找失败返回若未找到，且当前节点已是叶节点，查找失败返回若未找到，且当前节点已是叶节点，查找失败返回若未找到，且当前节点已是叶节点，查找失败返回 2.2.确定查找分支，转确定查找分支，转确定查找分支，转确定查找分支，转 1 1 2-3树插入算法树插入算法2-3 树插入算法（树插入算法（3 阶阶B 树）树）2-3树删除算法2-3 2-3 树删除算法树删除算法树删除算法树删除算法 删除键而非删除节点删除键而非删除节点删除键而非删除节点删除键而非删除节点 删除一个键时，删除一个键时，删除一个键时，删除一个键时，2 2 节点情况与节点情况与节点情况与节点情况与 BST BST 相同。相同。相同。相同。对于对于对于对于 3 3 节点情况，分节点情况，分节点情况，分节点情况，分 3 3 种情况：种情况：种情况：种情况：1.1.叶节点，有叶节点，有叶节点，有叶节点，有 2 2 个键：个键：个键：个键：删除右图删除右图删除右图删除右图“4 4 ”键键键键 简单删除简单删除简单删除简单删除“4”“4”，2-3 2-3 树性质不变树性质不变树性质不变树性质不变2.2.叶节点，仅叶节点，仅叶节点，仅叶节点，仅 1 1 个键：个键：个键：个键：删除右图删除右图删除右图删除右图“2”2”键键键键 简单删除简单删除简单删除简单删除2 2，不符合，不符合，不符合，不符合 2-3 2-3 树性质。树性质。树性质。树性质。若相邻兄弟无多余键若相邻兄弟无多余键若相邻兄弟无多余键若相邻兄弟无多余键（仅（仅（仅（仅1 1个，如去掉个，如去掉个，如去掉个，如去掉“4”“4”），），），），将该相邻兄弟和父节点中、它俩的分界键将该相邻兄弟和父节点中、它俩的分界键将该相邻兄弟和父节点中、它俩的分界键将该相邻兄弟和父节点中、它俩的分界键 并入已删除键的空节点中。并入已删除键的空节点中。并入已删除键的空节点中。并入已删除键的空节点中。若相邻兄弟有多余键若相邻兄弟有多余键若相邻兄弟有多余键若相邻兄弟有多余键（如（如（如（如“4”4”、“5”“5”）借码借码借码借码 把该兄弟的把该兄弟的把该兄弟的把该兄弟的 2 2 个键和父节点中的个键和父节点中的个键和父节点中的个键和父节点中的 分界键并入该空节点，再作分裂分界键并入该空节点，再作分裂分界键并入该空节点，再作分裂分界键并入该空节点，再作分裂3.3.内部节点（非叶节点）：内部节点（非叶节点）：内部节点（非叶节点）：内部节点（非叶节点）：如删除右上图如删除右上图如删除右上图如删除右上图“3”3”键键键键 删除仅在叶节点进行，替换后再删除替换键删除仅在叶节点进行，替换后再删除替换键删除仅在叶节点进行，替换后再删除替换键删除仅在叶节点进行，替换后再删除替换键（图略）（图略）（图略）（图略）替换键替换键替换键替换键 比该键大的子树中的最小键比该键大的子树中的最小键比该键大的子树中的最小键比该键大的子树中的最小键3 3,89 92 24 4,59 93 3,58 84 4,89 95 53 32-3树删除算法树删除算法2-3 树删除算法树删除算法 删除键而非删除节点删除键而非删除节点2-3树的时间效率2-3 2-3 树时间效率树时间效率树时间效率树时间效率 时间效率取决于时间效率取决于时间效率取决于时间效率取决于 树高（树高（树高（树高（h h），），），），下面考察下面考察下面考察下面考察 2-3 2-3 树的两种极端的树高树的两种极端的树高树的两种极端的树高树的两种极端的树高 树高：树高：树高：树高：从根到叶最长路径的边数从根到叶最长路径的边数从根到叶最长路径的边数从根到叶最长路径的边数 =最大层号（根为最大层号（根为最大层号（根为最大层号（根为 0 0 层）层）层）层）2-3 2-3 树全部由树全部由树全部由树全部由 2 2 节点构成：节点构成：节点构成：节点构成：当前层节点数当前层节点数当前层节点数当前层节点数 =2=2上一层节点数上一层节点数上一层节点数上一层节点数 一棵满的完全二叉树（一棵满的完全二叉树（一棵满的完全二叉树（一棵满的完全二叉树（n n 个节点，高度个节点，高度个节点，高度个节点，高度 h h），节点总数：），节点总数：），节点总数：），节点总数：n=2 n=20 0+2+21 1+2+22 2+.+2+.+2h h=2 2h+1 h+1 1 1 一般的一般的一般的一般的 2-3 2-3 树（既有树（既有树（既有树（既有 2 2 节点又有节点又有节点又有节点又有 3 3 节点），节点总数：节点），节点总数：节点），节点总数：节点），节点总数：n 2 n 2h+1 h+1 1 1 即即即即 h log h log2 2(n+1)1(n+1)1 2-3 2-3 树全部由树全部由树全部由树全部由 3 3 节点构成：节点构成：节点构成：节点构成：当前层节点数当前层节点数当前层节点数当前层节点数 =3=3上一层节点数上一层节点数上一层节点数上一层节点数 n=3n=30 0+3+31 1+3+32 2+.+3+.+3h h=3=3h+1 h+1 1 1 一般的一般的一般的一般的 2-3 2-3 树（既有树（既有树（既有树（既有 2 2 节点又有节点又有节点又有节点又有 3 3 节点），节点总数：节点），节点总数：节点），节点总数：节点），节点总数：n 3n 3h+1 h+1 1 1 即即即即 h log h log3 3(n+1)1(n+1)1 综合综合综合综合1 1、2 2：loglog3 3(n+1)1 h log(n+1)1 h log2 2(n+1)1(n+1)1 无论最差或平均情况，无论最差或平均情况，无论最差或平均情况，无论最差或平均情况，2-3 2-3 树字典操作（插入、删除、查找）的时间树字典操作（插入、删除、查找）的时间树字典操作（插入、删除、查找）的时间树字典操作（插入、删除、查找）的时间效率都属于效率都属于效率都属于效率都属于(logn)(logn)型。型。型。型。2-3 2-3 树有重要的扩展形式树有重要的扩展形式树有重要的扩展形式树有重要的扩展形式 B B、B B+、B*B*树树树树2-3树的时间效率树的时间效率2-3 树时间效率树时间效率堆与优先队列 堆堆堆堆(Heap)(Heap)与优先队列与优先队列与优先队列与优先队列(Priority queue)(Priority queue)堆是一种数据结构，尤其适合用来实现堆是一种数据结构，尤其适合用来实现堆是一种数据结构，尤其适合用来实现堆是一种数据结构，尤其适合用来实现 优先队列优先队列优先队列优先队列 。优先队列优先队列优先队列优先队列 按对象的按对象的按对象的按对象的 优先级优先级优先级优先级 属性排序的对象集合。属性排序的对象集合。属性排序的对象集合。属性排序的对象集合。优先队列应用例优先队列应用例优先队列应用例优先队列应用例 多任务操作系统对执行程序进行调度。某时刻，可能有多个程序已经多任务操作系统对执行程序进行调度。某时刻，可能有多个程序已经多任务操作系统对执行程序进行调度。某时刻，可能有多个程序已经多任务操作系统对执行程序进行调度。某时刻，可能有多个程序已经准备好可以执行。当一个任务已经准备好可以执行时，被插入到优先准备好可以执行。当一个任务已经准备好可以执行时，被插入到优先准备好可以执行。当一个任务已经准备好可以执行时，被插入到优先准备好可以执行。当一个任务已经准备好可以执行时，被插入到优先 队列。当系统允许执行新任务时，从优先队列中挑选具有最高优先级队列。当系统允许执行新任务时，从优先队列中挑选具有最高优先级队列。当系统允许执行新任务时，从优先队列中挑选具有最高优先级队列。当系统允许执行新任务时，从优先队列中挑选具有最高优先级的任务执行。有些应用要求能改变对象的优先级。的任务执行。有些应用要求能改变对象的优先级。的任务执行。有些应用要求能改变对象的优先级。的任务执行。有些应用要求能改变对象的优先级。堆的概念堆的概念堆的概念堆的概念堆，在逻辑上是一棵二叉树，必须满足两个条件：堆，在逻辑上是一棵二叉树，必须满足两个条件：堆，在逻辑上是一棵二叉树，必须满足两个条件：堆，在逻辑上是一棵二叉树，必须满足两个条件：1.1.树的形状：树的形状：树的形状：树的形状：完全二叉树完全二叉树完全二叉树完全二叉树，可用数组实现（存储结构）。，可用数组实现（存储结构）。，可用数组实现（存储结构）。，可用数组实现（存储结构）。2.2.父母优势：父母优势：父母优势：父母优势：每个父节点值每个父节点值每个父节点值每个父节点值 子节点值子节点值子节点值子节点值（即堆中元素值局部有序），（即堆中元素值局部有序），（即堆中元素值局部有序），（即堆中元素值局部有序），本节介绍最大值堆本节介绍最大值堆本节介绍最大值堆本节介绍最大值堆(max-heap)(max-heap)。另外还有最小值堆。另外还有最小值堆。另外还有最小值堆。另外还有最小值堆 (min-heap)(min-heap)，此条件刚好相反。，此条件刚好相反。，此条件刚好相反。，此条件刚好相反。堆与优先队列堆与优先队列 堆堆(Heap)与优先队列与优先队列(Priorit满二叉树与完全二叉树满二叉树满二叉树满二叉树满二叉树 (Full Binary Tree)(Full Binary Tree)每个内部节点都有两个非空子节点。每个内部节点都有两个非空子节点。每个内部节点都有两个非空子节点。每个内部节点都有两个非空子节点。完全二叉树完全二叉树完全二叉树完全二叉树 (Complete Binary Tree)(Complete Binary Tree)从二叉树的构形判断从二叉树的构形判断从二叉树的构形判断从二叉树的构形判断 1.1.最底层叶节点可以最底层叶节点可以最底层叶节点可以最底层叶节点可以从右向左连续缺从右向左连续缺从右向左连续缺从右向左连续缺若干个，其他层必须满。若干个，其他层必须满。若干个，其他层必须满。若干个，其他层必须满。2.2.叶节点只可以出现在最底两层上。叶节点只可以出现在最底两层上。叶节点只可以出现在最底两层上。叶节点只可以出现在最底两层上。问：在逻辑上，堆为什么是一棵完全二叉树？问：在逻辑上，堆为什么是一棵完全二叉树？问：在逻辑上，堆为什么是一棵完全二叉树？问：在逻辑上，堆为什么是一棵完全二叉树？满二叉树与完全二叉树满二叉树满二叉树与完全二叉树满二叉树(Full Binary Tr完全二叉树的数组实现完全二叉树的存储结构完全二叉树的存储结构完全二叉树的存储结构完全二叉树的存储结构 数组数组数组数组 所有节点按从上向下、从左至右存入数组。节点数一定，完全二叉树所有节点按从上向下、从左至右存入数组。节点数一定，完全二叉树所有节点按从上向下、从左至右存入数组。节点数一定，完全二叉树所有节点按从上向下、从左至右存入数组。节点数一定，完全二叉树就确定了即仅一种形状。就确定了即仅一种形状。就确定了即仅一种形状。就确定了即仅一种形状。任一节点的父节点、兄弟节点、子女节点等任一节点的父节点、兄弟节点、子女节点等任一节点的父节点、兄弟节点、子女节点等任一节点的父节点、兄弟节点、子女节点等 均可由数组下标计算出来。因此，不必用指针，而用数组实现。均可由数组下标计算出来。因此，不必用指针，而用数组实现。均可由数组下标计算出来。因此，不必用指针，而用数组实现。均可由数组下标计算出来。因此，不必用指针，而用数组实现。1 1k=2k=23 34 45 56 67 78 89 9 101011111212Hk,k=Hk,k=0 01 12 23 34 45 56 67 78 89 9101011111212父节点父节点父节点父节点1 11 12 22 23 33 34 44 45 55 56 6左子节点左子节点左子节点左子节点2 24 46 68 810101212右子节点右子节点右子节点右子节点3 35 57 79 91111左兄弟左兄弟左兄弟左兄弟2 24 46 68 81010右兄弟右兄弟右兄弟右兄弟3 35 57 79 91111k k奇数奇数奇数奇数k k偶数偶数偶数偶数完全二叉树的数组实现完全二叉树的存储结构完全二叉树的数组实现完全二叉树的存储结构 数组数组1k=2堆与数组实现堆的存储结构（数组）堆的存储结构（数组）堆的存储结构（数组）堆的存储结构（数组）10107 75 54 42 21 110107 75 54 41 110107 75 54 48 81 1【判断】上面三棵树那些是堆，那些不是堆？【判断】上面三棵树那些是堆，那些不是堆？【判断】上面三棵树那些是堆，那些不是堆？【判断】上面三棵树那些是堆，那些不是堆？非完全二叉树非完全二叉树非完全二叉树非完全二叉树不满足父母优势不满足父母优势不满足父母优势不满足父母优势 k=k=0 01 12 23 34 45 56 6 HkHk10107 75 52 24 41 11.1.树高树高树高树高 2.H0 2.H0 为空，或放置最大限位器为空，或放置最大限位器为空，或放置最大限位器为空，或放置最大限位器3.3.父母优势（兄弟节点没有关系）父母优势（兄弟节点没有关系）父母优势（兄弟节点没有关系）父母优势（兄弟节点没有关系）10107 75 54 42 21 1堆与数组实现堆的存储结构（数组）堆与数组实现堆的存储结构（数组）10754211075411堆的构造算法过程图解 堆的构造算法堆的构造算法堆的构造算法堆的构造算法 构造一棵满足父母优势的完全二叉树构造一棵满足父母优势的完全二叉树构造一棵满足父母优势的完全二叉树构造一棵满足父母优势的完全二叉树值交换算法：值交换算法：值交换算法：值交换算法：构造列表构造列表构造列表构造列表 2,9,72,9,7,6,5,8 ,6,5,8 的堆的堆的堆的堆 按列表元素的顺序将列表存入数组，逻辑结构是完全二叉树。按列表元素的顺序将列表存入数组，逻辑结构是完全二叉树。按列表元素的顺序将列表存入数组，逻辑结构是完全二叉树。按列表元素的顺序将列表存入数组，逻辑结构是完全二叉树。从最后的父母节点开始，从最后的父母节点开始，从最后的父母节点开始，从最后的父母节点开始，检查是否满足父母优势。若不满足，它与检查是否满足父母优势。若不满足，它与检查是否满足父母优势。若不满足，它与检查是否满足父母优势。若不满足，它与 最大子节点最大子节点最大子节点最大子节点交换，继续交换，继续交换，继续交换，继续下推下推下推下推至合适位置。继续检查下一个父母节点，至合适位置。继续检查下一个父母节点，至合适位置。继续检查下一个父母节点，至合适位置。继续检查下一个父母节点，此过程持续此过程持续此过程持续此过程持续到根节点止。到根节点止。到根节点止。到根节点止。不同的值交换算法生成的堆不唯一。不同的值交换算法生成的堆不唯一。不同的值交换算法生成的堆不唯一。不同的值交换算法生成的堆不唯一。2 29 97 75 56 68 82 29 98 85 56 67 72 29 98 85 56 67 72 29 98 85 56 67 79 92 28 85 56 67 79 96 68 85 52 27 7堆的构造算法过程图解堆的构造算法过程图解 堆的构造算法堆的构造算法 构造一棵满足父母优构造一棵满足父母优值交换的堆构造算法堆构造的值交换算法堆构造的值交换算法堆构造的值交换算法堆构造的值交换算法/父节点父节点父节点父节点 i i 循环，最后父节点开始循环，最后父节点开始循环，最后父节点开始循环，最后父节点开始/不满足父母优势不满足父母优势不满足父母优势不满足父母优势/满足父母优势，退出满足父母优势，退出满足父母优势，退出满足父母优势，退出 while while 循环循环循环循环/较大子节点下标较大子节点下标较大子节点下标较大子节点下标 j j/若有右子节点，则必有左子节点若有右子节点，则必有左子节点若有右子节点，则必有左子节点若有右子节点，则必有左子节点/j=2k/j=2k是左子节点下标，是左子节点下标，是左子节点下标，是左子节点下标，j+1 j+1 是右子节点下标是右子节点下标是右子节点下标是右子节点下标/检查父母优势条件，父节点值为检查父母优势条件，父节点值为检查父母优势条件，父节点值为检查父母优势条件，父节点值为 v v/v/v 是当前父节点值，是当前父节点值，是当前父节点值，是当前父节点值，k k 是它的下标是它的下标是它的下标是它的下标/无左子节点：叶节点无左子节点：叶节点无左子节点：叶节点无左子节点：叶节点/不满足父母优势，值覆盖不满足父母优势，值覆盖不满足父母优势，值覆盖不满足父母优势，值覆盖/kj/kj，父节点向下推后父节点向下推后父节点向下推后父节点向下推后，/继续继续继续继续while while 循环循环循环循环/当前父节点值还原当前父节点值还原当前父节点值还原当前父节点值还原注释：父节点下推过程中注释：父节点下推过程中注释：父节点下推过程中注释：父节点下推过程中值不变值不变值不变值不变。把它理解为。把它理解为。把它理解为。把它理解为空节点，与较大子节点交换键值，直到空节点空节点，与较大子节点交换键值，直到空节点空节点，与较大子节点交换键值，直到空节点空节点，与较大子节点交换键值，直到空节点到达它的最后位置，再把抹去的值还给它。到达它的最后位置，再把抹去的值还给它。到达它的最后位置，再把抹去的值还给它。到达它的最后位置，再把抹去的值还给它。值交换的堆构造算法堆构造的值交换算法值交换的堆构造算法堆构造的值交换算法/父节点父节点 i 循环，循环，值交换的堆构造算法时间效率堆构造值交换算法的时间效率堆构造值交换算法的时间效率堆构造值交换算法的时间效率堆构造值交换算法的时间效率输入规模：输入规模：输入规模：输入规模：节点数节点数节点数节点数 n.n.基本操作：基本操作：基本操作：基本操作：键值比较键值比较键值比较键值比较效率类别：效率类别：效率类别：效率类别：最差、最佳、平均效率。最优情况：已是最大值堆最差、最佳、平均效率。最优情况：已是最大值堆最差、最佳、平均效率。最优情况：已是最大值堆最差、最佳、平均效率。最优情况：已是最大值堆最差效率：最差效率：最差效率：最差效率：设设设设 n=2n=2h+1 h+1 1 1，满的完全二叉树，满的完全二叉树，满的完全二叉树，满的完全二叉树，h h 为最大层号（根为为最大层号（根为为最大层号（根为为最大层号（根为 0 0）下层节点数下层节点数下层节点数下层节点数 =上层节点数上层节点数上层节点数上层节点数2 2,h=log,h=log2 2(n+1)1.(n+1)1.最坏情况是最小值堆最坏情况是最小值堆最坏情况是最小值堆最坏情况是最小值堆 每个父母节点都要下推至叶节点。每个父母节点都要下推至叶节点。每个父母节点都要下推至叶节点。每个父母节点都要下推至叶节点。每次下推，都要作两次比较：每次下推，都要作两次比较：每次下推，都要作两次比较：每次下推，都要作两次比较：1.1.左右子节点比较，找较大者；左右子节点比较，找较大者；左右子节点比较，找较大者；左右子节点比较，找较大者；2.2.父子比较确定当前父节点是否下推。父子比较确定当前父节点是否下推。父子比较确定当前父节点是否下推。父子比较确定当前父节点是否下推。第第第第 k k 层上的父节点，需作层上的父节点，需作层上的父节点，需作层上的父节点，需作 2(h k)2(h k)次比较。次比较。次比较。次比较。k=0 h k=0 h 需要下推需要下推需要下推需要下推 h 1 h 1 层，总比较次数：层，总比较次数：层，总比较次数：层，总比较次数：结论：构造规模为结论：构造规模为结论：构造规模为结论：构造规模为n n的堆，的堆，的堆，的堆，少于少于少于少于2n2n次比较即可完成。次比较即可完成。次比较即可完成。次比较即可完成。思考：思考：思考：思考：2 2k k 项何意？项何意？项何意？项何意？值交换的堆构造算法时间效率堆构造值交换算法的时间效率结论：构值交换的堆构造算法时间效率堆构造值交换算法的时间效率结论：构堆构造的插入算法堆构造的插入算法堆构造的插入算法堆构造的插入算法堆构造的插入算法（效率较差）（效率较差）（效率较差）（效率较差）算法策略：算法策略：算法策略：算法策略：把元素（节点）一个接一个地插入堆中。把元素（节点）一个接一个地插入堆中。把元素（节点）一个接一个地插入堆中。把元素（节点）一个接一个地插入堆中。算法步骤：算法步骤：算法步骤：算法步骤：如图，插入键值如图，插入键值如图，插入键值如图，插入键值 =10=10 的一个节点的一个节点的一个节点的一个节点 1.1.把节点值把节点值把节点值把节点值 V=10 V=10 插入堆的末尾（最后叶节点，插入堆的末尾（最后叶节点，插入堆的末尾（最后叶节点，插入堆的末尾（最后叶节点，数组末尾数组末尾数组末尾数组末尾）2.V 2.V 在堆中的位置可能不正确，需要在堆中的位置可能不正确，需要在堆中的位置可能不正确，需要在堆中的位置可能不正确，需要 上推上推上推上推 到合适位置：到合适位置：到合适位置：到合适位置：（1 1）若）若）若）若 V V 父母，满足父母优势条件，位置合适；父母，满足父母优势条件，位置合适；父母，满足父母优势条件，位置合适；父母，满足父母优势条件，位置合适；（2 2）若）若）若）若 V V 父母，则交换它们。然后，