《DS06数据结构树二叉排序树》由会员分享，可在线阅读，更多相关《DS06数据结构树二叉排序树（30页珍藏版）》请在金锄头文库上搜索。
1、回顾：二分查找回顾：二分查找 当线性表中数据元素是当线性表中数据元素是按大小顺序排列存放按大小顺序排列存放时，可以采用时，可以采用二二分法分法 (折半查找折半查找)。v二分二分查找是每次在要找是每次在要查找的数据集合中取出中找的数据集合中取出中间元素关元素关键字字Kmid与要与要查找的关找的关键字字K进行比行比较，根据比，根据比较结果确定是否要果确定是否要进一步一步查找。找。v当当 Kmid=K ，查找成功；找成功；v当当 K Kmid，将在将在Kmid右半部分右半部分继续下一步下一步查找找v以此以此类推，每步的推，每步的查找范找范围都将是上一次的一半都将是上一次的一半。 优点：查找效率高优点
2、：查找效率高缺点：要求线性表，缺点：要求线性表，如果是进行如果是进行动态查找动态查找，即需要对线性表进行插入、，即需要对线性表进行插入、删除或排序操作，就必须移动大量的记录，当记录数很多时，这种移删除或排序操作，就必须移动大量的记录，当记录数很多时，这种移动的代价很大。动的代价很大。第44.4二叉搜索树631479510211811个元素的判定树个元素的判定树第4章 树 判定树的特点：判定树的特点：左子树左子树的值都比根结点的值都比根结点小小右子树右子树的值都比根结点的值都比根结点大大中序遍历中序遍历判定树得到的是一组有序判定树得到的是一组有序的序列的序列 11个元素的二分个元素的二分查找查找
3、判定树判定树4.4二叉搜索树能否根据以上特点，利用树型结构来动能否根据以上特点，利用树型结构来动态创建查找表呢？态创建查找表呢？第4章 树 4.4二叉搜索树【定义】【定义】一个二叉搜索树是一棵二叉树，它可以为空。如果不为空，一个二叉搜索树是一棵二叉树，它可以为空。如果不为空，它将满足以下性质：它将满足以下性质：1.非空非空左子树左子树的所有的所有键值小于其根结点键值小于其根结点的键值。的键值。2.非空非空右子树右子树的所有的所有键值大于其根结点键值大于其根结点的键值。的键值。3.左、右子树都是二叉搜索树左、右子树都是二叉搜索树。二叉搜索树二叉搜索树“二叉搜索树二叉搜索树（BST，Binary
4、Search Tree）”也称也称二叉排序树或二叉排序树或二叉查找树二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。，它是一种对排序和查找都很有用的特殊二叉树。18105207223015413350631479510211811个元素个元素二分查找二分查找的判定树的判定树 二叉搜索树的动态查找二叉搜索树的动态查找 二叉搜索树作为抽象数据结构的定义与普通二叉树相同，但操作集二叉搜索树作为抽象数据结构的定义与普通二叉树相同，但操作集中多了下列几个特别的函数：中多了下列几个特别的函数： Position Find( ElementType X, BinTree BST )：从二叉搜索树：从二
5、叉搜索树BST中查找元素中查找元素X，返回其所在结点的地址；，返回其所在结点的地址； Position FindMin( BinTree BST )：从二叉搜索树：从二叉搜索树BST中查找并返回最中查找并返回最小元素所在结点的地址；小元素所在结点的地址； Position FindMax( BinTree BST ) ：从二叉搜索树：从二叉搜索树BST中查找并返回中查找并返回最大元素所在结点的地址。最大元素所在结点的地址。第4章 树 4.4二叉搜索树 BinTree Insert( ElementType X, BinTree BST ) BinTree Delete( ElementType
6、 X, BinTree BST ) typedef Position BinTree 二叉搜索树的二叉搜索树的查找操作查找操作Find第4章 树 4.4二叉搜索树查找从根结点开始，如查找从根结点开始，如果树为空，返回果树为空，返回NULL，表示，表示未找到关键字为未找到关键字为X的结点。的结点。若若搜索树非空，则根结点搜索树非空，则根结点关键字和关键字和X进行比较进行比较，依据，依据比较结果，需要进行不同的处理：比较结果，需要进行不同的处理： 若若根结点键根结点键值值小于小于X，满足条件的结点将不会出现在它的，满足条件的结点将不会出现在它的左子树，接下来的搜索只需左子树，接下来的搜索只需在在右
7、子树右子树中进行；中进行； 如果如果根结点的键根结点的键值值大于大于X，接下来的搜索将，接下来的搜索将在在左子树中进左子树中进行；行； 若两者比较结果是若两者比较结果是相等相等，搜索完成，返回指向此结点的指，搜索完成，返回指向此结点的指针。针。 二叉搜索树的二叉搜索树的查找操作查找操作Find第4章 树 4.4二叉搜索树Position Find( ElementType X, BinTree BST )if( !BST ) return NULL; /查找失败查找失败if( X BST-Data ) return Find( X, BST-Right ); /在右子树中继续查找在右子树中继续
8、查找else if( X Data ) return Find( X, BST-Left ); /在左子树中继续查找在左子树中继续查找else /X = BST-Data return BST; /查找成功，返回找到结点的地址查找成功，返回找到结点的地址Position IterFind( ElementType X, BinTree BST ) while( BST ) if( X BST-Data ) BST = BST-Right; /向右子树中移动，继续查找向右子树中移动，继续查找 else if( X Data ) BST = BST-Left; /向左子树中移动，继续查找向左子树中
9、移动，继续查找 else / X = BST-Data return BST; /查找成功，返回结点的找到结点的地址查找成功，返回结点的找到结点的地址 return NULL; /查找失败查找失败 由于由于非递归函数非递归函数的执行的执行效率高效率高，一般采用非递归的迭代来实现查找。，一般采用非递归的迭代来实现查找。 很容易将很容易将“尾递归尾递归”函数改为函数改为迭代迭代函数函数第4章 树 4.4二叉搜索树 查找最大和最小元素查找最大和最小元素第4章 树 最大元素最大元素一定是在树的一定是在树的最右分枝的端结点最右分枝的端结点上上 最小元素最小元素一定是在树的一定是在树的最左分枝的端结点最左
10、分枝的端结点上上181015207229最左端点最左端点最右端点最右端点4.4二叉搜索树第4章 树 4.4二叉搜索树Position FindMax( BinTree BST ) if( !BST ) while( BST-Right ) BST = BST-Right; /沿右分支继续查找，直到最右叶结点沿右分支继续查找，直到最右叶结点 return BST; Position FindMin( BinTree BST ) if( !BST ) return NULL; /空的二叉搜索树，返回空的二叉搜索树，返回NULL else if( !BST-Left ) return BST; /找
11、到最左叶结点并返回找到最左叶结点并返回 else return FindMin( BST-Left ); /沿左分支继续查找沿左分支继续查找代码代码4.16 查找最小元素的查找最小元素的递归递归函数函数代码代码4.17 查找最查找最大大元素的元素的迭代迭代函数函数 二叉搜索树的插入二叉搜索树的插入第4章 树 4.4二叉搜索树分析将元素分析将元素X插入二叉搜索树插入二叉搜索树BST中关键是要找到元素应该插中关键是要找到元素应该插入的入的位置位置。位置的确定可以利用与查找函数。位置的确定可以利用与查找函数Find类似的方法，如果类似的方法，如果在树在树BST中找到中找到X，说明要插入的元素已存在，
12、可放弃插入操作。，说明要插入的元素已存在，可放弃插入操作。如果如果没找到没找到X，查找终止的位置就是，查找终止的位置就是X应插入的位置。应插入的位置。301541335035301541335035BinTree Insert( ElementType X, BinTree BST ) if( !BST ) /若原树为空，生成并返回一个结点的二叉搜索树若原树为空，生成并返回一个结点的二叉搜索树 BST = malloc(sizeof(struct TreeNode); BST-Data = X; BST-Left = BST-Right = NULL; else /开始找要插入元素的位置开始找
13、要插入元素的位置 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 二叉搜索树的插入算法二叉搜索树的插入算法【例【例4.8】以一年十二个月的英文缩写为键值，按从一月到十二月顺序】以一年十二个月的英文缩写为键值，按从一月到十二月顺序输入它们，即输入序列为输
14、入它们，即输入序列为（Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, Dec），将产生什么样的二叉搜索树？，将产生什么样的二叉搜索树？第4章 树 4.4二叉搜索树JanFebAprMarJunMayDecOctSeptJulyAugNov对于一个对于一个无序序列无序序列可以通过构造一棵可以通过构造一棵BST树而变成一个树而变成一个有有序序列序序列。由算法知，每次由算法知，每次插入的新结点都是插入的新结点都是BST树的叶子结点树的叶子结点，即，即在插入时不必移动其它结点，仅需修改某个结点的指针。在插入时不必移动其它结点，仅需修改某个
15、结点的指针。利用利用BST树的插入操作，可以从空树开始逐个插入每个结树的插入操作，可以从空树开始逐个插入每个结点，从而建立一棵点，从而建立一棵BST树树.第4章 树 4.4二叉搜索树 思考思考：用上述方法构造的含有：用上述方法构造的含有n个结点个结点BST树，其深度是多少？树，其深度是多少？深度：深度： 2n +1n第4章 树 4.5 平衡二叉树 例不同的插入次序，将导致不同的例不同的插入次序，将导致不同的深度深度。 (a) 按一月到十二月的按一月到十二月的自然月份序列自然月份序列输入所生成的；输入所生成的； (b) 输入序列为输入序列为（July, Feb, May, Mar, Aug, J
16、an, Apr, Jun, Oct, Sept, Nov, Dec） (c) 输入序列则是按输入序列则是按月份字符串月份字符串从小到大的顺序排列的。从小到大的顺序排列的。JanFebMarAprAugDecJuneJulyMaySeptOctNovJanFebMarAprAugDecJuneJulyMaySeptOctNovAprAugOctSept深度：深度： 2n +1n 二叉搜索树的二叉搜索树的删除删除第4章 树 4.4二叉搜索树 二叉搜索树的删除操作比其它操作更为复杂，有二叉搜索树的删除操作比其它操作更为复杂，有三种情况三种情况需要考虑：需要考虑： 要删除的是要删除的是叶结点叶结点可以
17、直接删除，然后再修改其父结点的指针。可以直接删除，然后再修改其父结点的指针。图图4.28 二叉搜索树叶结点的二叉搜索树叶结点的删除删除301541335035要删除结点要删除结点例：删除例：删除 35第4章 树 4.4二叉搜索树图图4.29 具有一个子树的结点删除具有一个子树的结点删除 要删除的结点要删除的结点只有一个孩子只有一个孩子结点结点删除之前需要改变其删除之前需要改变其父结点父结点的的指针，指针，指向指向要删除结点的要删除结点的孩子结点孩子结点。要删除结点要删除结点（只有一个孩子）（只有一个孩子）3015415035333015415035例：删除例：删除 33第4章 树 4.4二叉搜
18、索树图图4.30 具有两个子树的结点删除具有两个子树的结点删除 要删除的结点要删除的结点有左、右两棵子树有左、右两棵子树为了保持二叉搜索树的有序性，为了保持二叉搜索树的有序性，替代被删除的元素的位置可以有两种选择：一种是取其替代被删除的元素的位置可以有两种选择：一种是取其右子树中的最右子树中的最小元素小元素；另一个是取其；另一个是取其左子树中的最大元素左子树中的最大元素。41503015333534例：删除例：删除 411、取、取右子树右子树中的中的最小最小元素替代元素替代413534503015332、取、取左子树左子树中的中的最大最大元素替代元素替代BinTree Delete( Elem
19、entType 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, BST-Right); / 右子右子树递归删除除 else /找到要找到要删除的除的结点点 if( BST-Left & BST-Right ) /被被删除除结点有左右两个子点有左右两个子结点点 Tmp = FindM
20、in( BST-Right ); /在右子在右子树中找最小的元素填充中找最小的元素填充删除除结点点 BST-Data = Tmp-Data; BST-Right = Delete( BST-Data, BST-Right); /在在删除除结点的右子点的右子树中中删除最小元素除最小元素 else /被被删除除结点有一个或无子点有一个或无子结点点 Tmp = BST; if( !BST-Left ) / 有右孩子或无子有右孩子或无子结点点 BST = BST-Right; else if( !BST-Right ) /有左孩子或无子有左孩子或无子结点点 BST = BST-Left; free(
21、Tmp ); return BST;第4章 树 4.5 平衡二叉树二叉树排序树性能二叉树排序树性能 例不同的插入次序，将导致不同的例不同的插入次序，将导致不同的深度深度和平均查找长度和平均查找长度ASL。 (a) 按一月到十二月的按一月到十二月的自然月份序列自然月份序列输入所生成的；输入所生成的； (b) 输入序列为输入序列为（July, Feb, May, Mar, Aug, Jan, Apr, Jun, Oct, Sept, Nov, Dec） (c) 输入序列则是按输入序列则是按月份字符串月份字符串从小到大的顺序排列的。从小到大的顺序排列的。JanFebMarAprAugDecJuneJ
22、ulyMaySeptOctNovJanFebMarAprAugDecJuneJulyMaySeptOctNovAprAugOctSept 查找查找二叉搜索树二叉搜索树（BST）的时间复杂度（）的时间复杂度（最坏情况下最坏情况下）用查找过程中的比较次数来衡量，它取决于树的用查找过程中的比较次数来衡量，它取决于树的深度深度。第4章 树 4.5 平衡二叉树JanFebMarAprAugDecJuneJulyMaySeptOctNovJanFebMarAprAugDecJuneJulyMaySeptOctNovAprAugOctSept 按按ASL的定义，可以分别计算出三棵二叉搜索树的的定义，可以分别
23、计算出三棵二叉搜索树的平均查找长度平均查找长度：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；对于一棵具有对于一棵具有n个结点的树来说，其二叉排序树的个结点的树来说，其二叉排序树的形态形态对对于查找效率至关重要，或者说，一棵二叉排序树不一定就于查找效率至关重要，或者说，一棵二叉排序树不一定就能提高查找的速度，而是要看这棵树的形态。能提高查找的速度，而是要看这棵树的形态。思考思考：如何构造形态：如何构造形
24、态“好好”的二叉树？的二叉树？第4章 树 4.5 平衡二叉树 平衡二叉树的定义平衡二叉树的定义第4章 树 4.5 平衡二叉树【定义】对于二叉树中任一结点【定义】对于二叉树中任一结点T，其，其“平衡因子平衡因子（Balance Factor，简称，简称BF）”定义为定义为BF(T) = hL-hR，其中，其中hL和和hR分别为分别为T的左、右子树的高度。的左、右子树的高度。 “平衡二叉树平衡二叉树（Balanced Binary Tree）”又称为又称为“AVL树树” 。 AVL树或者是一棵空树，或者是具有下列性质的非空树或者是一棵空树，或者是具有下列性质的非空二叉搜索树二叉搜索树：“任一结点左
25、、右子树高度差的绝对值不超过任一结点左、右子树高度差的绝对值不超过1。”即即|BF(T) | 1。645819272581644563217MarMar0 1MayMay0NovNov012May0 1Nov0 02 1Mar0 00首个不平衡的首个不平衡的“发现者发现者”是是Mar（未必是根结点未必是根结点），它是调整起点位置。），它是调整起点位置。而而“麻烦结点麻烦结点”Nov 在发现者在发现者右右子树的子树的右边右边，因而叫，因而叫 RR 插入插入，需要，需要RR 旋转（右单旋）；旋转（右单旋）；一般情况一般情况（设（设A是首个发现者）是首个发现者）的调整方式如下的调整方式如下:A1B0
26、BLBRALRR插入插入RR旋转旋转A2B1BLBRALBLB0AALBR0右单旋右单旋 平衡二叉树的调整平衡二叉树的调整第4章 树 4.5 AVL树AugMay0 1Nov0 02 1Mar0 11Aug0AprApr0122LL旋转旋转左单旋左单旋May0 1Nov0 02 1Aug0 111Mar00Apr0 首个首个“发现者发现者”是是Mar； “麻烦结点麻烦结点”Apr 在发现者在发现者左左子树的子树的左边左边，因而，因而叫叫 LL 插入；插入；一般情况（设一般情况（设A是首个发现者）是首个发现者）的调整方式如下的调整方式如下:A1B0BRBLARLL插入插入A2B1BRBLARLL
27、旋转旋转B0AARBLBR0第4章 树 4.5 AVL树May0 1Nov0 02 1Aug0 111Mar00Apr0JanJan0112LR旋转Mar0 1May0 12 1Aug0 101Jan00Apr0Nov0首个首个“发现者发现者”是是May； “麻烦结点麻烦结点”Jan在在左左子树的子树的右边右边，因而叫，因而叫 LR 插入插入；一般情况（设；一般情况（设A是首个发现者）是首个发现者）的调整如下的调整如下:A1B0BLARC0CRCLLR插入A2B1BLARC1CRCLORLR旋转BLARC0A1 or 0CRB0 or 1CLOR左左-右双旋右双旋第4章 树 4.5 AVL树D
28、ecJulyMar0 1May0 12 1Aug0 111Jan0Apr0Nov0July0Dec0FebFeb01122RL旋转July0Dec0 1Aug0 121Jan0 101Feb00Apr0Mar0 1May0 12 1 1Nov0一般情况一般情况调整如下调整如下:A1B0BRALC0CLCRRL插入A2B1BRALC1CLCRORRL旋转BRALC0A0 or 1CLB1 or 0CROR第4章 树 4.5 AVL树右右-左双旋左双旋July0Dec0 1Aug0 121Jan0 101Feb00Apr0Mar0 1May0 12 1 1Nov0JuneOctSeptJune01
29、112Nov0Dec0 1Aug121Feb01July1Apr0Mar0May1June0Jan0Oct01211Oct0Dec0 1Aug121Feb01July1Apr0Mar0Nov0June0Jan0May0Sept01111注意：有时候插入元素即便注意：有时候插入元素即便不需要调整结构，也可能需要重新计算不需要调整结构，也可能需要重新计算一些平衡因子。一些平衡因子。第4章 树 4.5 AVL树LL、RR、LR、RL四种不平衡情况及其它们的旋转调整算四种不平衡情况及其它们的旋转调整算法程序，见教材法程序，见教材p.131代码代码4.20-代码代码4.22最后一个问题最后一个问题: 查
30、找和插入的时间复杂性查找和插入的时间复杂性 Tp = O( h ) 其中其中 h 是二叉树的高度，是二叉树的高度，但是，但是， h = ?第4章 树 4.5 AVL树设设 nh 高度为高度为h的平衡二叉树的最小结点数的平衡二叉树的最小结点数. 二叉树看起二叉树看起来应该是如下结构形式：来应该是如下结构形式： 斐波那契序列斐波那契序列: F0 = 1, F1 = 1, Fi = Fi 1 + Fi 2 for i 1 nh = Fh+2 1, for h 0斐波那契序列的理论值是：斐波那契序列的理论值是：第4章 树 4.5 AVL树Ah2h1Ah2h1或或 nh = nh 1 + nh 2 + 1 nh = nh 1 + nh 2 + 1第4章 树 4.5 AVL树设设 nh 是高度为是高度为h的平衡二叉树的的平衡二叉树的最小结点数最小结点数. h nh Fh0 0 01 1 12 2 13 4 24 7 35 12 56 20 87 33 138 54 219 nh = Fh+2 1, （对（对 h 0） 给定结点数为给定结点数为 n的的AVL树的树的最大高度为最大高度为O(log2n)！ 从而保证了从而保证了AVL树的树的查找时间性能为查找时间性能为O(log2n)！
