搜索
第九章.查找（Chapter9.Searching)查找运算是计算机中最常用的操作之一。有人统计过，计算机大约有40%的运算是与查找相关的。数据元素（或记录）的某个数据项，能用来标识一个数据元素。若能唯一的标识一个数据元素，则称为主关键字（primarykey），反之则为次关键字（secondarykey）。关键字（key）查找表（searchtable）§9.1静态表的查找查找（searching）根据某个给定的值，在查找表中找寻关键字等于给定值的数据元素（或记录）。若表中存在这样的数据元素，则称查找是成功的，查找结果即为查找到的数据元素；反之则称查找是不成功的，此时查找结果为空。由同一类型的数据元素（或记录）构成的集合。表中的元素基本上是固定的，这类查找表称为静态查找表（staticsearchtable）；若在查找过程中将不存在的元素插入查找表中，则称这类查找表为动态查找表（dynamicsearchtable）。实际查找时，通常将给定值放在第0个记录处，然后从后向前查找，直到找到所查记录为止，找不到则返回结果0。因为记录0像哨兵一样看守着查找表下界，所以不会越界。typedefstruct{keytypekey;......}elemtype;一、无序表的查找：查找表中的各元素（或记录）的关键字的值是无序的。typedefstruct{elemtype*elem;intlength;}sstable;intseqsearch(sstableR,keytypeK){R.elem[0].key:=K;for(i=R.length;R.elem[i].key!=K;i--);returni;}查找表的长度为n：查找性能分析：平均查找长度（averagesearchlength）为了确定记录在查找表中的位置，需与给定值比较的关键字的个数的期望值称为平均查找长度。对含有n个记录的查找表，查找成功时的平均查找长度为：ASL=∑PiCi，其中Pi为查找第i个记录的概率，且∑Pi=1。ni=1i=1n在等概率情况下，顺序查找无序表的平均查找长度为：ASL成功=（n+1)/2和ASL不成功=n+1。二、有序表的查找：查找表中的各元素（或记录）的关键字的值是有序的。这类有序表的查找仍可以用顺序查找，但在找不到时不需比较到表尾，只需比较到比给定值大的记录就可终止。在等概率情况下，顺序查找有序表的平均查找长度为：ASL成功=（n+1)/2和ASL不成功=（n+2)/2。有序表的查找比较好的方法是折半查找（binarysearch）：将给定值与中间的记录进行比较，若找到则查找成功；否则若给定值比中间记录小，则对前一半子表进行折半查找，反之则对后一半子表进行折半查找。若在查找过程中，遇到查找子表的上界小于下界，则表示查找失败。intseqsearch(sstableR,keytypeK){R.elem[0].key:=K;for(i=R.length;R.elem[i].keyK;i--);if(R.elem[i].key=K)returni;elsereturn0;}intbinsearch(sstableR,keytypeK){low=1;high=R.length;while(low=high){mid=(low+high)/2;if(R.elem[mid]==K)returnmid;elseif(R.elem[mid]K)high=mid-1;elselow=mid+1;}return0;}intbinsearch(sstableR,intlow,inthigh,keytypeK){if(lowhigh)return0;mid=(low+high)/2;if(R.elem[mid]==K)returnmid;if(R.elem[mid]K)returnbinsearch(R,low,mid-1,K);returnbinsearch(R,mid+1,high,K);}查找性能分析：折半查找每次只查表的一半，其所有记录的查找路径构成一棵二叉树，称为折半查找树（或判定树），每次查找只走了该树的一条分支，故平均查找长度不超过log2n+1。有一组记录的关键字为{1，2，3，4，5，6，7，8}，求其在等概率情况下查找成功的平均查找长度：例：42516378其查找树如左图所示：ASL成功==21/8。1*1+2*2+3*4+4*18有序表的查找也可用其它的查找方法，如费波拉契查找（Fibonaccisearch）。设查找表记录数为某个费波拉契数减一，即n=Fu-1，则可将给定值与第Fu-1个记录比较，若比其小，则在1~Fu-1-1记录间查找，否则在Fu-1+1~Fu-1记录间查找。如下图所示：4251637若有序表的关键字是均匀分布的，则还可用插值查找方法，其平均性能在记录数较多时比折半查找好：将给定值先与第i个记录比较，则i=n。K-r[L].keyr[H].key-r[L].key作业25.查找序列以带头结点的单链表表示，各结点中设一个访问频度，初始值为0，每次查找成功后该结点频度值增加1。试给出算法，在每次查找后查找序列均按访问频度从大到小排列。查找效率最高即平均查找长度最小，根据前面所学知识，我们可以给出有序表在非等概率情况下应遵循的两个原则：1、最先访问的结点应是访问概率最大的结点；2、每次访问应使结点两边尚未访问的结点的被访概率之和尽可能相等。三、静态树表的查找：前面介绍的有序表查找都是在“等概率”情况下的，若在非等概率情况下应该怎样查找才能使查找效率更高了？这样的树称为静态最优查找树（staticoptimalsearchtree），构造这样一棵树的时间代价太大，亦即时间复杂度很大，因此我们通常是构造次优查找树（nearlyoptimalsearchtree），构造它的时间代价远远低于构造最优查找树，但查找性能只比最优查找树差1%~2%，很少差3%以上。这两个原则可用一句话来表示，即判定树为带权内路径长度之和最小的二叉树，亦即：PH=∑wihi最小，其中n为有序表长度，hi为第i个结点在判定树上的层次数，wi=cpi，c为某个常数，pii=1n为第i个结点的查找概率。次优查找树的构造：设有序表每个记录的权值为wl,wl+1,…,wh，第一个应访问的结点号为i，则有：Δpi=∑wj-∑wj最小，即Δpi=Min{Δpj}再分别对{rl,rl+1,…,ri-1}和{ri+1,ri+2,…,rh}分别构造次优查找树。j=i+1j=lhi-ll≤j≤h为便于计算，引入累计权值swi=∑wj，并设wl-1=swl-1=0，则：j=li∑wjj=i+1h∑wjj=li-1swi-1-swl-1=swh-swi={Δpi=|swh+swl-1-swi-swi-1|由于在构造次优查找树时没有考虑前面说的原则一，因此被选为根的结点的权值可能比其邻近结点的权值小，此时应对查找树作适当的调整，将相邻权值大的结点作为根结点。次优查找树的查找方法与折半查找类似，其平均查找长度与logn成正比。四、索引顺序表的查找：有一些顺序表是带索引表的，这类表通常称为索引顺序表。一般的，索引顺序表的索引部分一定是有序的，故这部分可用折半查找等方法；但顺序表本身则不一定有序，因此，可根据顺序表是否有序而选用相应的查找方法。这种将索引部分和表体部分分开查找的方法称为分块查找（blockingsearch）。索引表如下图所示，其平均查找长度为两部分查找之和。35689311013最大关键字起始地址索引表231611356283125194157689375886913245678910111213141516顺序表ASLbs=Lb+Lw顺序查找所在块：ASLbs=(n/s+s)/2+1当s=√n时,ASLbs=√n+1,最小折半查找所在快：ASLbs=log2(n/s+1)+s/2§9.2动态表的查找一、二叉排序树：二叉排序树（binarysorttree）或者为空树，或者为这样一棵树：根结点的左子树的所有结点的关键字值均比根结点的关键字值小；根结点的右子树的所有结点的关键字值均比根结点的关键字值大；根结点的左右子树也是二叉排序树。二叉排序树是动态查找树，即在查找时将未找到的给定值的记录插入到查找树中，查找树是动态生成的。5432259947368有查找请求{54、32、54、25、73、25、94、68、32、73、9}，查找结果如下：例：查找失败查找失败查找成功查找失败查找失败查找成功查找失败查找失败查找成功查找成功查找失败作业26.试给出判别一棵给定的二叉树是否是排序二叉树的算法，设二叉树以二叉链表表示。二叉排序树的查找：若当前结点指针为空或当前结点为所找结点则返回当前指针；若当前结点关键字值比给定值大则继续查找当前结点的左子树；否则就继续查找当前结点的右子树。二叉排序树的插入：先用给定值查找二叉排序树，查找成功则返回所找结点指针；否则在找不到时的叶结点的左子树或右子树处插入给定值记录。（新插入的结点一定是叶子结点）二叉排序树的删除：若将删除的结点是叶子结点，直接删除即可；若将删除的结点只有左子树或只有右子树，则可用左孩子或右孩子直接替换将要删除结点位置；若将删除的结点左、右子树均存在，则可用将要删除结点左子树的最右结点（关键字值最大的结点）替换将要删除结点，用替换结点的左子树（若存在）替换“替换结点”。二叉排序树的查找分析：ASL与二叉排序树的高度有关。由于二叉排序树是根据查找请求序列建立的，因此很可能退化成为线性表（什么情况下？），如何解决这一问题呢？二、平衡二叉树：平衡二叉树（balancedbinarytree)又称AVL树(G.M.Adelson-Velskii&Y.M.Landis.Analgorithmfortheorganizationofinformation.SovietMath.Dokl.,3:1259--1262,1962.)，它具有如下性质：或者为空树，或者根结点的左、右子树也均为平衡二叉树，且左、右子树的树高之差的绝对值不超过1。平衡因子（balancefactor）：结点的左子树高度减去右子树高度的值称为该结点的平衡因子。因此平衡二叉树也可以这样定义：平衡二叉树是所有结点的平衡因子的绝对值均小于2的二叉树。我们谈论的平衡二叉树其实是平衡二叉排序树。平衡二叉树的插入：平衡二叉树插入时分为四种类型：LL型、LR型、RL型和RR型。1、将新的结点插入在平衡二叉树中，沿着刚插入的结点到根结点的路径修改所经过结点的平衡因子，直到找到某结点A的平衡因子为2或修改完根结点的平衡因子后仍为平衡二叉树。2、若结点A的平衡因子为2，则需进行调整，设A的儿子和孙子（刚经过的结点）分别为B和C，则有：ABCACBLR0-12000ABCRL01-2BCA000ABCABCLL012000ABCCBARR0-1-2000####JANFEBAPRAUGMARJUNMAYJULJANFEBMARAPRMAYJUNJULAUGSEPOCT有一组关键字序列{JAN、FEB、MAR、APR、MAY、JUN、JUL、AUG、SEP、OCT、NOV、DEC}，以此建立AVL树。例：LRAUG0APR-1FEB2OCT0SEP1MAY-2SEPOCTJANFEBMARAPRMAYJUNJULAUGNOVDECNOVSEPOCTJANFEBMARAPRMAYJUNJULAUGRLRROCT1MAR-1JAN-2第五次上机作业输入一组关键字序列，并以此顺序建立一棵平衡二叉树（提示：为简化运算，可采用含有左、右子树高度和指向父母的指针的三叉链表表示），并在建树过程中用逆中序法输出每次插入新结点后的平衡二叉树形状。含有n个关键字的平衡二叉树的最大深度为多少？平衡二叉树的查找分析：用Nh表示深度为h的平衡二叉树含有的最少结点数，则：N0=0、N1=1、N2=2、…、Nh=Nh-1+Nh-2+1=φh+2/√5-1，其中φ=（1+√5）/2，则含有n个结点的平衡二叉树