二分查找及算法设计

8查找二分查找及算法设计二叉排序树及构造平衡二叉树的查找、插入及旋转hash表的构造及查找8.1二分(折半）查找一、二分查找的先决条件表中结点按关键字有序，且顺序（一维数组）存储。二、二分法思想：取中，比较（1）求有序表的中间位置mid（2）若r[mid].key==k，查找成功；若r[mid].keyk，在左子表中继续进行二分查找；若r[mid].keyk，则在右子表中继续进行二分查找。12213035384048555660641234567891011i=1,j=11,二分法查找示例（1）k=35Kr[m]:在左半部分继续查找。m=(i+j)/2=6。i=1,j=m-1=5,m=(i+j)/2=3。Kr[m]:在右半部分继续查找。i=m+1=4,j=5m=(i+j)/2=4。r[m]==k:查找成功。m=(i+j)/2=6。1221303538404855566064i=1,j=11,m=(i+j)/2=6。r[m]k:在右半部分继续查找。i=m+1=7,j=11,m=(i+j)/2=9。r[m]k:在左半部分继续查找。i=7,j=m-1=8,m=(i+j)/2=7。r[m]k:在右半部分继续查找。i=m+1=8,j=8,m=(i+j)/2=8。r[m]k:在左半部分继续查找。i=8,j=m-1=7,ij:查找失败二分法查找示例（2）k=501234567891011三、存储结构keyinfotypedefstruct{keytypekey;………….}elemtype;k1k2k3…………kn0123n四、算法描述intSearch_bin(elemtyper[],intn,keytypek){//r[1]..r[n]是按key排序的n个元素，在表中查找ki=1;j=n;while(i=j){mid=(i+j)/2;//取中if(k==r[mid].key)return(mid);//查找成功elseif(kr[mid].key)j=mid-1;//在左半部分继续查找elsei=mid+1;//在右半部分继续查找}return(0);//k不在该有序表中。r[j].keykr[i].key}五、二分查找判定树（以11个结点为例）12213035384048555660641234567891011平均查找长度ASL=（1+2*2+4*3+4*4）/11=3二分查找算法的时间复杂度T(n)=O(log2n)455310061123907837248.2二叉排序树一、二叉排序树的定义二叉排序树或空，或对于二叉树中的每一个结点，若它的左子树非空，则左子树上所有结点的关键字值均小于该结点的值。若根的右子树非空，则右子树上的所有结点的关键字值均大于该结点的值。二、二叉排序树的特点中序遍历得一有（升）序序列。查找方法：若根结点的关键字值等于查找的关键字，查找成功。否则，若小于根结点的关键字值，查其左子树。若大于根结点的关键字的值，则查其右子树。在左右子树上的操作类似。45531006112390783724三、二叉排序树的查找例8.1:查找k=2445531006112390783724四、二叉排序树的插入若二叉树为空。则生成根结点。若二叉树非空（1）首先进行查找，找出被插结点的父结点。（2）判断被插结点是其父结点的左、右儿子，将其作为叶子结点插入。60例8.2:在二叉排序树中插入6045531006112390783724五、二叉排序树的构造若二叉树为空。则生成根结点。若二叉树非空（1）首先执行查找，找到被插结点的父亲结点。（2）判断被插结点是其父亲结点的左、右儿子，将其结点插入。例8.3：以{45,53,12,37,24,100,3,61,90,78}构造二叉排序树。539337244512一、什么是平衡二叉树或空树，或是具有下列性质的二叉排序树。它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。８.３平衡二叉树(AVL树)二、平衡因子（BalanceFactor)左子树的深度-右子树的深度即平衡二叉树中每一结点的平衡因子为：0，1，-1。0-10000三、平衡二叉树的查找——即二叉排序树查找4590100781236137240100001-1-1插入154590100781236137240100011-20152（1）找插入位置；（2）插入结点；（3）若插入后导致不平衡，则进行调整。四、平衡的二叉树的插入4590100781236137240100110LL旋转4590100781236124370-100001-2050015201500（1）找插入位置；（2）插入结点；（3）若插入后导致不平衡，则进行调整。四、平衡的二叉树的插入一、hash函数&hash表设计1个hash函数，计算Hash函数，其函数值恰好是key在hash表中的地址hash(key)=i(0..m-1)二、hash查找的特点——基于计算地址keyinfo0123ikeym-18.4hash(散列)查找例8.3hash查找示例。人口统计表。在右表中查找1989年出生的人数。查找方法（1）：顺序查找查找方法（2）：二分查找查找方法（3）：hash查找hash(key)=key-1949=1989-1949=40地址年份人数01949………11950………21951………31952………40……1989……592008………——除留余数法hash(key)=key%pp≤m(表长)关键问题是:如何选取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.4key={3,15,20,24}，m=5（表长），hash(k)=k%5hash(15)=0hash(20)=0产生冲突。四、冲突的概念与处理方法冲突的处理——链地址法将具有相同散列地址的记录都存储在同一个线性链表中。例8.5key={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)=1112779hash(key)=key%13hash(14)=1hash(1)=1hash(68)=3hash(27)=1hash(55)=3hash(23)=10hash(11)=11hash(10)=10hash(19)=6hash(20)=7hash(79)=1hash(84)=6146819202311558410ASL=（6*1+4*2+1*3+1*4）/12=21/120123456789101112对给定的关键值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表：01234567891011121314151614681552720198479112310比较次数：33ASL=(1*10+3*2)/12=16/12