《理学数据结构PPT第八章》由会员分享，可在线阅读，更多相关《理学数据结构PPT第八章（92页珍藏版）》请在金锄头文库上搜索。
1、n n并查集并查集n n静态搜索表静态搜索表n n二叉搜索树二叉搜索树n nAVL树树1并查集并查集 (Union-Find Sets)n n并查集支持以下三种操作：并查集支持以下三种操作：uu Union (Root1, Root2) /合并操作合并操作uu Find (x) /搜索操作搜索操作uu InitUFSets (s ) /初始化操作初始化操作n n对于并查集来说，每个集合用一棵树表示。对于并查集来说，每个集合用一棵树表示。n n为此，采用为此，采用树的双亲表示树的双亲表示作为集合存储表示。作为集合存储表示。集合元素的编号从集合元素的编号从0到到 n- -1。其中。其中 n 是最大
2、是最大元素个数。元素个数。2n n在在双亲表示双亲表示中，中，第第 i 个数组元素代表包含个数组元素代表包含集合元素集合元素 i 的树结点的树结点。初始时。初始时, 根结点的根结点的双亲为双亲为- -1，表示集合中的元素个数。，表示集合中的元素个数。n n在同一棵树上所有结点所代表的集合元素在同一棵树上所有结点所代表的集合元素在同一个子集合中。在同一个子集合中。n n为此，需要有两个映射：为此，需要有两个映射：uu 集合元素到存放该元素名的树结点间集合元素到存放该元素名的树结点间的对应；的对应；uu 集合名到表示该集合的树的根结点间集合名到表示该集合的树的根结点间的对应。的对应。3n n设设
3、S1= 0, 6, 7, 8 , S2= 1, 4, 9 , S3= 2, 3, 5 集合名集合名 指针指针0 S11 S22 S30427681935n n为为简简化化讨讨论论，忽忽略略实实际际的的集集合合名名，仅仅用用表表示集合的树的根来标识集合示集合的树的根来标识集合。4n n初初始始时时, InitUFSets(S) 构构造造一一个个森森林林, 每每棵棵树树只只有有一一个个结结点点, 表表示示集集合合中中各各元元素素自自成成一个子集合一个子集合 Si = - -1, i = 0, 1, , n- -1。n n用用 Find(S, i) 寻找集合元素寻找集合元素 i 的根。的根。n n如
4、果有两个集合元素如果有两个集合元素 i 和和 j: Find(S, i) = Find(S, j) 表明这两个元素在同一个集合中，表明这两个元素在同一个集合中，n n如如果果两两个个集集合合元元素素 i 和和 j 不不在在同同一一个个集集合合中中,可可用用 Union(S, i, j) 将将它它们们合合并并到到一一个个集集合中。合中。5S1下标下标下标下标parent集合集合 S S1 1, , S S2 2 和和 S S3 3 的双亲表示的双亲表示- -4 4 - -3 2 - -3 2 0 0 0 40 1 2 3 4 5 6 7 8 90768419235S2S36S1 S2的可能的表示
5、方法的可能的表示方法下标下标下标下标parent集合集合 S S1 1 S S2 2 和和 S S3 3 的双亲表示的双亲表示- -7 4 - -3 2 0 2 0 0 0 40 1 2 3 4 5 6 7 8 9076841941908767并查集的结构定义并查集的结构定义const int SetSize = 50; /并查集元素个数typedef struct /并查集结构定义 int parentSetSize; /集合元素数组 UFSets;void InitUFSets (UFSets *S) /集合初始化 for ( int i = 0; i parenti = -1; /每一个
6、自成一个单元素集合8% 并查集操作的算法并查集操作的算法n n 查找查找- - - -501230 01 12 23 34 4Find (S,4)Find (S,3) = 3 Find (S,2) =2 Find (S,1) = 1Find (S,0) = 0 = - -5 parent x parent x ); -5 0 1 2 35 0 1 2 3parentParent4 =3 Parent3 =2Parent2 =1Parent1 =0Parent0 =-50 1 2 3 410void Union (UFSets *S, int Root1, int Root2) /求两个不相交集
7、合Root1与Root2的并 S-parentRoot1 += S-parentRoot2; S-parentRoot2 = Root1; /将Root2连接到Root1下面n nFind和和Union操作性能不好。假设最初操作性能不好。假设最初 n 个个元素构成元素构成 n 棵树组成的森林，棵树组成的森林，S- - parenti = - -1。做处理。做处理Union(n- -2, n- -1), , Union(1, 2), Union(0, 1)后，将产生退后，将产生退化的树。化的树。11n n合并合并- - - -1- - - -1- - - -1- - - -1- - - -10
8、02 23 34 4- - - -3- - - -5032 21 13 33 34 4133220 02 23 31 14 4Union(0,1)- - - -23- - - -414 421 12 23 34 4Union(1,2)Union(2,3)Union(3,4)12n n 执行一次执行一次Union操作所需时间是操作所需时间是 O(1)，n- -1次次Union操作所需时间是操作所需时间是O(n)。n n 若再执行若再执行Find(0), Find(1), , Find(n- -1), 若被搜索的元素为若被搜索的元素为 i，完成完成 Find(i) 操作需要操作需要时间为时间为O(
9、i)，完成完成 n 次搜索需要的总时间将次搜索需要的总时间将达到达到n n 改进的方法改进的方法uu 按树的结点个数合并按树的结点个数合并uu 按树的高度合并按树的高度合并uu 压缩元素的路径长度压缩元素的路径长度13n n按树结点个数合并按树结点个数合并结点个数多的树的根结点作根结点个数多的树的根结点作根- - - -1- - - -1- - - -1- - - -1- - - -10 01 12 23 34 4- - - -1- - - -10- - - -725 56 6- - - -5- - - -222332 20 01 13 34 45 56 6233020 05 56 62 23
10、 31 14 4Union(2, 0)14void WeightedUnion (UFSets *S, int Rt1, int Rt2 ) /按Union的加权规则改进的算法 int temp = S-parentRt1 + S-parentRt2; if ( S-parentRt2 parentRt1 ) S-parentRt1 = Rt2; /Root2中结点多 S-parentRt2 = temp; /Root1指向Root2 else S-parentRt2 = Rt1; /Root1中结点多 S-parentRt1 = temp; /Root2指向Root1 15n n按树高度合并
11、按树高度合并 高度高的树的根结点作根高度高的树的根结点作根- - - -0- - - -0- - - -0- - - -0- - - -00 01 12 23 34 4- - - -0- - - -00- - - -225 56 6- - - -2- - - -122332 20 01 13 34 45 56 6233020 05 56 62 23 31 14 4Union(2, 0)16Union操作的折叠规则操作的折叠规则n n为为进进一一步步改改进进树树的的性性能能，可可以以使使用用如如下下折折叠叠规规则则来来“压压缩缩路路径径”。即即： 如如果果 j 是是从从 i 到到根根 root的
12、的 路路 径径 上上 的的 一一 个个 结结 点点 ， 且且 S- - parentj != rootj， 则则把把 S-parentj 置为置为 rooti。0067867819193535从 i = 5 压缩路径17int CollapsingFind (UFSets *S, int i ) /使用折叠规则的搜索算法 int j = i; while ( S-parentj = 0 ) j = S-parentj; /让 j 循双亲指针走到根 while ( i != j ) /换 parenti 到 j int temp = S-parenti; S-parenti = j; i = t
13、emp; return j;18搜索搜索(Search)的概的概念念静态搜索表静态搜索表n n 所谓所谓搜索搜索，就是在数据集合中寻找满足某就是在数据集合中寻找满足某n n 种条件的数据对象种条件的数据对象。n n 搜索的结果通常有两种可能：搜索的结果通常有两种可能：uu 搜索成功搜索成功，即找到满足条件的数据对，即找到满足条件的数据对象象 这时这时,作为结果作为结果, 可报告该对象在结构可报告该对象在结构中中 的位置的位置, 还可给出该对象中的具体信息。还可给出该对象中的具体信息。uu 搜索不成功搜索不成功，或搜索失败。作为结果，或搜索失败。作为结果, 应报告一些信息应报告一些信息, 如失败
14、标志、位置等。如失败标志、位置等。 19n n通常称用于搜索的数据集合为通常称用于搜索的数据集合为搜索结构搜索结构，它是由它是由同一数据类型的对象同一数据类型的对象(或记录或记录)组成。组成。n n在每个对象中有若干属性，其中有一个属在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为关性，其值可唯一地标识这个对象。称为关键码。键码。使用基于关键码的搜索，搜索结果使用基于关键码的搜索，搜索结果应是唯一的。应是唯一的。但在实际应用时，搜索条件但在实际应用时，搜索条件是多方面的，可以是多方面的，可以使用基于属性的搜索方使用基于属性的搜索方法，但搜索结果可能不唯一。法，但搜索结果可
15、能不唯一。20n n实施搜索时有两种不同的环境。实施搜索时有两种不同的环境。uu静态环境静态环境，搜索结构在插入和删除等，搜索结构在插入和删除等操作的前后不发生改变。操作的前后不发生改变。 静态搜索表静态搜索表 uu动态环境动态环境，为保持较高的搜索效率，为保持较高的搜索效率, , 搜索结构在执行插入和删除等操作的前搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。后将自动进行调整，结构可能发生变化。 动态搜索表动态搜索表 21#define MaxSize 100 /搜索表最大尺寸typedef int DataType; /搜索数据的类型 typedef struct
16、/搜索表结点定义 DataType key; /关键码域 other; /其他数据域 ListNode;typedef struct dataList /搜索表结点定义 ListNode dataMaxSize; /数据存储数组 int n; /数组当前长度静态搜索表结构的定义静态搜索表结构的定义22n n衡衡量量一一个个搜搜索索算算法法的的时时间间效效率率的的标标准准是是：在在搜搜索索过过程程中中关关键键码码的的平平均均比比较较次次数数，也也称称为为平平均均搜搜索索长长度度ASL(Average Search Length)，通通常常它它是是搜搜索索结结构构中中对对象象总总数数 n的函数的函
17、数。n n在在静静态态搜搜索索表表中中, 利利用用数数组组元元素素的的下下标标作作为为数数据据对对象象的的存存放放地地址址。搜搜索索算算法法根根据据给给定定值值x, 在在数数组组中中进进行行搜搜索索。直直到到找找到到x在在数数组组中中的的位位置置或或可可确确定定在在数数组组中中找找不不到到x为止。为止。n n另外衡量一个搜索算法还要考虑算法所需另外衡量一个搜索算法还要考虑算法所需要的存储量和算法的复杂性等问题。要的存储量和算法的复杂性等问题。23顺序搜索顺序搜索 (Sequential Search)n n所所谓谓顺顺序序搜搜索索, 又又称称线线性性搜搜索索, 主主要要用用于于在在线性结构中进
18、行搜索。线性结构中进行搜索。n n设设若若表表中中有有 n 个个对对象象，则则顺顺序序搜搜索索从从表表的的先先端端 (或或后后端端) 开开始始, 顺顺序序用用各各对对象象的的关关键键码码与与给给定定值值 x 进进行行比比较较, 直直到到找找到到与与其其值值相相等等的的对对象象, 则则搜搜索索成成功功; 给给出出该该对对象象在在表表中的位置。中的位置。n n若若整整个个表表都都已已检检测测完完仍仍未未找找到到关关键键码码与与x相相等的对象等的对象, 则搜索失败。给出失败信息。则搜索失败。给出失败信息。24int LinearSearch ( dataList A, DataType x ) /在
19、数据表A.data1.n中顺序搜索关键码为 x/的数据对象, A.data0.key 作为控制搜索自动/结束的“监视哨”使用 A.data0.key = x; int i = A.n; /将x送0号位置设置监视哨 while ( A.datai.key != x ) i- ; /从后向前顺序搜索 return i;设置设置“监视哨监视哨”的顺序搜索算法的顺序搜索算法25顺序搜索的平均搜索长度顺序搜索的平均搜索长度 设搜索第设搜索第 i 个元素的概率为个元素的概率为 pi , 搜索到第搜索到第 i 个个元素所需比较次数为元素所需比较次数为 ci , 则搜索成功的平均则搜索成功的平均搜索长度搜索长
20、度:在顺序搜索并设置在顺序搜索并设置“监视哨监视哨”情形：情形： ci = n- - i +1, i = n, n- -1, , 1，因此，因此26在等概率情形，在等概率情形，pi = 1/n, i = 1, 2, , n。 在搜索不成功情形，在搜索不成功情形，ASLunsucc = n+1. 27顺序搜索的递归算法顺序搜索的递归算法int SequentSearch ( dataList A, dataType x, int& loc ) /在数据表 A.data0.n- -1 中搜索其关键码与/给定值匹配的对象, 函数返回其表中位置。/参数 loc 是在表中开始搜索位置 if ( loc
21、= A.n ) return -1; /搜索失败 else if ( A.dataloc.key = x ) return loc; /搜索成功 else return SequentSearch ( A, x, loc+1 ); /递归搜索28int SequentSearch ( dataList A, DataType x ) /在数据表 A.data0.n- -1 中顺序搜索关键码为 x 的数据对象 for ( int i = 0; i x ) break; return -1; /顺序搜索失败, 返回失败信息基于有序顺序表的顺序搜索算法基于有序顺序表的顺序搜索算法29n n有序顺序表
22、的顺序搜索有序顺序表的顺序搜索 ( 10, 20, 30, 40, 50, 60 )105060= = = = = = =20304030基于有序顺序表的折半搜索基于有序顺序表的折半搜索n n设设n个个对对象象存存放放在在一一个个按按其其关关键键码码从从小小到到大大排好了序的有序顺序表中。排好了序的有序顺序表中。n n折折半半搜搜索索时时, 先先求求位位于于搜搜索索区区间间正正中中的的对对象的下标象的下标mid，用其关键码与用其关键码与给定值给定值x比较比较:uu A.datamid.key = x, 搜索成功搜索成功；uu A.datamid.key x, 把把搜搜索索区区间间缩缩小小到到
23、表的表的前半部分前半部分，继续折半搜索，继续折半搜索；uu A.datamid.key x，把把搜搜索索区区间间缩缩小小到到表的表的后半部分后半部分，继续折半搜索。，继续折半搜索。n n如如果果搜搜索索区区间间已已缩缩小小到到一一个个对对象象，仍仍未未找找到想要搜索的对象，则搜索失败。到想要搜索的对象，则搜索失败。31搜索成功的例子搜索成功的例子- -1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8搜索搜索搜索搜索lowmidhigh6 6 8 10 125 6 7 8low midhigh665low mid high632搜索失败的例子搜索失败的例子- -1 0
24、1 3 4 6 8 10 1250 1 2 3 4 5 6 7 8搜索搜索搜索搜索lowmidhigh5 6 8 10 125 6 7 8low midhigh655low mid high533int BinarySearch ( dataList A, DataType x, int low, int high ) int mid = -1; if ( low = high ) mid = ( low + high ) / 2; if ( A.datamid.key x )mid = BinarySearch ( A, x, low, mid -1 ); return mid;基于有序顺序
25、表的折半搜索递归算法基于有序顺序表的折半搜索递归算法34int BinarySearch ( dataList A, DataType x ) int high = A.n-1, low = 0, mid; while ( low = high ) mid = ( low + high ) / 2; if ( A.datamid.key x ) high = mid - 1; /左缩搜索区间 else return mid; /搜索成功 return -1; /搜索失败基于有序顺序表的折半搜索迭代算法基于有序顺序表的折半搜索迭代算法35n n有序顺序表的折半搜索的判定树有序顺序表的折半搜索的判
26、定树 ( 10, 20, 30, 40, 50, 60 )1050= = = = = = =30204060ASLunsucc = (2*1+3*6)/7 = 20/7 ASLsucc = (1+2*2+ 3*3)/6 = 14/6 36折半搜索性能分析折半搜索性能分析n n若设若设 n = 2h-1，则描述折半搜索的判定树是则描述折半搜索的判定树是高度为高度为 h-1 的满二叉树的满二叉树。 2h = n+1, h = log2(n+1)。n n第第0层结点有层结点有1个个, 搜索第搜索第0层结点要比较层结点要比较1次次; 第第1层结点有层结点有2个个, 搜索第搜索第1层结点要比较层结点要比
27、较2次次; , 第第 i (0 i h) 层结点有层结点有 2i 个个, 搜索搜索第第 i 层结点要比较层结点要比较 i+1次次，。n n假定每个结点的搜索概率相等，即假定每个结点的搜索概率相等，即 pi = 1/n，则搜索成功的平均搜索长度为，则搜索成功的平均搜索长度为37可以用归纳法证明可以用归纳法证明这样这样38定义定义 二叉搜索树或者是一棵空树，或者是具有二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：下列性质的二叉树： 每个结点都有一个作为搜索依据的关键每个结点都有一个作为搜索依据的关键码码(key)，所有结点的关键码互不相同。，所有结点的关键码互不相同。 左子树左子树(如果存
28、在如果存在)上上所有结点的关键码所有结点的关键码都小于根结点的关键码都小于根结点的关键码。 右子树右子树(如果存在如果存在)上上所有结点的关键码所有结点的关键码都大于根结点的关键码都大于根结点的关键码。 左子树和右子树也是二叉搜索树。左子树和右子树也是二叉搜索树。二叉搜索树二叉搜索树 ( Binary Search Tree )39351545504025102030二叉搜索树例二叉搜索树例uu结点左子树上结点左子树上所有关键码小所有关键码小于结点关键码于结点关键码uu右子树上所有右子树上所有关键码大于结关键码大于结点关键码点关键码uu注意：若从根结点到某个叶结点有一条路注意：若从根结点到某个
29、叶结点有一条路径，路径左边的结点的关键码不一定小于径，路径左边的结点的关键码不一定小于路径上的结点的关键码。路径上的结点的关键码。40n 个结点的二叉搜索树的数目个结点的二叉搜索树的数目【例】【例】3 个结点的二叉搜索树个结点的二叉搜索树122133132123123123 132 213 231 312 32141 二叉搜索树的结构定义二叉搜索树的结构定义typedef char DataType; /树结点数据类型typedef struct node /搜索树结点定义 DataType data; struct node *leftChild, *rightChild; BstNode;
30、typedef BstNode *BST; /二叉搜索树定义 如果对一棵二叉搜索树进行中序遍历，可如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树。起来，所以也称二叉搜索树为二叉排序树。42 在二叉搜索树上进行搜索，在二叉搜索树上进行搜索，是一个从根结是一个从根结点开始，沿某一个分支逐层向下进行比较判点开始，沿某一个分支逐层向下进行比较判等的过程等的过程。它可以是一个递归的过程。它可以是一个递归的过程。二叉搜索树上的搜索二叉搜索树上的搜索351545504025102030搜索搜索45 搜索成功
31、搜索成功 搜索搜索28搜索失败搜索失败43n n假假设设想想要要在在二二叉叉搜搜索索树树中中搜搜索索关关键键码码为为x的元素，搜索过程从根结点开始。的元素，搜索过程从根结点开始。n n如如果果根根指指针针为为NULL，则则搜搜索索不不成成功功；否否则用给定值则用给定值 x 与根结点的关键码进行比较：与根结点的关键码进行比较：uu如如果果给给定定值值等等于于根根结结点点的的关关键键码码，则则搜搜索成功。索成功。 uu如如果果给给定定值值小小于于根根结结点点的的关关键键码码，则则继继续递归搜索根结点的左子树；续递归搜索根结点的左子树；uu否则。递归搜索根结点的右子树。否则。递归搜索根结点的右子树。
32、44uu搜索成功时检测指针停留在树中某个结点。搜索成功时检测指针停留在树中某个结点。uu搜索不成功时检测指针停留在某个外结点搜索不成功时检测指针停留在某个外结点（失败结点）。（失败结点）。3515455025102030搜索搜索22搜索搜索4545BstNode * Find ( BstNode *ptr, DataType x ) /二叉搜索树的迭代的搜索算法 if ( ptr != NULL ) BstNode * p = ptr; /从根搜索 while ( p != NULL ) if ( p-data = x ) return p; if ( p-data rightChild; /
33、右子树 else p = p-leftChild; /左子树 return NULL; /搜索失败 4635154550402510203028插入新结点插入新结点28二叉搜索树的插入二叉搜索树的插入n n每次结点的插入，都要从根结点出发搜索每次结点的插入，都要从根结点出发搜索插入位置，然后把插入位置，然后把 新结点作为叶结点新结点作为叶结点 插入。插入。n n为了向二叉搜索树为了向二叉搜索树 中插入一个新元素，中插入一个新元素， 必须先检查这个必须先检查这个元元 素是否在树中已经素是否在树中已经 存在存在。47n n在在插插入入之之前前，先先使使用用搜搜索索算算法法在在树树中中检检查查要插入
34、元素有还是没有。要插入元素有还是没有。uu搜搜索索成成功功: 树树中中已已有有这这个个元元素素,不不再再插插入。入。uu搜搜索索不不成成功功: 树树中中原原来来没没有有关关键键码码等等于于给给定定值值的的结结点点，把把新新元元素素加加到到搜搜索索操操作作停止的地方。停止的地方。 递归的二叉搜索树插入算法递归的二叉搜索树插入算法void Insert ( DataType x, BstNode * & ptr) /将新元素x插到以*ptr为根的二叉搜索树中48 if ( ptr = NULL ) /空二叉树 ptr = new BstNode; /创建结点 if ( ptr = NULL ) c
35、out “存储不足 data = x; ptr-leftChild = ptr-rightChild = NULL; else if ( x data ) /在左子树插入 Insert ( x, ptr-leftChild ); else if ( x ptr-data ) /在右子树插入 Insert ( x, ptr-rightChild );49 输入数据，建立二叉搜索树的过程输入数据，建立二叉搜索树的过程输入数据输入数据 53, 78, 65, 17, 87, 09, 81, 15 5353785378655378651753786587175378650917875378658117
36、8709537865151787098150void CreateBST ( BstNode *& T, DataType Refvalue ) /输入数据, 建立二叉搜索树。RefValue 是输入/结束标志。这个值应取不可能在输入序列中/出现的值, 例如输入序列的值都是正整数时, /取RefValue为0或负数。 dataType x; T = NULL; cin x; while ( x != RefValue ) if ( Find (T, x) = NULL ) Insert ( x, T ); cin x; 51 同样同样 3 个数据个数据 1, 2, 3 ，输入顺序不同，输入顺序
37、不同，建立起来的二叉搜索树的形态也不同。这直建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。接影响到二叉搜索树的搜索性能。 如果输入序列选得不好，会建立起一棵单如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达到最大。支树，使得二叉搜索树的高度达到最大。 2, 1, 3 1, 2, 3 1, 3, 2 2, 3, 1 3, 1, 2 3, 2, 1 12311113222332352二叉搜索树的删除二叉搜索树的删除n n在在二二叉叉搜搜索索树树中中删删除除一一个个结结点点时时，必必须须将将因因删删除除结结点点而而断断开开的的二二叉叉链链表表重重新新链链接接起起
38、来，同时确保二叉搜索树的性质不会失去。来，同时确保二叉搜索树的性质不会失去。n n为为保保证证在在删删除除后后树树的的搜搜索索性性能能不不至至于于降降低低，还还需要防止重新链接后树的高度增加需要防止重新链接后树的高度增加。n n删删除除叶叶结结点点，只只需需将将其其双双亲亲结结点点指指向向它它的指针清零，再释放它即可。的指针清零，再释放它即可。n n被被删删结结点点缺缺右右子子树树，可可以以拿拿它它的的左左子子女女结点顶替它的位置，再释放它。结点顶替它的位置，再释放它。53n n被被删删结结点点缺缺左左子子树树，可可以以拿拿它它的的右右子子女女结点顶替它的位置，再释放它。结点顶替它的位置，再释
39、放它。n n被被删删结结点点左左、右右子子树树都都存存在在，可可以以在在它它的的右右子子树树中中寻寻找找中中序序下下的的第第一一个个结结点点( (关关键键码码最最小小),),用用它它的的值值填填补补到到被被删删结结点点中中，再来处理这个结点的删除问题。再来处理这个结点的删除问题。5378651787092345删除45缺右子树, 用左子女顶替53786517870923548853788817940923删除78缺左子树, 用右子女顶替53948817092353788117940945删除78在右子树上找中序下第一个结点填补236553818817940945236555 二叉搜索树性能分析
40、二叉搜索树性能分析n n对于有对于有 n 个关键码的集合，其关键码有个关键码的集合，其关键码有 n! 种不同排列，可构成不同二叉搜索树有种不同排列，可构成不同二叉搜索树有 (棵棵)n n用树的搜索效率来评价这些二叉搜索树。用树的搜索效率来评价这些二叉搜索树。n n在树中增加失败结点在树中增加失败结点(外部结点外部结点), 它们是搜它们是搜索失败时到达的结点索失败时到达的结点, 物理上实际不存在。物理上实际不存在。n n增加了外部结点的二叉搜索树称为扩充二增加了外部结点的二叉搜索树称为扩充二叉搜索树。叉搜索树。56n n在扩充二叉搜索树中在扩充二叉搜索树中uu 表表示示内内部部结结点点，包包含含
41、了了关关键键码码集集合合中中的某一个关键码；的某一个关键码；uu 表表示示外外部部结结点点，代代表表各各关关键键码码间间隔隔中中的不在关键码集合中的关键码。的不在关键码集合中的关键码。n n在每两个外部结点间必存在一个内部结点在每两个外部结点间必存在一个内部结点。57n n例，已知关键码集合例，已知关键码集合 a1, a2, a3 = do, if, to ，对应搜索概率，对应搜索概率 p1, p2, p3, 在各搜索不在各搜索不成功间隔内搜索概率分别为成功间隔内搜索概率分别为 q0, q1, q2, q3。可能的二叉搜索树如下所示。可能的二叉搜索树如下所示。doiftodoiftoq0q1p
42、1q2p2q3p3q0q1q2q3p1p2p3(a)(b)58doifto扩充二叉搜索树扩充二叉搜索树q0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)59 一棵扩充二叉搜索树的一棵扩充二叉搜索树的搜索成功的平均搜搜索成功的平均搜索长度索长度ASLsucc可以定义为可以定义为该树所有内部结点该树所有内部结点上的权值上的权值pi与搜索该结点时所需的与搜索该结点时所需的关键码关键码比较次数比较次数ci (= li + 1)乘积之和：乘积之和： 搜索不成功的平均搜索长度搜索不成功的平均搜索长度ASLunsucc为树中为树中所
43、有外部结点上权值所有外部结点上权值qj与到达外部结点所需与到达外部结点所需关键码比较次数关键码比较次数cj(= lj)乘积之和：乘积之和：60(1) 相等搜索概率的情形相等搜索概率的情形 设树中所有内、外部结点的搜索概率都相等：设树中所有内、外部结点的搜索概率都相等： pi = 1/3, 1 i 3 qj = 1/4，0 j 3 图图(a)：ASLsucc = 1/3*3+1/3*2+1/3*1 = 6/3 = 2 ASLunsucc = 1/4*3*2+1/4*2+1/4*1 = 9/4 图图(b)：ASLsucc = 1/3*1+1/3*2*2 = 5/3 ASLunsucc = 1/4*
44、2*4 = 2 图图(c) 图图(e)：ASLsucc = 2, ASLunsucc = 9/4 图图(b)的情形所得的平均搜索长度最小。的情形所得的平均搜索长度最小。 61 一般把平均搜索长度达到最小的扩充二叉搜一般把平均搜索长度达到最小的扩充二叉搜索树称作最优二叉搜索树。索树称作最优二叉搜索树。 在在相等搜索概率的情形相等搜索概率的情形下，所有内部、外部下，所有内部、外部结点的搜索概率都相等，视它们的权值都为结点的搜索概率都相等，视它们的权值都为 1。同时，第同时，第 k 层有层有 2k 个结点，个结点，k = 0, 1, 。则有。则有 n 个内部结点的扩充二叉搜索树的内部路径长个内部结点
45、的扩充二叉搜索树的内部路径长度度 I 至少等于序列至少等于序列 62 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 的的前前 n 项项的和。的和。 因此，最优二叉搜索树的搜索成功的平均搜因此，最优二叉搜索树的搜索成功的平均搜索长度和搜索不成功的平均搜索长度分别为索长度和搜索不成功的平均搜索长度分别为:(2) 不相等搜索概率的情形不相等搜索概率的情形 设树中所有内、外部结点的搜索概率互不设树中所有内、外部结点的搜索概率互不相等。相等。63 p1 = 0.5, p2 = 0.1, p3 = 0.05 q0 = 0.15, q1 = 0.1,
46、q2 = 0.05, q3 = 0.05 doiftodoiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05q0=0.15 q1=0.1 q2=0.05q3= 0.05p1=0.5p2=0.1p3=0.05(a)(b)图图(a)：ASLsucc = 0.5*3+0.1*2+0.05*1 = 1.75， ASLunsucc = 0.15*3+0.1*3+0.05*2+0.05*1= 0.9。 ASL = ASLsucc + ASLunsucc = 2.65。64doifto q0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0
47、.05p3=0.05doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(d)(c)图图(c) : ASLsucc = 0.5*1+0.1*2+0.05*3 = 0.85,ASLunsucc = 0.15*1+0.1*2+0.05*3+0.05*3 = 0.75.ASL = 0.85+0.75 = 1.6图图(b) : ASL = 1.9; 图图(d) : ASL = 2.15; 65doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(e) 图图(e) : ASLsucc = 0.5*1
48、+0.05*2+0.1*3 = 0.9; ASLunsucc = 0.15*1+ 0.1*3+0.05*3+0.05*2 = 0.7; ASL = 0.9+0.7 = 1.6. 由此可知，图由此可知，图(c)和图和图(e)的情形下树的平均搜的情形下树的平均搜索长度达到最小，因此，图索长度达到最小，因此，图(c)和图和图(e)的情形的情形是最优二叉搜索树。是最优二叉搜索树。66AVL树树 高度平衡的二叉搜索树高度平衡的二叉搜索树高度平衡的二叉搜索树高度平衡的二叉搜索树AVL树的定义树的定义 一棵一棵AVL树或者是空树，或者是具有下列性树或者是空树，或者是具有下列性质的二叉搜索树：质的二叉搜索树：
49、它的左子树和右子树都是它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对树，且左子树和右子树的高度之差的绝对值不超过值不超过1。 高度不平衡高度不平衡 高度平衡高度平衡ABCABCDEDE67 结点的平衡因子结点的平衡因子balance (balance factor)n n每个结点附加一个数字每个结点附加一个数字, 给出该结点给出该结点右子右子树的高度减去左子树的高度树的高度减去左子树的高度所得的所得的高度差高度差,这个数字即为结点的平衡因子这个数字即为结点的平衡因子balance n nAVL树任一结点平衡因子只能取树任一结点平衡因子只能取 - -1, 0, 1n n如果一个
50、结点的平衡因子的绝对值大于如果一个结点的平衡因子的绝对值大于1,则这棵二叉搜索树就失去了平衡则这棵二叉搜索树就失去了平衡, 不再是不再是AVL树。树。n n如果一棵二叉搜索树是高度平衡的如果一棵二叉搜索树是高度平衡的, 且有且有 n 个结点，其高度可保持在个结点，其高度可保持在O(log2n),平均平均搜索长度也可保持在搜索长度也可保持在O(log2n)。68AVL树的结构定义树的结构定义typedef int DataType; /结点数据类型typedef struct node /AVL树结点定义 DataType data; /结点数据域 int balance; /结点平衡因子域 s
51、truct node *leftChild, *rightChild; /结点左、右子女指针域结点左、右子女指针域 AVLNode;typedef AVLNode * AVLTree; /AVL树69平衡化旋转平衡化旋转n n如果在一棵平衡的二叉搜索树中插入一个如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。此时必须调整树新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。的结构，使之平衡化。n n平衡化旋转有两类：平衡化旋转有两类：uu 单旋转单旋转 (左旋和右旋左旋和右旋)uu 双旋转双旋转 (左平衡和右平衡左平衡和右平衡)n n每插入一个新结点时每插入一个新结点时, AVL
52、 树中相关结点树中相关结点的平衡状态会发生改变。因此的平衡状态会发生改变。因此, 在插入一在插入一 个新结点后，需要个新结点后，需要从插入位置沿通向根的从插入位置沿通向根的路径回溯路径回溯，检查各结点的平衡因子检查各结点的平衡因子。70n n如果在某一结点发现高度不平衡，停止回如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。的路径取直接下两层的结点。n n如果这三个结点处于一条直线上，则采用如果这三个结点处于一条直线上，则采用单旋转进行平衡化单旋转进行平衡化。单旋转可按其方向分单旋转可按其方向分为左单旋转和右
53、单旋转为左单旋转和右单旋转, 其中一个是另一其中一个是另一 个的镜像，其方向与不平衡的形状相关。个的镜像，其方向与不平衡的形状相关。n n如果这三个结点处于一条折线上，则采用如果这三个结点处于一条折线上，则采用双旋转进行平衡化双旋转进行平衡化。双旋转分为先左后右双旋转分为先左后右和先右后左两类。和先右后左两类。71右单旋转右单旋转右单旋转右单旋转左单旋转左单旋转左单旋转左单旋转 左右双旋转左右双旋转左右双旋转左右双旋转右左双旋转右左双旋转右左双旋转右左双旋转左左单单旋旋转转 (RotateLeft )hhhACEBDhhh+1BACEDhhh+1CEABD+1+1+2+20 0+1+10 00
54、 072右单旋转右单旋转右单旋转右单旋转左单旋转左单旋转左单旋转左单旋转 左右双旋转左右双旋转左右双旋转左右双旋转右左双旋转右左双旋转右左双旋转右左双旋转左左单单旋旋转转 (RotateLeft )hhhACEBDhhh+1BACEDhhh+1CEABD+1+1+2+20 0+1+10 00 073n n在在子子树树E中中插插入入新新结结点点，该该子子树树高高度度增增1导导致结点致结点A的平衡因子变成的平衡因子变成+2，出现不平衡。，出现不平衡。n n沿沿插插入入路路径径检检查查三三个个结结点点A、C和和E。它它们们处于方向为处于方向为“”的直线上，需做左单旋转。的直线上，需做左单旋转。n n
55、以结点以结点C为旋转轴，让结点为旋转轴，让结点A反时针旋转。反时针旋转。右单旋转右单旋转 (RotateRight )n n在左子树在左子树D上插入新结点使其高度增上插入新结点使其高度增1，导，导致结点致结点A的平衡因子增到的平衡因子增到 - -2，造成不平衡。，造成不平衡。n n为使树恢复平衡，从为使树恢复平衡，从A沿插入路径连续取沿插入路径连续取3 个结点个结点A、B和和D，它们处于一条方向为，它们处于一条方向为“/”的直线上，需要做右单旋转。的直线上，需要做右单旋转。74hhhACEBDhh+1BACEDhhh+1CEABDn n以结点以结点B为旋转轴，将结点为旋转轴，将结点A顺时针旋转
56、。顺时针旋转。h0 00 00 0- - - -1 1- - - -1 1- - - -2 2先左后右双旋转先左后右双旋转 (RotationLeftRight)n n在在子子树树F或或G中中插插入入新新结结点点，该该子子树树的的高高度度增增1。结结点点A的的平平衡衡因因子子变变为为 - -2，发发生生了了不不平衡。平衡。75插入插入0 00 0- - - -1 1- - - -2 2+1+1- - - -1 1hhACEDh-1h-1hhAh-1hBCEDB左单左单左单左单旋转旋转旋转旋转FGFGn n从从结结点点A起起沿沿插插入入路路径径选选取取3个个结结点点A、B和和E，它它们们位位于于
57、一一条条形形如如“ ”的的折折线线上上，因此需要进行先左后右的双旋转。因此需要进行先左后右的双旋转。n n以结点以结点E为旋转轴，将结点为旋转轴，将结点B反时针旋转。反时针旋转。760 00 0- - - -2 20 0 0 00 0+1+1hhACED- - - -2 2h-1hhhAh-1hBCEDB右单右单右单右单旋转旋转旋转旋转FGFG77先右后左双旋转先右后左双旋转 (RotationRightLeft)n n右左双旋转是左右双旋转的镜像。右左双旋转是左右双旋转的镜像。n n在在子子树树F或或G中中插插入入新新结结点点，该该子子树树高高度度增增1。结结点点A的的平平衡衡因因子子变变为
58、为2，发发生生了了不不平平衡。衡。 n n从从结结点点A起起沿沿插插入入路路径径选选取取3个个结结点点A、C和和D，它它们们位位于于一一条条形形如如“ ”的的折折线线上上，需要进行先右后左的双旋转。需要进行先右后左的双旋转。78插入插入插入插入右右右右单单单单旋旋旋旋转转转转+1+10 00 00 0- - - -1 1+1+10 0hhACEDh-1BFGh-1+2+20 00 00 0hhACEhBFGh-1Dn n首首先先做做右右单单旋旋转转：以以结结点点D为为旋旋转转轴轴，将将结结点点C顺时针旋转，以顺时针旋转，以D代替原来代替原来C的位置。的位置。790 00 0+2+20 0 0
59、0- - - -1 10 0hhACE+ +2 2h-1hhhAh-1hBCEDB左单左单左单左单旋转旋转旋转旋转FGFGDn n再再做做左左单单旋旋转转：以以结结点点D为为旋旋转转轴轴，将将结结点点A反时针旋转，恢复树的平衡。反时针旋转，恢复树的平衡。80AVL树的插入树的插入n n在在向向一一棵棵本本来来是是高高度度平平衡衡的的AVL树树中中插插入入一一个个新新结结点点时时，如如果果树树中中某某个个结结点点的的平平衡衡因因子子的的绝绝对对值值 |balance| 1，则则出出现现了了不不平平衡，需要做平衡化处理。衡，需要做平衡化处理。n n算法算法从一棵空树开始从一棵空树开始，通过输入一系
60、列对，通过输入一系列对象关键码，象关键码，逐步建立逐步建立AVL树树。在插入新结。在插入新结点时点时使用平衡旋转方法进行平衡化处理使用平衡旋转方法进行平衡化处理。811616例，输入关键码序列为例，输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和调整过程如下。插入和调整过程如下。0 03163- - - -1 10 07 70 01 1- - - -2 2左右双旋左右双旋左右双旋左右双旋7 73160 00 00 07 73110 0- - - -1 11 17 7316161190 0- - - -1 1- - - -2 2右单旋右单旋右单旋右单旋3
61、7 71690 00 00 01 137 71126916110 01 11 12 22 28218180 03163- - - -1 10 0160 02 2右左双旋右左双旋右左双旋右左双旋7390 00 00 0182611- - - -1 1732616119- - - -1 1左单旋左单旋左单旋左单旋9716140 00 01 1711262691 11 1118315182 231816- - - -2 2左右双旋左右双旋左右双旋左右双旋730 00 00 0117149- - - -1 116150 01 1112626141 1- - - -2 29从空树开始的建树过程从空树开始
62、的建树过程84AVL树的高度树的高度n n设设在在新新结结点点插插入入前前AVL树树的的高高度度为为 h，结结点点个个数数为为 n，则则插插入入一一个个新新结结点点的的时时间间是是O(h)。对于。对于AVL树来说，树来说，h 多大？多大？n n设设 Nh 是是高高度度为为 h 的的AVL树树的的最最小小结结点点数数。根根的的一一棵棵子子树树的的高高度度为为 h- -1，另另一一棵棵子子树树的的高高度度为为 h- -2，这这两两棵棵子子树树也也是是高高度度平平衡衡的。因此有的。因此有uu N- -1 = 0 (空树空树)uu N0 = 1 (仅有根结点仅有根结点)uu Nh = Nh- -1 +
63、 Nh- -2 +1 , h 085n n可以证明可以证明, 对于对于 h 0, 有有 Nh = Fh+3 - -1 成立。成立。 其中，斐波那契数列其中，斐波那契数列 F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2, n 1时时n n有有 n 个结点的个结点的AVL树的高度不超过树的高度不超过 1.44*log2(n+1)- -1n n在在AVL树删除一个结点并做平衡化旋转所树删除一个结点并做平衡化旋转所需时间为需时间为 O(log2n)。n n二叉搜索树适合于组织在内存中的较小的二叉搜索树适合于组织在内存中的较小的索引索引(或目录或目录)。对于存放在外存中的较大。对于存放
64、在外存中的较大的文件系统，用二叉搜索树来组织索引不的文件系统，用二叉搜索树来组织索引不太合适。太合适。86赠送精美图标1、字体安装与、字体安装与设置置如果您对PPT模板中的字体风格不满意，可进行批量替换，一次性更改各页面字体。1.在“开始”选项卡中，点击“替换”按钮右侧箭头，选择“替换字体”。（如下图）2.在图“替换”下拉列表中选择要更改字体。（如下图）3.在“替换为”下拉列表中选择替换字体。4.点击“替换”按钮，完成。882、替、替换模板中的模板中的图片片模板中的图片展示页面，您可以根据需要替换这些图片，下面介绍两种替换方法。方法一：更改图片方法一：更改图片1.选中模版中的图片（有些图片与其
65、他对象进行了组合，选择时一定要选中图片本身，而不是组合）。2.单击鼠标右键，选择“更改图片”，选择要替换的图片。（如下图）注意：注意：为防止替换图片发生变形，请使用与原图长宽比例相同的图片。88PPT放映设置PPT放映场合不同，放映的要求也不同，下面将例举几种常用的放映设置方式。让让PPT停止自动播放停止自动播放1. 单击”幻灯片放映”选项卡，去除“使用计时”选项即可。让让PPT进行循环播放进行循环播放1.单击”幻灯片放映”选项卡中的“设置幻灯片放映”，在弹出对话框中勾选“循环放映，按ESC键终止”。89赠送精美图标1、字体安装与、字体安装与设置置如果您对PPT模板中的字体风格不满意，可进行批
66、量替换，一次性更改各页面字体。1.在“开始”选项卡中，点击“替换”按钮右侧箭头，选择“替换字体”。（如下图）2.在图“替换”下拉列表中选择要更改字体。（如下图）3.在“替换为”下拉列表中选择替换字体。4.点击“替换”按钮，完成。912、替、替换模板中的模板中的图片片模板中的图片展示页面，您可以根据需要替换这些图片，下面介绍两种替换方法。方法一：更改图片方法一：更改图片1.选中模版中的图片（有些图片与其他对象进行了组合，选择时一定要选中图片本身，而不是组合）。2.单击鼠标右键，选择“更改图片”，选择要替换的图片。（如下图）注意：注意：为防止替换图片发生变形，请使用与原图长宽比例相同的图片。91PPT放映设置PPT放映场合不同，放映的要求也不同，下面将例举几种常用的放映设置方式。让让PPT停止自动播放停止自动播放1. 单击”幻灯片放映”选项卡，去除“使用计时”选项即可。让让PPT进行循环播放进行循环播放1.单击”幻灯片放映”选项卡中的“设置幻灯片放映”，在弹出对话框中勾选“循环放映，按ESC键终止”。92
