DS06数据结构树-二叉排序树ppt课件

1、回顾：二分查找回顾：二分查找 当线性表中数据元素是当线性表中数据元素是按大小按大小顺序顺序排列存放排列存放时时，可以可以采用采用二二分法分法 (折半查找折半查找)。v二分查找是每次在要查找的数据集合中取出中间元素关键字二分查找是每次在要查找的数据集合中取出中间元素关键字Kmid与要查找的关键字与要查找的关键字K进行比较，根据比较结果确定是否要进行比较，根据比较结果确定是否要进一步查找。进一步查找。v 当当 Kmid=K ，查找成功；，查找成功；v 当当 K Kmid，将在将在Kmid右半部分右半部分继续下一步查找继续下一步查找v以此类推，每步的以此类推，每步的查找范围都将是上一次的一半查找范围

2、都将是上一次的一半。 优点：查找效率高优点：查找效率高缺点：要求线性表缺点：要求线性表有序有序，如果是进行如果是进行动态查找动态查找，即需要对线性表进行，即需要对线性表进行插入、删除或排序操作，就必须移动大量的记录，当记录数很多时，插入、删除或排序操作，就必须移动大量的记录，当记录数很多时，这种移动的代价很大。这种移动的代价很大。第4章 树 4.4二叉搜索树1；.631479510211811个元素的判定树个元素的判定树第4章 树 判定树的特点：判定树的特点： 左子树左子树的值都比根结点的值都比根结点小小 右子树右子树的值都比根结点的值都比根结点大大 中序遍历中序遍历判定树得到的是一组有序判定

3、树得到的是一组有序的序列的序列vv 11个元素的二分个元素的二分查找查找判定树判定树4.4二叉搜索树能否根据以上特点，利用树型结构来动能否根据以上特点，利用树型结构来动态创建查找表呢？态创建查找表呢？2；.第4章 树 4.4二叉搜索树【定义定义】一个二叉搜索树是一棵二叉树，它可以为空。如果不为空，一个二叉搜索树是一棵二叉树，它可以为空。如果不为空，它将满足以下性质：它将满足以下性质：1. 非空非空左子树左子树的所有的所有键值小于其根结点键值小于其根结点的键值。的键值。2. 非空非空右子树右子树的所有的所有键值大于其根结点键值大于其根结点的键值。的键值。3. 左、右子树都是二叉搜索树左、右子树都

4、是二叉搜索树。vv二叉搜索树二叉搜索树“二叉搜索树二叉搜索树（BST，Binary Search Tree）”也称也称二叉排序树二叉排序树或二叉查找树或二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。，它是一种对排序和查找都很有用的特殊二叉树。18105207223015413350631479510211811个元素个元素二分查找二分查找的判定树的判定树3；.vv 二叉搜索树的动态查找二叉搜索树的动态查找 二叉搜索树作为抽象数据结构的定义与普通二叉树相同，但操作集二叉搜索树作为抽象数据结构的定义与普通二叉树相同，但操作集中多了下列几个特别的函数：中多了下列几个特别的函数： Positi

5、on Find( ElementType X, BinTree BST )：从二叉搜索树：从二叉搜索树BST中查找元素中查找元素X，返回其所在结点的地址；，返回其所在结点的地址； Position FindMin( BinTree BST )：从二叉搜索树：从二叉搜索树BST中查找并返回中查找并返回最小元素所在结点的地址；最小元素所在结点的地址； Position FindMax( BinTree BST ) ：从二叉搜索树：从二叉搜索树BST中查找并返回中查找并返回最大元素所在结点的地址。最大元素所在结点的地址。第4章 树 4.4二叉搜索树 BinTree Insert( ElementTy

6、pe X, BinTree BST ) BinTree Delete( ElementType X, BinTree BST ) typedef Position BinTree4；.vv 二叉搜索树的二叉搜索树的查找操作查找操作Find第4章 树 4.4二叉搜索树 查找从根结点开始，如查找从根结点开始，如果树为空，返回果树为空，返回NULL，表示，表示未找到关键字为未找到关键字为X的结点。的结点。 若若搜索树非空，则根结点搜索树非空，则根结点关键字和关键字和X进行比较进行比较，依据，依据比较结果，需要进行不同的处理：比较结果，需要进行不同的处理： 若若根结点键根结点键值值小于小于X，满足条件

