二叉排序树课件

1、2022/7/20查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素关键字是数据元素中某个数据项的值，它可以标识一个数据元素查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值基本概念:2022/7/20查找成功在查找表中找到关键字值等于给定值的记录。查找失败对查找表常进行的操作：查询某个“特定的”数据元素是否在查找表中检索某个“特定的”数据元素的各种属性在查找表中插入一个数据元素从查找表中删除某个元素静态查找表：对查找表只前两种“查找

2、”操作动态查找表：对查找表要进行后两种“查找”操作2022/7/20一 顺序查找（线性查找）查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较算法描述i例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464监视哨iiii比较次数=5比较次数：查找第n个元素： 1查找第n-1个元素：2.查找第1个元素： n查找第i个元素： n+1-i查找失败： n+18.1 静态查找表2022/7/20typedef int KeyType;typedef float ElemType;typedef struct KeyType

3、 key; /记录的关键字 ElemType info; /记录的其他信息JD;int seqsrch(JD r, int n, KeyType k) /设置监视哨的算法 int i=n; r0.key=k; while(ri.key!=k) i-; return(i);2022/7/20int seqsrch(JD r,int n,KeyType k) /未设置监视哨 int i=0; while (i=n) return(-1); else return(i);2022/7/20顺序查找方法的ASL2022/7/20二 折半查找查找过程：每次将待查记录所在区间缩小一半适用条件：顺序存储结构

4、查找表按关键字排序算法实现设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k=rmid.key，查找成功若krmid.key，则low=mid+1重复上述操作，直至lowhigh时，查找失败2022/7/20算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92

5、lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid2022/7/20例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10

