《数据结构 二叉排序树.pptx》由会员分享，可在线阅读，更多相关《数据结构 二叉排序树.pptx（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、503080209010854035252388例如例如:是二叉排序树。是二叉排序树。66不不对对二叉排序树进行中序遍历，得到一个有序序列二叉排序树进行中序遍历，得到一个有序序列第1页/共50页1）若给定值）若给定值等于等于根结点的关键字，则根结点的关键字，则查找成功；查找成功；2）若给定值）若给定值小于小于根结点的关键字，则根结点的关键字，则继续在左子树上进行查找；继续在左子树上进行查找；3）若给定值）若给定值大于大于根结点的关键字，则根结点的关键字，则继续在右子树上进行查找。继续在右子树上进行查找。否则否则若二叉排序树若二叉排序树为空为空，则查找不成功；，则查找不成功；2.二叉排序树的查找
2、算法：二叉排序树的查找算法：第2页/共50页50308020908540358832例如:二叉排序树查找关键字=50,505035,503040355090,50809095,第3页/共50页二叉链表类型定义：二叉链表类型定义：typedef struct BiTNode KeyType key；/其它成员 struct BiTNode*lchild；struct BiTNode *rchild；BiTNode，*BiTree；第4页/共50页二叉排序树的查找：二叉排序树的查找：BiTree bstsrch(BiTree bt，KeyType k)/二叉排序树的存储结构为二叉链表，函数返回结点
3、的/关键字为k的指针，若查找不成功，返回空指针 if(t=NULL）return NULL；else if（btkey=k）return(bt)else if(btkey k)return（bstsrch(btrchild，k)）else return（bstsrch(btlchild，k)）；第5页/共50页3.二叉排序树的构造二叉排序树的构造特点：树结构在查找的过程中动态生成。特点：树结构在查找的过程中动态生成。每次插入的结点只能成为新的每次插入的结点只能成为新的叶子结点叶子结点例：关键字序列为 45，24，53，12，14，90 452412145390中序遍历:12,14,24,45,
4、53,90第6页/共50页(1)插入算法：插入算法：status ins_bstree(BiTree&bt，BiTree s)/将指针将指针s所指的结点插入到根指针为所指的结点插入到根指针为bt的二叉排序树中的二叉排序树中 if（bt=NULL）bt=s；/若若bt为空树，则为空树，则s为根为根 else if(skey btkey)ins_bstree(btlchild，s)；else ins_bstree(btrchild，s)；第7页/共50页(2)生成二叉排序树的算法：生成二叉排序树的算法：BiTree crt_bstree(BiTree&root)/输入一个关键字序列，生成一棵二叉排
5、序树的二叉链表结构输入一个关键字序列，生成一棵二叉排序树的二叉链表结构 root=NULL；read(x)；while(x 结束标志结束标志)s=(BiTree)malloc(sizeof(BiTNode)skey=x；/生成新结点生成新结点 slchild=NULL；srchild=NULL；ins_ bstree(root,s)；read(x)；return(root);/crt_bstree第8页/共50页(1)被删除的结点被删除的结点是叶子是叶子；(2)被删除的结点被删除的结点只有左子树只有左子树或者或者只有右子树；只有右子树；(3)被删除的结点被删除的结点既有左子树，也有右子树。既有
6、左子树，也有右子树。4.二叉排序树的删除算法二叉排序树的删除算法可分可分三种情况三种情况讨论：讨论：删除一个结点后，仍是二叉排序树。删除一个结点后，仍是二叉排序树。第9页/共50页50308020908540358832(1)被删除的结点是被删除的结点是叶子结点叶子结点例如例如:被删关键字被删关键字=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”第10页/共50页50308020908540358832(2)被删除结点被删除结点只有左子树只有左子树或者或者只有右子树只有右子树p只有左子树：f rchild=p lchild；p只有右子树：f rchild=p rc
7、hild；被删关键字被删关键字=4080第11页/共50页503080209085403588324040以其前驱替代之，然后再删除该前驱结点被删结点被删结点前驱结点前驱结点被删关键字被删关键字=50某结点的前驱一某结点的前驱一定在它的左子树定在它的左子树的最右下方的最右下方(3)被删除的结点被删除的结点既有左子树既有左子树，也有右子树也有右子树第12页/共50页5.二叉排序树的查找分析 比较次数=被查结点所在的层次数。二叉排序树的性能取决于树的形态，而二叉树的形态形态取决于插入结点的顺序取决于插入结点的顺序。关键字序列：(45，24，53，12，37，90)ASL=(1+2*2+3*3)/6
8、=14/6452412375390第13页/共50页例：关键字序列：例：关键字序列：(12,24,37,45,53,90)。其二叉排序树为：其二叉排序树为：ASL=(1+2+3+4+5+6)/6 =21/6122437455390 二叉排序树的性能取决于树二叉排序树的性能取决于树的形态，而二叉树的形态的形态，而二叉树的形态取决于取决于插入结点的顺序。插入结点的顺序。构造一棵接近理想平衡树的构造一棵接近理想平衡树的二叉排序树？二叉排序树？第14页/共50页 平衡二叉树平衡二叉树(AVLAVL树树)：对于每个结点，|左子树的深度左子树的深度 -右子树的深度右子树的深度|1|1 结点的平衡因子结点的
9、平衡因子=左子树的深度左子树的深度 -右子树的深度右子树的深度 AVL树中所有结点的平衡因子只有三种值：-1-1，0 0，1 1是平衡树是平衡树141253928635360501718730+1+1-1-1-100000000145392863536050171830+1+2-1-100000+1-1问：平衡树是理想平衡树吗？问：平衡树是理想平衡树吗？不是平衡树不是平衡树9.5 平衡二叉树平衡二叉树第15页/共50页如何检测二叉树是否失去平衡？如何检测二叉树是否失去平衡？当插入一个新结点时，重新计算从新插入的当插入一个新结点时，重新计算从新插入的结点到根结点的路径上所包含结点的平衡因结点到根
10、结点的路径上所包含结点的平衡因子（子（bfbf），如果某一结点的），如果某一结点的 bf bf 的绝对值超的绝对值超过过1 1，则二叉树失去平衡。，则二叉树失去平衡。0-1平衡平衡133713372401-2失去平衡失去平衡第16页/共50页如何使失去平衡的二叉树达到平衡？如何使失去平衡的二叉树达到平衡？需进行调整：四种调整类型：四种调整类型：设设x为插入结点，为插入结点，A结点为离插入结点结点为离插入结点x最近的最近的一个失衡结点：一个失衡结点：13372401-2243713第17页/共50页XA1BBLBRAR0LL型BLBBRAARABBLBRARXBAALBLBRXALABLBBRR
11、R型BAALBLBRX第18页/共50页XXABCLBLCRCAR01LR型BLBCLC CR AARABCLBLCRCAR-1XXABCLALCRCBR0-1XXRL型BACLALCRCBR-1XXALACLC CR BBR第19页/共50页例：按下列关键字的次序生成一棵AVL树。13，24，37，90，53，28，981313插入点插入点 插入后结果插入后结果 失衡原因失衡原因 调整调整2437RR型1324132437AB243713AB第20页/共50页53RL型90243713902437139053ABC-22453139037CBA第21页/共50页28RL型98RR型24531
12、39037BCA28-23753249028BAC133753249028AB-2139837902498281353第22页/共50页哈希表的基本思想:“一次一次”查找成功。查找成功。关键字集合映射函数 H地址空间 H(key)ASL的T(n)=O(1)。通常设定一个一维数组空间存储记录集合，则H(key)指示数组中的下标。称这个一维数组为哈希哈希(Hash)表表或或散列表散列表。称映射函数 H 为哈希函数哈希函数。H(key)为哈希地址哈希地址什么是哈希表什么是哈希表9.6 哈希表哈希表第23页/共50页 0 1 2 3 4 5 6 7 8 9 10 11 12H例：假定一个线性表为：A=
13、(18，75，60，43，54，90，46)假定选取的哈希函数为 hash3(key)=key%13若根据哈希函数把元素存储到哈希表H13中，则存储映象为：18756043549046第26页/共50页哈希表的哈希表的查找查找同插入元素一样。如从表中查找关键字为60的元素时，只要利用上面的函数计算出地址 H(60)=60%13=8查找不成功：查找不成功：查找61：H(61)=61%13=9 0 1 2 3 4 5 6 7 8 9 10 11 12H18756043549046第27页/共50页 如果如果 key1 key2，但但 H(key1)=H(key2)这种现象称为“冲突冲突”，称 ke
14、y1 和 key2 为同义词同义词。在实际应用中，应尽量选择均匀的哈希函数来减少冲突。冲突不能避免时，选定一个解决冲突的方法。第28页/共50页(1)装填因子装填因子(load factor):=(负载因子)m为hash表的长度，n为填入的记录数。越大，冲突的可能性越大。越大，冲突的可能性越大。越小，冲突的可能性会减小，但空间的利用率变低。越小，冲突的可能性会减小，但空间的利用率变低。为兼顾两者，为兼顾两者，在在 0.6，0.9范围内为宜。范围内为宜。(2)与采用的散列函数有关。与采用的散列函数有关。(3)与解决冲突的方法有关。与解决冲突的方法有关。方法选择的好坏也将减少或增加发生冲突的可能性
15、方法选择的好坏也将减少或增加发生冲突的可能性。发生冲突与下列三个因素有关：发生冲突与下列三个因素有关：第29页/共50页哈希函数的构造方法构造构造哈希哈希函数的目标：函数的目标：哈希哈希地址尽可能均匀分布在表空间上地址尽可能均匀分布在表空间上均均匀性好；匀性好；哈希哈希地址计算尽量简单。地址计算尽量简单。考虑因素：考虑因素：函数的复杂度；函数的复杂度；关键字长度与表长的关系；关键字长度与表长的关系；关键字分布情况；关键字分布情况；元素的查找频率。元素的查找频率。第30页/共50页例：1949年后出生的人口调查表，关键字是年份 年份 1949 1950 1951 人数 H(key)=key+(-
16、1948)此法仅适合于：此法仅适合于：地址集合的大小地址集合的大小=关键字集合的大小关键字集合的大小一、直接地址法一、直接地址法取关键字或关键字的某个线性函数值为哈希地址即：H(key)=key 或：H(key)=a*key+b其中，a，b为常数。第31页/共50页二、数字分析法二、数字分析法例如：有若干记录，关键字为 8 位十进制数，假设哈希表的表长为100,对关键字进行分析，取随机性较好的两位十进制数作为哈希地址。假设关键字集合中的每个关键字都是由 s 位数字组成(u1,u2,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。此方法仅适合于：此方法仅适合于：能预
17、先估计出预先估计出全体关键字的每一位上每一位上各种数字出现的频度数字出现的频度。第32页/共50页三、平方取中法三、平方取中法将将k平方后的中间几位取为哈希地址。平方后的中间几位取为哈希地址。位数由表长决定位数由表长决定例1：时间 8:40:02。m=84002,(m)2=705633604.例2：四位字母标识符的hash地址，地址空间为0 999用两位数字01 26表示对应的26个字母，如：AABB的内部代码：01010202关键字关键字 内部代码内部代码 (内部代码内部代码)2 H(key)KEYA 11052501 122157778355001 778KEYB 11052502 122
18、157800460004 800AKEY 01110525 001233265775625 265BKEY 02110525 004454315775625 315第33页/共50页四四、折叠法、折叠法将关键字分割成位数相同的几部分，然后将这几部分叠加，舍去进位作为哈希地址。适用于关键字位数很多，而且关键字中每一位上数字分布大致均匀的情况。移位叠加移位叠加：将分割之后的每一部分的最低位对齐，然后相加。间界叠加间界叠加：从一端向令一端沿分割界来回折叠，然后相加。此方法适合于此方法适合于:关键字的数字位数特别多。第34页/共50页例如：有一国际标准编号 0-4 4 2 2 0 5 8 6-4移位叠
19、加移位叠加 5 8 6 4 4 2 2 0 0 41 0 0 8 8H(key)=0088 5 8 6 4 0 2 2 4 0 4 6 0 9 2H(key)=6092间界叠加间界叠加第35页/共50页五、五、除留余数法除留余数法当关键字k为整数时，用关键字除以一个整数p 所得余数作为哈希的地址。H(key)=key%pp的选择很重要，若选得不好容易产生冲突。例如：p=10k，(k=1,2,）或p为偶数等由经验可知：由经验可知：取p为素数。p为不超过散列表的长度m的最大素数。第36页/共50页例如：可以让 p=m,并取m为素数。由于 的取值最好在 0.6，0.9，0.6 0.9 m 1.1*n
20、 m 1.7*n例：若 n=100，则 m 最好取113,127,139,143等素数。第37页/共50页设定哈希函数为设定哈希函数为:H(key)=Random(key)其中，其中，Random 为伪随机函数为伪随机函数六、六、随机数法随机数法 通常，此方法用于对长度不等的关键字构造哈希函数。第38页/共50页处理冲突的方法设hash表的长度为m，冲突是指 j=H(K)的位置已有记录，(0jm-1)“处理冲突”既为K另找一个“空”的地址。方法方法1:线性探测再散列线性探测再散列哈希表的存储结构：哈希表的存储结构：typedef struct KeyType key；/关键字成员 ；/其它成员
21、 elemtypetypedef elemtype hashtablem；第39页/共50页 哈希函数如下：H(key)=key%p 利用下面的公式求“下一个”地址。Hi=(H(key)+di)%m,di=1，2，3，m-1 例如：已知长度为13的哈希表，现有四个记录，其关键字分别为（19，70，33，18）。第40页/共50页 0 1 5 6 7 8 9 12 70 19 33 例如：已知长度为13的哈希表，现有四个记录，其关键字分别为（19，70，33，18）。哈希函数为 H(key)=key%13,则 H(19)=6，H(70)=5，H(33)=7，H(18)=5 用线性探测再散列方法解
22、决冲突：H1=(H(key)+d1)%13=(5+1)%13=6H2=(5+2)%13=7,H3=(5+3)%13=818第41页/共50页0 1 2 3 4 5 6 7 8 9 10例如例如:关键字集合 19,01,23,14,55,68,11,82,36 设定哈希函数：H(key)=key%11 (表长=11)191011232141551683若采用线性探测再散列线性探测再散列处理冲突116822365第42页/共50页在查找概率相同的情况下，在查找概率相同的情况下，查找成功时的ASLASLsucc=(1*4+2*2+3+5+6)/9=22/9若采用线性探测再散列线性探测再散列处理冲突0
23、 1 2 3 4 5 6 7 8 9 10191011232141551683116822365平均查找长度平均查找长度ASL：第43页/共50页线性探测再散列的优点优点：只要哈希表未满，总能找到一个空地址。只要哈希表未满，总能找到一个空地址。缺点：缺点：会产生二次聚集。会产生二次聚集。70 19 33 18 0 1 5 6 7 8 9 12下一个hash地址为5、6、7、8时，将争夺地址为9的空间第44页/共50页三、三、链地址法链地址法将哈希表的每一个单元存放一个指针存放一个指针，将所有将所有的同义词连成一个链表。的同义词连成一个链表。假设哈希地址在区间0.m-1上，则则哈希哈希表为表为一
24、个一个指针数组。第45页/共50页typedef struct node /定义链表中结点 KeyType key；其它成员；struct node*next；Node，*Nodeptr；typedef Nodeptr chainhashm；/定义指针数组第46页/共50页0123456 111982 68 5514 0136 23 ASLsucc=(61+22+3)/9=13/9例例1:关键字集合 19,01,23,14,55,68,11,82,36 哈希函数 H(key)=key%7 (表长=7)第47页/共50页例例2：有一组关键字BITE,EACH,BITTER,BROOM,AND,ALSO,HASH,EGGS，现以关键字中第一个字母在字母表中的位置为该关键字的哈希函数哈希函数值，链地址哈希表链地址哈希表如下：ASLsucc=(4*1+3*2+1*3)/8=13/8 1 AND ALSO 2 BITE BITTER BROOM 5 EACH EGGS 8 HASH 26第48页/共50页9.1(2)9.2、9.3、9.99.21(除留余数法构造哈希函数)第49页/共50页感谢您的观看！第50页/共50页