7、的结点将不会出现在它的，满足条件的结点将不会出现在它的左子树，接下来的搜索只需左子树，接下来的搜索只需在在右子树右子树中进行；中进行； 如果如果根结点的键根结点的键值值大于大于X，接下来的搜索将，接下来的搜索将在在左子树中进左子树中进行；行； 若两者比较结果是若两者比较结果是相等相等，搜索完成，返回指向此结点的指，搜索完成，返回指向此结点的指针。针。5；.vv 二叉搜索树的二叉搜索树的查找操作查找操作Find第4章 树 4.4二叉搜索树Position Find( ElementType X, BinTree BST )if( !BST ) return NULL; /查找失败查找失败if(

8、X BST-Data ) return Find( X, BST-Right ); /在右子树中继续查找在右子树中继续查找else if( X Data ) return Find( X, BST-Left ); /在左子树中继续查找在左子树中继续查找else /X = BST-Data return BST; /查找成功，返回找到结点的地址查找成功，返回找到结点的地址6；.Position IterFind( ElementType X, BinTree BST ) while( BST ) if( X BST-Data ) BST = BST-Right; /向右子树中移动，继续查找向右子

9、树中移动，继续查找 else if( X Data ) BST = BST-Left; /向左子树中移动，继续查找向左子树中移动，继续查找 else / X = BST-Data return BST; /查找成功，返回结点的找到结点的地址查找成功，返回结点的找到结点的地址 return NULL; /查找失败查找失败 由于由于非递归函数非递归函数的执行的执行效率高效率高，一般采用非递归的迭代来实现查找。，一般采用非递归的迭代来实现查找。 很容易将很容易将“尾递归尾递归”函数改为函数改为迭代迭代函数函数第4章 树 4.4二叉搜索树7；.vv 查找最大和最小元素查找最大和最小元素第4章 树 最大

10、元素最大元素一定是在一定是在树的树的最右分枝的端结点最右分枝的端结点上上 最小元素最小元素一定是在树的一定是在树的最左分枝的端结点最左分枝的端结点上上181015207229最左端点最左端点最右端点最右端点4.4二叉搜索树8；.第4章 树 4.4二叉搜索树Position FindMax( BinTree BST ) if( !BST ) while( BST-Right ) BST = BST-Right; /沿右分支继续查找，直到最右叶结点沿右分支继续查找，直到最右叶结点 return BST; Position FindMin( BinTree BST ) if( !BST ) retu

11、rn NULL; /空的二叉搜索树，返回空的二叉搜索树，返回NULL else if( !BST-Left ) return BST; /找到最左叶结点并返回找到最左叶结点并返回 else return FindMin( BST-Left ); /沿左分支继续查找沿左分支继续查找代码代码4.16 查找最小元素的查找最小元素的递归递归函函数数代码代码4.17 查找最查找最大大元素的元素的迭代迭代函数函数9；.vv 二叉搜索树的插入二叉搜索树的插入第4章 树 4.4二叉搜索树分析分析将元素将元素X插入二叉搜索树插入二叉搜索树BST中关键是要找到元素应该插中关键是要找到元素应该插入的入的位置位置。位