6、 115 13 19 21 37 56 64 75 80 88 92lowhighmid2022/7/201 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 926指在查找表中的位置r6，查找范围为r1r1110指在查找表中的位置r10，查找范围为r10r11注：判定树的形态只与表记录个数n有关，与记录的内容无关。2022/7/20int BinSearch(JD r,int n,KeyT

7、ype k) int low,high,mid,found; low=1; high=n; found=0; while (lowrmid.key) low=mid+1; else if(khith) return -1; else mid=(low+high)/2; if (k=rmid.key) return mid; else if (krmid.key) return (BinSearch(r,mid+1,high,k); else return (BinSearch(r,low,mid-1,k); 2022/7/208.2 动态查找表 动态查找表的特点：表结构本身是在查找过程中动态生

8、成的，即对于给定值key，若表中存在其关键字等于key的纪录，则返回查找成功，否则插入关键字等于key的纪录。 本节主要介绍二叉排序树和平衡二叉树的有关概念和查找分析2022/7/20定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值它的左、右子树也分别为二叉排序树二叉排序树的插入插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子二叉排序树生成：从

9、空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树二叉排序树2022/7/20插入算法例 10， 18， 3， 8， 12， 2， 7， 31010181018310183810183812101838122101838122710183812273中序遍历二叉排序树可得到一个关键字的有序序列2022/7/20二叉排序树的删除要删除二叉排序树中的p结点，分三种情况：p为叶子结点，只需修改p双亲f的指针f-lchild=NULL f-rchild=NULLp只有左子树或右子树p只有左子树，用p的左孩子代替p (1)(2)p只有右子树，用p的右孩子代替p (3)(4)p左、右子树均非空

10、沿p左子树的根C的右子树分支找到S，S的右子树为空，将S的左子树成为S的双亲Q的右子树，用S取代p (5)若C无右子树，用C取代p (6)2022/7/20SQPLP中序遍历：Q S PL PSQPL中序遍历：Q S PL(2)SPPLQ中序遍历：PL P S QSPLQ中序遍历：PL S Q(1)2022/7/20中序遍历：P PR S QSPRQ中序遍历：PR S Q(3)SPPRQ中序遍历：Q S P PRSQPR中序遍历：Q S PR(4)SQPRP2022/7/20FPCPRCLQQLSSL中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：CL C

11、 QL Q SL S PR F(5)FPCPRCL中序遍历：CL C P PR FFCPRCL中序遍历：CL C PR F(6)2022/7/20删除算法例805012060110150557053删除508060120110150557053删除60805512011015053701042581354删除1084255134删除58425413二叉排序树的查找分析在二叉树上查找一个关键字的过程，恰是走了一条从根节点到该节点的路径，因此与给定值比较的次数不超过树的深度。对相同数的集合构成的二叉排序树因为根节点不同而造成平均查找长度不同。452453371293ASL=(1+2*2+3*3)/

12、6=14/6122437455393ASL=(1+2+3+4+5+6)/6=21/62022/7/20含有n个节点的二叉排序树的平均查找长度和树的形态有关。若插入的关键字有序时，构成的二叉排序树蜕变成单支树，其平均查找长度为(n+1)/2。最好的情况为二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2n成正比。 要想使任何的关键字的集合构成的二叉排序树的平均查找长度均达到log2n数量级，需对二叉排序树进行“平衡化”处理，成为平衡二叉树。2022/7/20 平衡二叉树或者是一棵空树，或者具有以下性质：左子树和右子树的深度之差的绝对值不超过1；它的左子树和右子树又分别是平衡二叉树。

13、二叉树节点的平衡因子BF：该节点的左子树深度减去右子树的深度。 BFBalance Factor所以平衡二叉树的平衡因子只可能为-1，0，1。否则不能成为平衡二叉树。平衡二叉树AVL树2022/7/20下面举例说明构成平衡二叉树的过程:有关键字序列（13，24，37，90，53），生成平衡二叉树： 空（a）013024-113037-124-2130370240132022/7/20-137-124013090(1)(2)-237-224013190053-237-224013-153090(3)053-124013090037(4)2022/7/20若插入结点使平衡二叉树失去平衡的最小子树根

14、结点指针为a, 则:由于在*a的左子树根节点的左子树上插入接点，*a的平衡因子 由1增到2，致使以*a为根的子树失去平衡，则需要进行一次向右 的顺时针旋转操作。(LL型)由于在*a的右子树根节点的右子树上插入接点，*a的平衡因子 由-1变为-2，致使以*a为根的子树失去平衡，需要进行一次向左 的逆时针旋转操作。(RR型)由于在*a的左子树根节点的右子树上插入接点，*a的平衡因子 由1变为2，致使以*a为根的子树失去平衡，需要进行两次旋转操 作（先左后右）。(LR型)由于在*a的右子树根节点的左子树上插入接点，*a的平衡因子 由-1变为-2，致使以*a为根的子树失去平衡，需要进行两次旋转 操作（

15、先右后左）。(RL型)调整的原则：一是满足平衡二叉树的要求； 二是保持排序二叉树的性质2022/7/20 (1) LL型调整LL型调整规则将A的左子女B提升为新二叉树的根；原来的根A连同其右子树向右下旋转成为B的右子树；B的原右子树作为A的左子树。 2022/7/20 (2) RR型调整RR型调整规则：将A的右子女B提升为新二叉树的根；原来的根A连同其左子树向左下旋转成为B的左子树；B的原左子树作为A的右子树。 2022/7/20 (3) LR型调整LR型调整规则：设C为A的左子女的右子女，将A的孙子结点C提升为新二叉树的根；原C的父结点B连同其左子树向左下旋转成为新根C的左子树，原C的左子树

16、成为B的右子树；原根A连同其右子树向右下旋转成为新根C的右子树，原C的右子树成为A的左子树。 2022/7/20 (4) RL型调整 RL型调整规则：设C为A的右子女的左子女，将A的孙子结点C提升为新二叉树的根，原来C的父结点B连同其右子树向右下旋转成为新根C的右子树，C的原右子树成为B的左子树；原来的根A连同其左子树向左下旋转成为新根C的左子树，原来C的左子树成为A的右子树。 2022/7/20如：输入关键字序列16,3,7,11,9,26,18,14,15,给出构造一棵AVL树的步骤。2022/7/202022/7/201、B_树定义： 一棵m阶的B_树，或为空树，或为满足下列特征的m叉树

17、：树中每个节点至多有m棵子树；（m=3)若根不是叶子(非单根树)，则最少有两棵子树，最多有m棵子树；除根之外的所有非终端节点最少有m/2棵子树，最多m棵子树；所有的非终端节点包含下列信息数据 (n,A0,K1,A1,K2,A2,Kn,An)Ki为关键字，且Ki352、B_树的查找2022/7/20查找47的过程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF4347782022/7/20查找47的过程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.ta

18、bcefghFFFFFFFFFFFF查找成功2022/7/20查找23的过程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF23182022/7/20查找23的过程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF23272022/7/20查找23的过程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF查找失败2022/7/2

19、03、B_树的插入100h45a53 90e24b3 12c37d50f61 70gbt2022/7/20插入303 12c45a53 90e24b30 37d50f61 70g100hbt2022/7/20插入2645a53 90e24b3 12c26 30 37d50f61 70g100hbt2022/7/20插入2645a53 90e24 30b3 12c37d50f61 70g100hbt26d2022/7/20插入8545a53 90e24 30b3 12c37d50f61 70 85g100hbt26d2022/7/20bt插入8545a53 70 90e24 30b3 12c37

20、d50f61 g100h26d85 g2022/7/20100hbt插入8545 70a53e24 30b3 12c37d50f61 g26d85 g90e2022/7/20bt插入745 70a53e7 24 30b3c37d50f61 g100h26d85 g12c90e2022/7/20插入7bt24 45 70a53e7b3c37d50f61 g100h26d85 g12c30b90e2022/7/20bt插入745m53e7b3c37d50f61 g100h26d85 g12c30b90e70a24a2022/7/20B+树B树是B_树的一种变形，一棵m阶B树和B树的区别：有n棵子树

21、的节点中含有n个关键字。所有的叶子节点中包含了全部关键字的信息，及指向这些关 键字的指针，且叶子节点本身以关键字的大小自小到大顺序 连接。所有的非终端节点可以看成是索引部分，节点中仅包含有其 子树中的最大(或最小)关键字。2022/7/20如：一棵3阶B+树59 9772 9715 44 5910 1521 37 4451 5963 7285 91 97bt叶子节点有序子树根的最大值子树根的最大值2022/7/208.4 哈希查找Hash查找基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法定义哈希函数记录的关键字与记录的存储

22、地址之间建立的一种对应关系哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素addr(ai)是ai的存储地址ki是ai的关键字关键字集合存储地址集合hash2022/7/20哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址。该表叫哈希查找又叫散列查找，利用哈希函数进行查找的过程叫例1 30个地区的各民族人口统计表编号 地区别 总人口 汉族 回族.1 北京2 上海.以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H

23、(Beijing)=2 H(Shanghai)=19 H(Shenyang)=192022/7/20例2: 对于一组关键字序列 (25，74，36，15，40，29，82，19，65，33，57，47，50), 选取函数 h(key)key%13 建立记录与其在查找表中存储位置之间的关系，可得到如下表所示的一张查找表：当对该表检索时，只需用给定关键字值k通过这个函数计算出地址，以该地址从检索表的对应位置取出记录的有关信息即可，不需要进行关键字值的比较操作。如检索key=57的记录，通过h(57)=57%13=5知关键字值为57的记录在检索表的存储位置5处，从而得到关键字值为57的记录的有关信息

24、。 2022/7/20从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可冲突：key1key2，但H(key1)=H(key2)的现象叫同义词：具有相同函数值的两个关键字，叫该哈希函数的哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法产生散列冲突相关的主要因素： 装填因子：散列表中已存入元素n与散列表空间大小m的比。 装填因子越小，产生的冲突就越小；否则，就越大。 散列函数 散列函数选择适当，使散列地址尽可能均匀地分布在散列空间中，产生的冲突就少；否则，就大。 冲突的解决方法20

25、22/7/20哈希函数的构造方法直接定址法方法：取关键字或关键字的某个线性函数作哈希地址。 H(key)=key 或 H(key)=akey+b特点：直接定址法所得地址集合与关键字集合大小相等，不会发生冲突。若有冲突，说明关键字错误。实际中能用这种哈希函数的情况很少适用于关键字分布基本连续的情况。若不连续，空号较多，将造成存储空间的严重浪费。2022/7/20数字分析法方法：对关键字进行分析，取关键字的若干位或其组合作哈希地址适用于关键字位数比哈希地址位数大，且关键字事先知道的情况例： 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8 1 3 4 6 5 3 28 1 3 7 2

26、2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析： 位只取8 位只取1 位只取3、4 位只取2、7、5 位数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作哈希地址2022/7/20平方取中法方法：取关键字平方后中间几位作哈希地址适用于不知道全部关键字情况折叠法方法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字

27、位数很多，且每一位上数字分布大致均匀情况例 关键字为 ：0442205864，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加2022/7/20除留余数法方法：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pm特点简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词随机数法方法：取关键字的随机函数值作哈希地址。 H(key)=random(key)适用于关键字长度不等的情况选取哈希函数，考

28、虑以下因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率2022/7/20处理冲突的方法开放定址法方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中。 Hi = (H(key)+di) MOD m，i=1,2,k(km-1) 其中：H(key)哈希函数 m哈希表表长 di增量序列分类线性探测再散列：di=1,2,3,m-1 H1 =H(key) Hj =(Hj-1+1) MOD m j=2,3,二次探测再散列：di=1,-1,2,-2,3,k(km/2) H1=H(key) H2j=

29、(H1+j2) MOD m H2j+1=(H1-j2) MOD m j=1,2,3,伪随机探测再散：di=伪随机数序列 H1=H(key) Hj= (H1+R) MOD m2022/7/20例 表长为11的哈希表中已填有关键字为17，60，29的记录， H(key)=key MOD 11,现有第4个记录，其关键字为38， 按三种处理冲突的方法，将它填入表中0 1 2 3 4 5 6 7 8 9 1060 17 29(1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突 38

30、(2) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5-1) MOD 11=4 不冲突38(3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则： H1=(5+9) MOD 11=3 不冲突382022/7/20再哈希法方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址。 Hi=Rhi(key) i=1,2,k 其中：Rhi不同的哈希函数特点：计算时间增加链地址法方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针2022/7/20例： 已知一组关键字 (19，14，23，1，68，20，84，27

31、，55，11，10，79) 哈希函数为： H(key)=key MOD 13 用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 141277968551984202310112022/7/20哈希查找过程及分析哈希查找过程给定k值计算H(k)此地址为空关键字=k查找失败查找成功按处理冲突方法计算HiYNYN2022/7/20哈希查找分析哈希查找过程仍是一个给定值与关键字进行比较的过程评价哈希查找效率仍要用ASL哈希查找过程与给定值进行比较的关键字的个数取决于：哈希函数处理冲突的方法哈希表的装填因子=表中填入的记录数/哈希表长度例 已知一组关键字(19,14,23,1,

32、68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等(1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD mH(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2*1+3*3+4*1+1*9)/12 =2.514 168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1 冲突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 冲突，H1=(6+1)MOD16