二分查找及算法设计.ppt

8 查 找,二分查找及算法设计二叉排序树及构造平衡二叉树的查找、插入及旋转hash表的构造及查找,8.1 二分(折半）查找,一、二分查找的先决条件 表中结点按关键字有序，且顺序（一维数组）存储。二、二分法思想：取中，比较（1）求有序表的中间位置mid（2）若rmid.key=k，查找成功；若rmid.keyk，在左子表中继续进行二 分查找；若rmid.keyk，则在右子表中继续进 行二分查找。,12,21,30,35,38,40,48,55,56,60,64,1 2 3 4 5 6 7 8 9 10 11,i=1,j=11,二分法查找示例（1）k=35,Krm:在左半部分继续查找。,m=(i+j)/2=6。,i=1,j=m-1=5,m=(i+j)/2=3。,Krm:在右半部分继续查找。,i=m+1=4,j=5,m=(i+j)/2=4。,rm=k:查找成功。,m=(i+j)/2=6。,12,21,30,35,38,40,48,55,56,60,64,i=1,j=11,m=(i+j)/2=6。rmk:在左半部分继续查找。i=7,j=m-1=8,m=(i+j)/2=7。rmk:在左半部分继续查找。i=8,j=m-1=7,ij:查找失败,二分法查找示例（2）k=50,1 2 3 4 5 6 7 8 9 10 11,三、存储结构 key info typedef struct keytype key;.elemtype;,k1,k2,k3,kn,0123n,四、算法描述,int Search_bin(elemtype r,int n,keytype k)/r1.rn 是按key排序的n个元素，在表中查找 k i=1;j=n;while(i=j)mid=(i+j)/2;/取中 if(k=rmid.key)return(mid);/查找成功 else if(k rmid.key)j=mid-1;/在左半部分继续查找 else i=mid+1;/在右半部分继续查找 return(0);/k不在该有序表中。rj.keykri.key,五、二分查找判定树（以11个结点为例）,12,21,30,35,38,40,48,55,56,60,64,1 2 3 4 5 6 7 8 9 10 11,平均查找长度ASL=（1+2*2+4*3+4*4）/11=3二分查找算法的时间复杂度T(n)=O(log2n),45,53,100,61,12,3,90,78,37,24,8.2二叉排序树,一、二叉排序树的定义二叉排序树或空，或对于二叉树中的每一个结点，若它的左子树非空，则左子树上所有结点的关键字值均小于该结点的值。若根的右子树非空，则右子树上的所有结点的关键字值均大于该结点的值。,二、二叉排序树的特点 中序遍历得一有（升）序序列。,查找方法：若根结点的关键字值等于查找的关键字，查找成功。否则，若小于根结点的关键字值，查其左子树。若大于根结点的关键字的值，则查其右子树。在左右子树上的操作类似。,45,53,100,61,12,3,90,78,37,24,三、二叉排序树的查找,例8.1:查找k=24,45,53,100,61,12,3,90,78,37,24,四、二叉排序树的插入,若二叉树为空。则生成根结点。若二叉树非空（1）首先进行查找，找出被插结点的 父结点。（2）判断被插结点是其父结点的左、右儿 子，将其作为叶子结点插入。,60,例8.2:在二叉排序树中插入60,45,53,100,61,12,3,90,78,37,24,五、二叉排序树的构造,若二叉树为空。则生成根结点。若二叉树非空（1）首先执行查找，找到被插结点的 父亲结点。（2）判断被插结点是其父亲结点的左、右儿子，将其结点插入。,例8.3：以 45,53,12,37,24,100,3,61,90,78 构造二叉排序树。,53,93,37,24,45,12,一、什么是平衡二叉树或空树，或是具有下列性质的二叉排序树。它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。,.平衡二叉树(AVL树),二、平衡因子（Balance Factor)左子树的深度-右子树的深度 即平衡二叉树中每一结点的平衡因子为：0，1，-1。,0,-1,0,0,0,0,三、平衡二叉树的查找即二叉排序树查找,45,90,100,78,12,3,61,37,24,0,1,0,0,0,0,1,-1,-1,插入 15,45,90,100,78,12,3,61,37,24,0,1,0,0,0,1,1,-2,0,15,2,（1）找插入位置；（2）插入结点；（3）若插入后导致不平衡，则进行调整。,四、平衡的二叉树的插入,45,90,100,78,12,3,61,37,24,0,1,0,0,1,1,0,LL旋转,45,90,100,78,12,3,61,24,37,0,-1,0,0,0,0,1,-2,0,50,0,15,2,0,15,0,0,（1）找插入位置；（2）插入结点；（3）若插入后导致不平衡，则进行调整。,四、平衡的二叉树的插入,一、hash函数&hash表 设计1个hash函数，计算 Hash函数，其函数值恰好是 key 在 hash 表中的地址hash(key)=i(0.m-1)二、hash查找的特点基于计算,8.4 hash(散列)查找,例8.3 hash查找示例。人口统计表。在右表中查找 1989年出生的人数。查找方法（1）：顺序查找查找方法（2）：二分查找查找方法（3）：hash 查找 hash(key)=key-1949=1989-1949=40,除留余数法 hash(key)=key%p pm(表长)关键问题是:如何选取 p?p 应为不大于m 的最大质数例：设表长m=8，16，32，64，128，1001 则 p=7，13，31，61，127，1001,三、hash函数的构造方法,若对于不同的键值k1和k2,且k1 k2,但 hash(k1)=hash(k2)，即具有相同的散列地址，这种现象称为冲突。称 k1、k2称为同义词。例8.4 key=3,15,20,24，m=5（表长），hash(k)=k%5 hash(15)=0 hash(20)=0 产生冲突。,四、冲突的概念与处理方法,冲突的处理链地址法,将具有相同散列地址的记录都存储在同一个线性链表中。例8.5 key=14,1,68,27,55,23,11,10,19,20,79,84,hash(key)=key%13,用链地址法解决冲突,构造hash表。hash(14)=hash(1)=hash(27)=hash(79)=1hash(68)=hash(55)=3hash(19)=hash(84)=6hash(20)=7hash(23)=hash(10)=10hash(11)=11,1,27,79,hash(key)=key%13 hash(14)=1hash(1)=1hash(68)=3hash(27)=1hash(55)=3hash(23)=10hash(11)=11hash(10)=10hash(19)=6 hash(20)=7hash(79)=1 hash(84)=6,14,68,19,20,23,11,55,84,10,ASL=（6*1+4*2+1*3+1*4）/12=21/12,对给定的关键值 key，若地址d(即hash(key)=d)的单元发生冲突，则依次探查下述地址单元：d+1,d+2,.,m-1,0,1,d-1直到找到一个开放的地址（空位置）止，将发生冲突的键值放到该地址中。设增量函数为d(i)=1,2,3,m-1,m表长 i:为探测次数。,冲突的处理线性探测法,例8.6以14,1,68,27,55,23,11,10,19,20,79,84,构造 hash表。hash表长度为17,hash(key)=key%17。用线性探测法解决冲突。,hash 表：,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,14,68,1,55,27,20,19,84,79,11,23,10,比较次数：3 3ASL=(1*10+3*2)/12=16/12,