12、置的确定可以利用与查找函数。位置的确定可以利用与查找函数Find类似的方法，如果类似的方法，如果在树在树BST中找到中找到X，说明要插入的元素已存在，可放弃插入操作。，说明要插入的元素已存在，可放弃插入操作。如果如果没找到没找到X，查找终止的位置就是，查找终止的位置就是X应插入的位置。应插入的位置。30154133503530154133503510；.BinTree Insert( ElementType X, BinTree BST ) if( !BST ) /若原树为空，生成并返回一个结点的二叉搜索树若原树为空，生成并返回一个结点的二叉搜索树 BST = malloc(sizeof(st

13、ruct TreeNode); BST-Data = X; BST-Left = BST-Right = NULL; else /开始找要插入元素的位置开始找要插入元素的位置 if( X Data ) BST-Left = Insert( X, BST-Left); /递归插入左子树递归插入左子树 else if( X BST-Data ) BST-Right = Insert( X, BST-Right); /递归插入右子树递归插入右子树 / else X已经存在，什么都不做已经存在，什么都不做 return BST;第4章 树 4.4二叉搜索树代码代码4.18 二叉搜索树的插入算法二叉搜索

14、树的插入算法11；.【例例4.8】以一年十二个月的英文缩写为键值，按从一月到十二月顺序以一年十二个月的英文缩写为键值，按从一月到十二月顺序输入它们，即输入序列为输入它们，即输入序列为（Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, Dec），将产生什么样的二叉搜索树？，将产生什么样的二叉搜索树？第4章 树 4.4二叉搜索树JanFebAprMarJunMayDecOctSeptJulyAugNov12；. 对于一个对于一个无序序列无序序列可以通过构造一棵可以通过构造一棵BST树而变成一个树而变成一个有有序序列序序列。 由算法知，每

15、次由算法知，每次插入的新结点都是插入的新结点都是BST树的叶子结点树的叶子结点，即，即在插入时不必移动其它结点，仅需修改某个结点的指针。在插入时不必移动其它结点，仅需修改某个结点的指针。 利用利用BST树的插入操作，可以从空树开始逐个插入每个结树的插入操作，可以从空树开始逐个插入每个结点，从而建立一棵点，从而建立一棵BST树树.第4章 树 4.4二叉搜索树 思考思考：用上述方法构造的含有：用上述方法构造的含有n个结点个结点BST树，其深度是多少？树，其深度是多少？深度：深度： 2n +1n13；.第4章 树 4.5 平衡二叉树 例例不同的插入次序，将导致不同的不同的插入次序，将导致不同的深度深

16、度。 (a) 按一月到十二月的按一月到十二月的自然月份序列自然月份序列输入所生成的；输入所生成的； (b) 输入序列为输入序列为（July, Feb, May, Mar, Aug, Jan, Apr, Jun, Oct, Sept, Nov, Dec） (c) 输入序列则是按输入序列则是按月份字符串月份字符串从小到大的顺序排列的。从小到大的顺序排列的。JanFebMarAprAugDecJuneJulyMaySeptOctNovJanFebMarAprAugDecJuneJulyMaySeptOctNovAprAugOctSept深度：深度： 2n +1n14；.vv 二叉搜索树的二叉搜索树的

17、删除删除第4章 树 4.4二叉搜索树 二叉搜索树的删除操作比其它操作更为复杂，有二叉搜索树的删除操作比其它操作更为复杂，有三种情况三种情况需要考虑：需要考虑： 要删除的是要删除的是叶结点叶结点可以直接删除，然后再修改其父结点的指针。可以直接删除，然后再修改其父结点的指针。图图4.28 二叉搜索树叶结点的二叉搜索树叶结点的删除删除301541335035要删除结点要删除结点例例：删除：删除 3515；.第4章 树 4.4二叉搜索树图图4.29 具有一个子树的结点删除具有一个子树的结点删除 要删除的结点要删除的结点只有一个孩子只有一个孩子结点结点删除之前需要改变其删除之前需要改变其父结点父结点的的

18、指针，指针，指向指向要删除结点的要删除结点的孩子结点孩子结点。要删除结点要删除结点（只有一个孩子）（只有一个孩子）3015415035333015415035例例：删除：删除 3316；.第4章 树 4.4二叉搜索树图图4.30 具有两个子树的结点删除具有两个子树的结点删除 要删除的结点要删除的结点有左、右两棵子树有左、右两棵子树为了保持二叉搜索树的有序性，为了保持二叉搜索树的有序性，替代被删除的元素的位置可以有两种选择：一种是取其替代被删除的元素的位置可以有两种选择：一种是取其右子树中的最右子树中的最小元素小元素；另一个是取其；另一个是取其左子树中的最大元素左子树中的最大元素。4150301

19、5333534例例：删除：删除 411、取、取右子树右子树中的中的最小最小元素替代元素替代413534503015332、取、取左子树左子树中的中的最大最大元素替代元素替代17；.BinTree Delete( ElementType X, BinTree BST ) Position Tmp; if( !BST ) printf(要删除的元素未找到要删除的元素未找到); else if( X Data ) BST-Left = Delete( X, BST-Left); / 左子树递归删除左子树递归删除 else if( X BST-Data ) BST-Right = Delete( X,

20、 BST-Right); / 右子树递归删除右子树递归删除 else /找到要删除的结点找到要删除的结点 if( BST-Left & BST-Right ) /被删除结点有左右两个子结点被删除结点有左右两个子结点 Tmp = FindMin( BST-Right ); /在右子树中找最小的元素填充删除结点在右子树中找最小的元素填充删除结点 BST-Data = Tmp-Data; BST-Right = Delete( BST-Data, BST-Right); /在删除结点的右子树中删除最小元素在删除结点的右子树中删除最小元素 else /被删除结点有一个或无子结点被删除结点有一个

21、或无子结点 Tmp = BST; if( !BST-Left ) / 有右孩子或无子结点有右孩子或无子结点 BST = BST-Right; else if( !BST-Right ) /有左孩子或无子结点有左孩子或无子结点 BST = BST-Left; free( Tmp ); return BST;18；.第4章 树 4.5 平衡二叉树vv二叉树二叉树排序树性能排序树性能 例例不同的插入次序，将导致不同的不同的插入次序，将导致不同的深度深度和平均查找长度和平均查找长度ASL。 (a) 按一月到十二月的按一月到十二月的自然月份序列自然月份序列输入所生成的；输入所生成的； (b) 输入序列为

22、输入序列为（July, Feb, May, Mar, Aug, Jan, Apr, Jun, Oct, Sept, Nov, Dec） (c) 输入序列则是按输入序列则是按月份字符串月份字符串从小到大的顺序排列的。从小到大的顺序排列的。JanFebMarAprAugDecJuneJulyMaySeptOctNovJanFebMarAprAugDecJuneJulyMaySeptOctNovAprAugOctSept 查找查找二叉搜索树二叉搜索树（BST）的时间复杂度（）的时间复杂度（最坏情况下最坏情况下）用查找过程中的比较次数来衡量，它取决于树的用查找过程中的比较次数来衡量，它取决于树的深度深

23、度。19；.第4章 树 4.5 平衡二叉树JanFebMarAprAugDecJuneJulyMaySeptOctNovJanFebMarAprAugDecJuneJulyMaySeptOctNovAprAugOctSept 按按ASL的定义，可以分别计算出三棵二叉搜索树的的定义，可以分别计算出三棵二叉搜索树的平均平均查找查找长度长度：ASL(a)=(1+22+33+43+52+61)/12 = 3.5；ASL(b)=(1+22+34+45)/12 = 3.0；ASL(c)=(1+21+31+41+51+61+71+81+91+101+111+121)/12 = 6.5；20；. 对于一棵具有

24、对于一棵具有n个结点的树来说，其二叉排序树的个结点的树来说，其二叉排序树的形态形态对对于查找效率至关重要，或者说，一棵二叉排序树不一定就于查找效率至关重要，或者说，一棵二叉排序树不一定就能提高查找的速度，而是要看这棵树的形态。能提高查找的速度，而是要看这棵树的形态。思考思考：如何构造形态：如何构造形态“好好”的二叉树？的二叉树？第4章 树 4.5 平衡二叉树21；.vv 平衡二叉树的定义平衡二叉树的定义第4章 树 4.5 平衡二叉树【定义定义】对于二叉树中任一结点对于二叉树中任一结点T，其，其“平衡因子平衡因子（Balance Factor，简，简称称BF）”定义为定义为BF(T) = hL-

25、hR，其中，其中hL和和hR分别为分别为T的左、右子树的高度。的左、右子树的高度。 “平衡二叉树平衡二叉树（Balanced Binary Tree）”又称为又称为“AVL树树” 。 AVL树或者是一棵空树，或者是具有下列性质的非空树或者是一棵空树，或者是具有下列性质的非空二叉搜索树二叉搜索树：“任一结点左、右子树高度差的绝对值不超过任一结点左、右子树高度差的绝对值不超过1。”即即|BF(T) | 1。64581927258164456321722；.MarMar0 1MayMay0NovNov012May0 1Nov0 02 1Mar0 00首个不平衡的首个不平衡的“发现者发现者”是是Mar

26、（未必是根结点未必是根结点），它是调整起点位置。），它是调整起点位置。而而“麻烦结点麻烦结点”Nov 在发现者在发现者右右子树的子树的右边右边，因而叫，因而叫 RR 插入插入，需要，需要RR 旋转（右单旋）；旋转（右单旋）；一般情况一般情况（设（设A是首个发现者）是首个发现者）的调整方式如下的调整方式如下:A1B0BLBRALRR插入插入RR旋转旋转A2B1BLBRALBLB0AALBR0右单旋右单旋vv 平衡二叉树的调整平衡二叉树的调整第4章 树 4.5 AVL树23；.AugMay0 1Nov0 02 1Mar0 11Aug0AprApr0122LL旋转旋转左单旋左单旋May0 1Nov0

27、 02 1Aug0 111Mar00Apr0 首个首个“发现者发现者”是是Mar； “麻烦结点麻烦结点”Apr 在发现者在发现者左左子树的子树的左边左边，因而叫因而叫 LL 插入；插入；一般情况（设一般情况（设A是首个发现者）是首个发现者）的调整方式如下的调整方式如下:A1B0BRBLARLL插入插入A2B1BRBLARLL旋转旋转B0AARBLBR0第4章 树 4.5 AVL树24；.May0 1Nov0 02 1Aug0 111Mar00Apr0JanJan0112LR旋转Mar0 1May0 12 1Aug0 101Jan00Apr0Nov0首个首个“发现者发现者”是是May； “麻烦结

28、点麻烦结点”Jan在在左左子树的子树的右边右边，因而叫，因而叫 LR 插入插入；一般情况（设；一般情况（设A是首个发现者）是首个发现者）的调整如下的调整如下:A1B0BLARC0CRCLLR插入A2B1BLARC1CRCLORLR旋转BLARC0A1 or 0CRB0 or 1CLOR左左-右双旋右双旋第4章 树 4.5 AVL树25；.DecJulyMar0 1May0 12 1Aug0 111Jan0Apr0Nov0July0Dec0FebFeb01122RL旋转July0Dec0 1Aug0 121Jan0 101Feb00Apr0Mar0 1May0 12 1 1Nov0一般情况一般情况调整如下调整如下:A1B0BRALC0CLCRRL插入A2B1BRALC1CLCRORRL旋转BRALC0A0 or 1CLB1 or 0CROR第4章 树 4.5 AVL树右右-左双旋左双旋26；.July0Dec0 1Aug0 121Jan0 101Feb0