DS08-查找79892.ppt

§ 基本概念基本概念§ 线性表的查找线性表的查找 § 树表的查找树表的查找 § 散列散列( (Hash)Hash)技术技术 第八章第八章 查找查找18.1 查找的基本概念查找的基本概念       查找（查找（Searching））的定义是：给定的定义是：给定一个关键字值一个关键字值K，在含有，在含有n个结点的个结点的表中找出关键字等于给定值表中找出关键字等于给定值K的结点若找到，则查找成功，返回该结点的若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查信息或该结点在表中的位置；否则查找失败，返回相关的指示信息找失败，返回相关的指示信息2§查找表的数据结构表示查找表的数据结构表示                          若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为动态查找表动态查找表（Dynamic Search Table）否则称之为静态查找表静态查找表(Static Search Table)          若整个查找过程都在内存进行，则称之为内查找内查找；反之，若查找过程中需要访问外存，则称之为外查找 3n n平均查找长度平均查找长度平均查找长度平均查找长度   ASLASL（（（（Average Search LengthAverage Search Length））））的的的的定义为定义为定义为定义为 ：§ASL=ASL=   其中：其中：    　　1、、n是结点的个数；是结点的个数；   　　 2、、Pi是查找第是查找第i个结点的概率。

若不特别个结点的概率若不特别声明，认为每个结点的查找概率相等，即声明，认为每个结点的查找概率相等，即                  pl = p2…… = pn = 1/n   　　 3、、ci是找到第是找到第i个结点所需进行的比较次个结点所需进行的比较次数i=1,2, ··· ,n））4§顺序查找顺序查找(Sequential Search) 基本思想是：基本思想是：从表的一端开始，顺序扫从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字描线性表，依次将扫描到的结点关键字和给定值和给定值K相比较若当前扫描到的结点相比较若当前扫描到的结点关键字与关键字与K相等，则查找成功；若扫描结相等，则查找成功；若扫描结束后，仍未找到关键字等于束后，仍未找到关键字等于K的结点，则的结点，则查找失败查找失败8.2线性表的查找线性表的查找5§基于顺序结构的顺序查找算法基于顺序结构的顺序查找算法 类型说明类型说明  typedef struct  typedef struct  { KeyType key  { KeyType key；； /* KeyType/* KeyType/* KeyType/* KeyType由用户定由用户定由用户定由用户定义义义义 */ */ */ */    InfoType otherinfo    InfoType otherinfo；；/* /* /* /* 此类型此类型此类型此类型依赖于依赖于依赖于依赖于 应用应用应用应用 */ */ */ */   }NodeType   }NodeType；；  typedef NodeType Seqlist[n+1]  typedef NodeType Seqlist[n+1]；； /*0 /*0号单元用作监视哨号单元用作监视哨*/*/6具体算法具体算法具体算法具体算法     int SeqSearch(Seqlist R，，KeyType K)    { /*在顺序表在顺序表R[1..n]中顺序查找关键字为中顺序查找关键字为K的结点，成功时返回找到的结点位置，失败的结点，成功时返回找到的结点位置，失败时返回时返回0*/      int i；；      R[0].key=K；；                /*设置监视哨设置监视哨*/      for(i=n；；R[i].key!=K;i--)；； /*从表后往前从表后往前找找*/      return i；； /*若若i为为0，表示查找失败，否，表示查找失败，否则则R[i]为要找的结点为要找的结点*/    } /*SeqSearch*/7§算法分析算法分析查找成功时的顺序查找的平均查找长度：查找成功时的顺序查找的平均查找长度：ASL= =pASL= =pi i =np =np1 1+(n-+(n-1)p1)p2 2+…+2p+…+2pn-1n-1+p+pn n （式（式8.28.2））在等概率情况下，在等概率情况下，p pi i=1/n(1≤i≤n)=1/n(1≤i≤n)，故成，故成功的平均查找长度为功的平均查找长度为        (n+…+2+1)/n=(n+1)/2        (n+…+2+1)/n=(n+1)/2即查找成功时的平均比较次数约为表长的即查找成功时的平均比较次数约为表长的一半。

一半8n n顺序查找的优点顺序查找的优点顺序查找的优点顺序查找的优点      算法简单，且对表的结构无任何要求，无论是用算法简单，且对表的结构无任何要求，无论是用算法简单，且对表的结构无任何要求，无论是用算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是向量还是用链表来存放结点，也无论结点之间是向量还是用链表来存放结点，也无论结点之间是向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用否按关键字有序，它都同样适用否按关键字有序，它都同样适用否按关键字有序，它都同样适用n n顺序查找的缺点顺序查找的缺点顺序查找的缺点顺序查找的缺点         查找效率低查找效率低查找效率低查找效率低9n n二分查找二分查找二分查找二分查找又称又称又称又称折半查找折半查找折半查找折半查找，它是一种效率较高的查找方，它是一种效率较高的查找方，它是一种效率较高的查找方，它是一种效率较高的查找方法n n二分查找要求二分查找要求二分查找要求二分查找要求：线性表是有序表，即表中结点按关键：线性表是有序表，即表中结点按关键：线性表是有序表，即表中结点按关键：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。

不妨设有字有序，并且要用向量作为表的存储结构不妨设有字有序，并且要用向量作为表的存储结构不妨设有字有序，并且要用向量作为表的存储结构不妨设有序表是递增有序的序表是递增有序的序表是递增有序的序表是递增有序的§ 二分查找二分查找二分查找二分查找 10二分查找的基本思想是：二分查找的基本思想是：（（1）首先确定该区间的中点位置：）首先确定该区间的中点位置：                     mid = （（2）然后将待查的）然后将待查的K值与值与R[mid].key比较：比较：若相等，则查找成功并返回此位置，否则若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找须确定新的查找区间，继续二分查找 11二分查找算法二分查找算法int BinSearch(SeqList R，，KeyType K)    {int low=1，，high=n，，mid；；     while(low<=high)        {mid=(low+high)/2；；          if(R[mid].key==K) return mid；；          if(R[mid].key>K)             high=mid-1;          else             low=mid+1；；         }      return 0；；     }12例：设算法的输入实例中有序的关键字序例：设算法的输入实例中有序的关键字序列为：列为：    05，，13，，19，，21，，37，，56，，64，，75，，80，，88，，92，查找的关键字，查找的关键字K=21。

 n第一步：05，13，19，21，37，56，64，75，80，88，92 13n第二步：05，13，19，21，37，56，64，75，80，88，92 n第三步：05，13，19，21，37，56，64，75，80，88，92此时R[mid].key＝K，return mid＝4 14二分查找判定树二分查找判定树二分查找过程可用二叉树来描述：二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树点分别作为根的左子树和右子树由此得到的二叉树，称为描述二分由此得到的二叉树，称为描述二分查找的查找的判定树判定树(Decision Tree)或或比比较树较树(Comparison Tree)15二分查找判定树的组成二分查找判定树的组成n n圆结点即树中的内部结点树中圆结点内圆结点即树中的内部结点树中圆结点内的数字表示该结点在有序表中的位置的数字表示该结点在有序表中的位置n n外部结点：圆结点中的所有空指针均用一外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。

个虚拟的方形结点来取代，即外部结点n n当查找时找到外部节点时，表示查找的值当查找时找到外部节点时，表示查找的值没有在该有序表中没有在该有序表中 16二分查找的平均查找长度二分查找的平均查找长度 n二分查找成功时的平均查找长度为：二分查找成功时的平均查找长度为：  ASL  ASLbnbn≈lg(n+1)-1 ≈lg(n+1)-1 n二分查找在查找失败时所需比较的关二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超坏情况下查找成功的比较次数也不超过判定树的深度即为：过判定树的深度即为：       17二分查找的优点和缺点二分查找的优点和缺点n虽然二分查找的效率高，但是要将表虽然二分查找的效率高，但是要将表按关键字排序按关键字排序 n二分查找只适用顺序存储结构为保二分查找只适用顺序存储结构为保持表的有序性，在顺序结构里插入和持表的有序性，在顺序结构里插入和删除都必须移动大量的结点删除都必须移动大量的结点 18分块查找分块查找 n分块查找表分块查找表存储结构存储结构n分块查找表由分块查找表由" "分块有序分块有序" "的线性表的线性表和和索引表索引表组成。

组成19n分块查找的分块查找的基本思想基本思想 ：：n首先查找索引表首先查找索引表 索引表是有序表，可采用二分查索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在找或顺序查找，以确定待查的结点在哪一块n然后在已确定的块中进行顺序查找然后在已确定的块中进行顺序查找 由于块内无序，只能用顺序查找由于块内无序，只能用顺序查找 20查找查找关键字等于给定值关键字等于给定值K=24K=24的结点的结点 (见见P197)n因为索引表小，不妨用顺序查找方法查因为索引表小，不妨用顺序查找方法查找索引表即首先将找索引表即首先将K K依次和索引表中各依次和索引表中各关键字比较，直到找到第关键字比较，直到找到第1 1个关键宇大小个关键宇大小等于等于K K的结点，由于的结点，由于K<48K<48，所以关键字为，所以关键字为2424的结点若存在的话，则必定在第二块的结点若存在的话，则必定在第二块中；然后，由中；然后，由ID[2].addrID[2].addr找到第二块的找到第二块的起始地址起始地址7 7，从该地址开始在，从该地址开始在R[7..12]R[7..12]中中进行顺序查找，直到进行顺序查找，直到R[11].key=KR[11].key=K为止。

为止21算法分析算法分析 n分块查找是两次查找过程整个查找过程的平分块查找是两次查找过程整个查找过程的平均查找长度是两次查找的平均查找长度之和均查找长度是两次查找的平均查找长度之和 以二分查找来确定块，分块查找成功时的以二分查找来确定块，分块查找成功时的平均查找长度平均查找长度nASLASLblkblk=ASL=ASLbnbn+ASL+ASLsqsqn≈log≈log2 2(b+1)-1+(s+1)/2≈log(b+1)-1+(s+1)/2≈log2 2(n/s+1)+s/2(n/s+1)+s/2 以顺序查找确定块，分块查找成功时的平以顺序查找确定块，分块查找成功时的平均查找长度均查找长度nASL’ASL’blkblk=(b+1)/2+(s+1)/2=(s=(b+1)/2+(s+1)/2=(s2 2+2s+n)/(2s) +2s+n)/(2s) 22n分块查找的优点分块查找的优点n①①在表中插入或删除一个记录时，只在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内要找到该记录所属的块，就在该块内进行插入和删除运算进行插入和删除运算n②②因块内记录的存放是任意的，所以因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量插入或删除比较容易，无须移动大量记录。

记录 238.3 8.3 树表的查找树表的查找n1 1、二叉排序树的、二叉排序树的定义定义 n二叉排序树二叉排序树(Binary Sort Tree)(Binary Sort Tree)又称又称二叉查找二叉查找( (搜索搜索) )树树(Binary Search Tree)(Binary Search Tree)其定义为：二其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉排序树或者是空树，或者是满足如下性质的二叉树：叉树：n（（1 1）若它的左子树非空，则左子树上所有结点）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；的值均小于根结点的值；n（（2 2）若它的右子树非空，则右子树上所有结点）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；的值均大于根结点的值；n（（3 3）左、右子树本身又各是一棵二叉排序树左、右子树本身又各是一棵二叉排序树 24n二叉排序树的特点二叉排序树的特点 n（（1 1）） 二叉排序树中任一结点二叉排序树中任一结点x x，其，其左左( (右右) )子树中任一结点子树中任一结点y(y(若存在若存在) )的的关键字必小关键字必小( (大大) )于于x x的关键字。

的关键字n（（2 2）） 二叉排序树中，各结点关键字二叉排序树中，各结点关键字是唯一的是唯一的n（（3 3）） 按中序遍历该树所得到的中序按中序遍历该树所得到的中序序列是一个递增有序序列序列是一个递增有序序列25二叉排序树的存储结构二叉排序树的存储结构ntypedef int KeyTypetypedef int KeyType；； ntypedef struct node typedef struct node n{ { n  KeyType key  KeyType key；； n  InfoType otherinfo  InfoType otherinfo；； n struct node *lchild struct node *lchild，，*rchild*rchild；； n}BSTNode}BSTNode；；ntypedef BSTNode *BSTreetypedef BSTNode *BSTree；； 26n二叉排序树插入新结点的过程二叉排序树插入新结点的过程n在二叉排序树中插入新结点，要保证插入后仍满足在二叉排序树中插入新结点，要保证插入后仍满足BSTBST性质。

其插入过程是：性质其插入过程是：n1)1)若二叉排序树若二叉排序树T T为空，则为待插入的关键字为空，则为待插入的关键字keykey申请申请一个新结点，并令其为根；一个新结点，并令其为根；n2)2)若二叉排序树若二叉排序树T T不为空，则将不为空，则将keykey和根的关键字比较：和根的关键字比较：n    (a)    (a)若二者相等，则说明树中已有此关键字若二者相等，则说明树中已有此关键字keykey，无须插入无须插入n    (b)    (b)若若keyT→keykey>T→key，则将它插入根的右子树中则将它插入根的右子树中 27n二叉排序树插入新结点的二叉排序树插入新结点的算法算法n      void InsertBST(BSTree *Tptr，，KeyType key)n      {     nBSTNode *f，，*p=*TPtr；；   n        while(p){                  n          if(p->key==key) return；； n          f=p；；                   n          p=(keykey)?p->lchild:p->rchild；；            n         }  n            n   p=(BSTNode *)malloc(sizeof(BSTNode))；；n         p->key=key；； p->lchild=p->rchild=NULL；； n         if(*TPtr==NULL)                       n         *Tptr=p；；                              n        else  n          if(keykey)n           f->lchild=p；；n          else f->rchild=p；；n       } 28n二叉排序树的生成二叉排序树的生成n是从空的二叉排序树开始，每输入一是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法，个结点数据，就调用一次插入算法，将它插入到当前已生成的二叉排序树将它插入到当前已生成的二叉排序树中。

中 29 BSTree CreateBST(void)   {       BSTree T=NULL；；            KeyType key；；     scanf("％％d"，，&key)；；       while(key)      {                           InsertBST(&T，，key)；；          scanf("％％d"，，&key)；；       }    return T；；     } 生成二叉排序树的算法生成二叉排序树的算法 30n输入实例(5，3，7，2，4，8)，根据生成二叉排序树算法生成二叉排序树的过程 55325375372537425374831二叉排序树的删除二叉排序树的删除 n从二叉排序树中删除一个结点，不能把以从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足证删除后所得的二叉树仍然满足BSTBST性质n1)1)删除操作的删除操作的一般步骤一般步骤n① ① 进行查找进行查找        查找时，令查找时，令p p指向当前访问到的指向当前访问到的结点，结点，parentparent指向其双亲指向其双亲( (其初值为其初值为NULL)NULL)。

若树中找不到被删结点则返回，若树中找不到被删结点则返回，否则被删结点是否则被删结点是*p*p32n② ② 删去删去*p*pn删删*p*p时，应将时，应将*p*p的子树的子树( (若有若有) )仍连接在树仍连接在树上且保持上且保持BSTBST性质不变按性质不变按*p*p的孩子数目分的孩子数目分三种情况进行处理三种情况进行处理n2)2)删除删除*p*p结点的三种情况结点的三种情况n①*p①*p是叶子是叶子( (即它的孩子数为即它的孩子数为0)0)n        　无须连接　无须连接*p*p的子树，只需将的子树，只需将*p*p的的双亲双亲*parent*parent中指向中指向*p*p的指针域置空即可的指针域置空即可n②*p②*p只有一个孩子只有一个孩子*child*childn只需将只需将*child*child和和*p*p的双亲直接连接后，即的双亲直接连接后，即可删去可删去*p*p33n③*p③*p有两个孩子有两个孩子 先令先令q=pq=p，将被删结点的地址保存在，将被删结点的地址保存在q q中；然后找中；然后找*q*q的中序后继的中序后继*p*p，并在查，并在查找过程中仍用找过程中仍用parentparent记住记住*p*p的双亲位的双亲位置。

置q*q的中序后继的中序后继*p*p一定是一定是*q*q的右子的右子树中最左下的结点，它无左子树因树中最左下的结点，它无左子树因此，可以将删去此，可以将删去*q*q的操作转换为删去的操作转换为删去的的*p*p的操作，即在释放结点的操作，即在释放结点*p*p之前将之前将其数据复制到其数据复制到*q*q中，就相当于删去了中，就相当于删去了*q*q34二叉排序树删除算法二叉排序树删除算法 nvoid DelBSTNode(BSTree *Tptr，，KeyType key)n {   nBSTNode *parent=NUll，，*p=*Tptr，，*q，，*child；；n  while(p){                  n    if(p->key==key) break；；   n    parent=p；；               n    p=(keykey)?p->lchild：：p->rchild；； n   }n  if(!p) return；；            n    q=p；；                      n  if(q->lchild&&q->rchild)  n    for(parent=q，，p=q->rchild；； p->lchild；；nparent=p，，p=p=->lchild)；；    n    child=(p->lchild)?p->lchild：：p->rchild；； n if(!parent)  n   *Tptr=child；；  n else{   n      if(p==parent->lchild)       n        parent->lchild=child；；    n else parent->rchild=child；； nif(p!=q)                    n  q->key=p->key；；          n}                             nfree(p)；；                     n} 35二叉排序树上的查找二叉排序树上的查找n在二叉排序树上进行查找，和二分查找类似，也是一个逐步在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。

缩小查找范围的过程n递归的查找算法：递归的查找算法：nBSTNode *SearchBST(BSTree TBSTNode *SearchBST(BSTree T，，KeyType key)KeyType key)n    { { nif(T==NULL||key==T->key) if(T==NULL||key==T->key) n            return Treturn T；； n        if(keykey)if(keykey)n            return SearchBST(T->lchildreturn SearchBST(T->lchild，，key)key)；；n        elseelsen            return SearchBST(T->rchildreturn SearchBST(T->rchild，，key)key)；； n      } } 36n在二叉排序树上进行查找时的在二叉排序树上进行查找时的平均查找长度和二平均查找长度和二叉树的形态有关：叉树的形态有关：n(a)(a)在最坏情况下，二叉排序树是通过把一个有在最坏情况下，二叉排序树是通过把一个有序表的序表的n n个结点依次插入而生成的，此时所得的个结点依次插入而生成的，此时所得的二叉排序树蜕化为一棵深度为二叉排序树蜕化为一棵深度为n n的单支树，它的的单支树，它的平均查找长度和单链表上的顺序查找相同，也是平均查找长度和单链表上的顺序查找相同，也是(n+1)/2(n+1)/2。

n(b)(b)在最好情况下，二叉排序树在生成的过程中，在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是均查找长度大约是loglog2 2n nn(c)(c)插入、删除和查找算法的时间复杂度均为插入、删除和查找算法的时间复杂度均为O(logO(log2 2n)n)37n二叉排序树和二分查找的比较二叉排序树和二分查找的比较        就平均时间性能而言，二叉排序树上的就平均时间性能而言，二叉排序树上的查找和二分查找差不多查找和二分查找差不多n就维护表的有序性而言，二叉排序树无须移动结就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为其平均的执行时间均为O(logO(log2 2n)n)，因此更有效因此更有效二分查找所涉及的有序表是一个向量，若有插入二分查找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代和删除结点的操作，则维护表的有序性所花的代价是价是O(n)O(n)。

当有序表是静态查找表时，宜用向量当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作为其存储结构，而采用二分查找实现其查找操作；若有序表是动态查找表，则应选择二叉排序作；若有序表是动态查找表，则应选择二叉排序树作为其存储结构树作为其存储结构38ＢＢ- - 树树 nB- B- 树的定义树的定义n一棵一棵m(m≥3)m(m≥3)阶的阶的B-B-树是满足如下性质的树是满足如下性质的m m叉树：叉树：n(1)(1)每个结点至少包含下列数据域：每个结点至少包含下列数据域：n    (n    (n，，P P0 0，，K Kl l，，P P1 1，，K K2 2，，……，，K Ki i，，P Pi i) )n其中：其中：n    n    n为关键字总数为关键字总数n    K    Ki i(1≤i≤j)(1≤i≤j)是关键字，关键字序列递增是关键字，关键字序列递增有序：有序：K K1 1

为空指针 39n(2)所有叶子是在同一层上，叶子的层数为树的高度hn(3)每个非根结点中所包含的关键字个数j满足：                 n(4)若树非空，则根至少有1个关键字，故若根不是叶子，则它至少有2棵子树根至多有m-1个关键字，故至多有m棵子树40nB- 树的存储结构树的存储结构#define Max l000  n#define Min 500   ntypedef int KeyType；；  ntypedef struct node{  nint keynum；；  n  　　KeyType key[Max+1]；； n  　　struct node *parent；； n  　　struct node *son[Max+1]；； n }BTreeNode；；ntypedef BTreeNode *BTree；；41nB-B-树的查找树的查找 在在B-B-树中查找给定关键字的方法类似于二叉排序树中查找给定关键字的方法类似于二叉排序树上的查找不同的是在每个结点上确定向下查树上的查找不同的是在每个结点上确定向下查找的路径不一定是二路而是找的路径不一定是二路而是keynum+1keynum+1路的。

路的n对结点内的存放有序关键字序列的向量对结点内的存放有序关键字序列的向量key[l..keynum] key[l..keynum] 用顺序查找或折半查找方法查用顺序查找或折半查找方法查找若在某结点内找到待查的关键字找若在某结点内找到待查的关键字K K，则返回，则返回该结点的地址及该结点的地址及K K在在key[1..keynum]key[1..keynum]中的位置；中的位置；否则，确定否则，确定K K在某个在某个key[i]key[i]和和key[i+1]key[i+1]之间的结之间的结点后，从磁盘中读点后，从磁盘中读son[i]son[i]所指的结点继续查找所指的结点继续查找…………直到在某结点中查找成功；或直至找到叶直到在某结点中查找成功；或直至找到叶结点且叶结点中的查找仍不成功时，查找过程失结点且叶结点中的查找仍不成功时，查找过程失败42nB-树的查找算法树的查找算法BTreeNode *SearchBTree(BTree T，，KeyType K，，int *pos)n {   int i；；n  T→key[0]=k ;               n  for(i=T->keynum；；Kkey[i];i--)；；  n  if(i>0 && T->key[i]==1)n    {      *pos=i；；n      return T；；n     }  n   if(!T->son[i])   n      return NULL；；n       DiskRead(T->son[i])；；           n    return SearchBTree(T->Son[i]，，k，，pos)；； n   }43n查找操作的时间开销查找操作的时间开销    B-    B-树上的查找有两个基本步骤：树上的查找有两个基本步骤：n　　①①在在B-B-树中查找结点，该查找涉及读盘树中查找结点，该查找涉及读盘DiskReadDiskRead操作，属外查找；操作，属外查找；n　　②②在结点内查找，该查找属内查找。

在结点内查找，该查找属内查找n　查找操作的时间为：　查找操作的时间为：n　　①①外查找的读盘次数不超过树高外查找的读盘次数不超过树高h h，故其，故其时间是时间是O(h)O(h)；；n　　②②内查找中，每个结点内的关键字数目内查找中，每个结点内的关键字数目keynum

变45n将违反性质将违反性质(3)(3)的结点以中间位置上的的结点以中间位置上的关键字关键字 为划分点，将该结点为划分点，将该结点( (不妨设是不妨设是*current)*current)：：(m(m，，P P0 0，，K K1 1，，P P1 1，，……，，K Km m，，P Pm m) ) ，其中，其中KiKi表示表示key[i]key[i]，，P Pi i表示表示son[i] "son[i] "分裂分裂" "为两个结点为两个结点：46B-B-树中插入关键字树中插入关键字6 6的分裂过程的分裂过程 1215 0135 7 82151312875 621513126528747nB-B-树的删除树的删除n（（1 1）删除操作的两个步骤：）删除操作的两个步骤：n    ①    ①在树中查找被删关键字在树中查找被删关键字K K所在的所在的结点；结点；n    ②    ②进行删去进行删去K K的操作n（（2 2）删去）删去K K的操作的操作n    B-    B-树是二叉排序树的推广，中序遍树是二叉排序树的推广，中序遍历历B-B-树同样可得到关键字的有序序列。

任树同样可得到关键字的有序序列任一关键字一关键字K K的中序前趋的中序前趋( (后继后继) )必是必是K K的左子的左子树树( (右子树右子树) )中最右中最右( (左左) )下的结点中最后下的结点中最后( (最最前前) )一个关键字一个关键字48n若被删关键字若被删关键字K K所在的结点非树叶，则用所在的结点非树叶，则用K K的中序的中序前趋前趋( (或后继或后继)K')K'取代取代K K，然后从叶子中删去，然后从叶子中删去K'K'从叶子从叶子*x*x开始删去某关键字开始删去某关键字K K的三种情形为：的三种情形为：n    情形一情形一：若：若x->keynum>Minx->keynum>Min，则只需删去，则只需删去K K及及其右指针其右指针(*x(*x是叶子，是叶子，K K的右指针为空的右指针为空) )即可使删即可使删除操作结束除操作结束n 情形二情形二：若：若x->keynum=Minx->keynum=Min，该叶子中的关键字，该叶子中的关键字个数已是最小值，删个数已是最小值，删K K及其右指针后会破坏及其右指针后会破坏B-B-树树的性质的性质(3)(3)若*x*x的左的左( (或右或右) )邻兄弟结点邻兄弟结点*y*y中的中的关键字数目大于关键字数目大于MinMin，则将，则将*y*y中的最大中的最大( (或最小或最小) )关键字上移至双亲结点关键字上移至双亲结点*parent*parent中，而将中，而将*parent*parent中相应的关键字下移至中相应的关键字下移至x x中。

中 49n情形三情形三：若：若*x*x及其相邻的左右兄弟及其相邻的左右兄弟( (也可能只有一个兄弟也可能只有一个兄弟) )中的关键字数中的关键字数目均为最小值目均为最小值MinMin，则上述的移动操，则上述的移动操作就不奏效，此时须作就不奏效，此时须*x*x和左或右兄弟和左或右兄弟合并 50 B B－树中删除关键字－树中删除关键字6 6，，7 7的过程的过程 126897521513127985215131258 9 2151351n性能分析性能分析①n①n个结点的平衡的二叉排序的高度个结点的平衡的二叉排序的高度H H（即（即loglog2 2n n）比）比B-B-树的高度树的高度h h约大约大loglog2 2t t倍n例如例如m=1024m=1024，则，则loglog2 2t=logt=log2 2512=9512=9此时若B-B-树树高度为高度为4 4，则平衡的二叉排序树的高度约为，则平衡的二叉排序树的高度约为3636显然，若显然，若m m越大，则越大，则B-B-树高度越小树高度越小n②②若要作为内存中的查找表，则若要作为内存中的查找表，则B-B-树却不一定树却不一定比平衡的二叉排序树好，尤其当比平衡的二叉排序树好，尤其当m m较大时更是较大时更是如此。

如此528.4 8.4 散列表的查找散列表的查找n散列表散列表(Hash Table)(Hash Table)      散列是一种重要的存储方法，也是一种散列是一种重要的存储方法，也是一种常见的查找方法散列的基本思想是：以结点常见的查找方法散列的基本思想是：以结点的关键字的关键字K K为自变量，通过一个确定的函数为自变量，通过一个确定的函数（即映射）关系（即映射）关系h h，计算出对应的函数值，计算出对应的函数值h(K)h(K)，然后把这个值解释为结点的存储地址，将结，然后把这个值解释为结点的存储地址，将结点存入点存入h(K)h(K)所指的存储位置上在查找时，根所指的存储位置上在查找时，根据要查找的关键字用同一函数据要查找的关键字用同一函数h h计算出地址，计算出地址，再到相应的单元里去取要找的结点因此，再到相应的单元里去取要找的结点因此，散散列方法列方法又称为关键字又称为关键字- -地址转换法，用散列方地址转换法，用散列方法存储的线性表称为法存储的线性表称为散列表散列表(Hash Table)(Hash Table)，也，也称称哈希表哈希表或或杂凑表杂凑表上述的函数上述的函数h h称为称为散列函散列函数数，，h(K)h(K)称为称为散列地址散列地址。

53 通常散列表的存储空间是一个一维数组，散列地址是该数组的下标在不会引起混淆的情况下，我们就将这个一维数组简称为散列表 例例8.98.9 以城市名或省名的拼音作为关键字K，散列函数h(K)为取K的首字母在字母表中的序号，可得散列地址如下： 54n散列表的冲突现象散列表的冲突现象（（1 1）冲突）冲突        两个不同的关键字，由于散列函数值两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上该现象称相同，因而被映射到同一表位置上该现象称为为冲突冲突(Collision)(Collision)或碰撞发生冲突的两个或碰撞发生冲突的两个关键字称为该散列函数的同义词关键字称为该散列函数的同义词(Synonym)(Synonym) n（（2 2）安全避免冲突的条件）安全避免冲突的条件n最理想的解决冲突的方法是安全避免冲突要最理想的解决冲突的方法是安全避免冲突要做到这一点必须满足两个条件：做到这一点必须满足两个条件：①①关键字的个数小于或等于散列表的长度；关键字的个数小于或等于散列表的长度；②②选择合适的散列函数选择合适的散列函数 55n（3）冲突不可能完全避免n 通常情况下，由于关键字的个数大于散列表的长度，因此，无论怎样设计h，也不可能完全避免冲突。

我们只能做到，在设计h时尽可能使冲突最少，同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到散列表中 n（4）影响冲突的因素 冲突的频繁程度除了与h相关外，还与表的填满程度相关n 设m表示散列表的表长，n表示表中填入的结点个数，则将α=n/m定义为散列表的装填因子装填因子(Load Factor)α越大，表越满，冲突的机会也越大通常取α≤1 56常用散列函数常用散列函数n平方取中法平方取中法n具体方法：先通过求关键字的平方值具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值又取中间的几位数作为散列函数值又因为一个乘积的中间几位数和乘数的因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列每一位都相关，所以由此产生的散列地址较为均匀地址较为均匀57n除留余数法除留余数法 n该方法是最为简单常用的一种方法该方法是最为简单常用的一种方法它是以表长它是以表长m m来除关键字，取其余数来除关键字，取其余数作为散列地址，即作为散列地址，即 h(key)=key h(key)=key％％m mn该方法的关键是选取该方法的关键是选取m m。

选取的选取的m m应使应使得散列函数值尽可能与关键字的各位得散列函数值尽可能与关键字的各位相关m m最好为素数最好为素数58n相乘取整法相乘取整法n该方法包括两个步骤：首先用关该方法包括两个步骤：首先用关键字键字keykey乘上某个常数乘上某个常数A(0

序列沿此序列逐个单元地查找，直到找到给定的关沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址键字，或者碰到一个开放的地址( (即该地址单即该地址单元为空元为空) )为止（若要插入，在探查到开放的地为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）址，则可将待插入的新结点存人该地址单元）查找时探查到开放的地址则表明表中无待查的查找时探查到开放的地址则表明表中无待查的关键字，即查找失败关键字，即查找失败1、开放地址法61（（2 2）开放地址法的一般形式）开放地址法的一般形式n开放定址法的一般形式为：开放定址法的一般形式为： h hi i=(h(key)+d=(h(key)+di i) )％％m 1≤i≤m-1 m 1≤i≤m-1 （（3 3）开放地址法堆装填因子的要求）开放地址法堆装填因子的要求n开放定址法要求散列表的装填因开放定址法要求散列表的装填因子子α≤lα≤l，实用中取，实用中取αα为为0.50.5到到0.90.9之之间的某个值为宜间的某个值为宜62n（（4 4）形成探测序列的方法）形成探测序列的方法n按照形成探查序列的方法不同，可将开放定址按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

法区分为线性探查法、二次探查法、双重散列法等n①①线性探查法线性探查法(Linear Probing)(Linear Probing)n该方法的基本思想是：该方法的基本思想是：n将散列表将散列表T[0..m-1]T[0..m-1]看成是一个循环向量，若初看成是一个循环向量，若初始探查的地址为始探查的地址为d(d(即即h(key)=d)h(key)=d)，则最长的探查序列，则最长的探查序列为：为：n        d        d，，d+ld+l，，d+2d+2，，……，，m-1m-1，，0 0，，1 1，，……，，d-1d-1n即即: :探查时从地址探查时从地址d d开始，首先探查开始，首先探查T[d]T[d]，然后，然后依次探查依次探查T[d+1]T[d+1]，，……，直到，直到T[m-1]T[m-1]，此后又循环到，此后又循环到T[0]T[0]，，T[1]T[1]，，……，直到探查到，直到探查到T[d-1]T[d-1]为止63n②②二次探查法二次探查法( (Quadratic Probing)Quadratic Probing)n      　二次探查法的探查序列是：　二次探查法的探查序列是：n         h         hi i=(h(key)+i*i)=(h(key)+i*i)％％m mn 0≤i≤m-1 0≤i≤m-1 ，即，即d di i=i=i2 2n　　　　 即探查序列为即探查序列为d=h(key)d=h(key)，，d+1d+12 2，，d+2d+22 2，，……，等。

等n        　该方法的缺陷是不易探查　该方法的缺陷是不易探查到整个散列空间到整个散列空间64n③③双重散列法双重散列法(Double Hashing)(Double Hashing)n        　该方法是开放定址法中最　该方法是开放定址法中最好的方法之一，它的探查序列是：好的方法之一，它的探查序列是：n              hi=(h(key)+i*h1(key))hi=(h(key)+i*h1(key))％％m mn 0≤i≤m-1 0≤i≤m-1，即，即d di i=i*h1(key)=i*h1(key)n        　即探查序列为：　即探查序列为：n       d=h(key)       d=h(key)，，(d+h1(key))(d+h1(key))％％m m，，(d+2h1(key))(d+2h1(key))％％m m，，……，等65n2、拉链法处理冲突拉链法处理冲突n拉链法解决冲突的做法是：将所有关拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单键字为同义词的结点链接在同一个单链表中若选定的散列表长度为链表中若选定的散列表长度为m m，则，则可将散列表定义为一个由可将散列表定义为一个由m m个头指针组个头指针组成的指针数组成的指针数组T[0..m-1]T[0..m-1]。

凡是散列地凡是散列地址为址为i i的结点，均插入到以的结点，均插入到以T[i]T[i]为头指为头指针的单链表中针的单链表中T T中各分量的初值均应中各分量的初值均应为空指针在拉链法中，装填因子为空指针在拉链法中，装填因子αα可以大于可以大于1 1，但一般均取，但一般均取α≤1α≤166　例：　例：已知一组已知一组关键字为（关键字为（2626，，3636，，4141，，3838，，4444，，1515，，6868，，1212，，0606，，5151），取表），取表长为长为1313，，用拉链用拉链法解决冲突构造法解决冲突构造这组关键字的散这组关键字的散列表，如右图所列表，如右图所示  0123458697101112∧∧∧∧∧∧26 ∧1541 ∧1236 ∧68 ∧06 ∧3844 ∧51 ∧67n拉链法的优点拉链法的优点n(1)(1)拉链法处理冲突简单，且无堆积现象，即非拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；同义词决不会发生冲突，因此平均查找长度较短；n(2)(2)由于拉链法中各链表上的结点空间是动态申由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；请的，故它更适合于造表前无法确定表长的情况；n(3)(3)开放定址法为减少冲突，要求装填因子开放定址法为减少冲突，要求装填因子αα较较小，故当结点规模较大时会浪费很多空间。

而拉小，故当结点规模较大时会浪费很多空间而拉链法中可取链法中可取α≥1α≥1，且结点较大时，拉链法中增，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；加的指针域可忽略不计，因此节省空间；n(4)(4)在用拉链法构造的散列表中，删除结点的操在用拉链法构造的散列表中，删除结点的操作易于实现只要简单地删去链表上相应的结点作易于实现只要简单地删去链表上相应的结点即可 68n拉链法的缺点拉链法的缺点n拉链法的缺点是：指针需要额外的空拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度中的冲突，从而提高平均查找速度 69散列表上的运算散列表上的运算 n散列表类型说明：散列表类型说明：n#define NIL -1  n#define m 997  ntypedef struct{  n  KeyType key；；n  InfoType otherinfo；；  n }NodeType；；ntypedef NodeType HashTable[m]；； 70n基于开放地址法的查找算法基于开放地址法的查找算法n 散列表的查找过程和建表过程相似。

假散列表的查找过程和建表过程相似假设给定的值为设给定的值为K K，根据建表时设定的散列，根据建表时设定的散列函数函数h h，计算出散列地址，计算出散列地址h(K)h(K)，若表中该，若表中该地址单元为空，则查找失败；否则将该地地址单元为空，则查找失败；否则将该地址中的结点与给定值址中的结点与给定值K K比较若相等则查比较若相等则查找成功，否则按建表时设定的处理冲突的找成功，否则按建表时设定的处理冲突的方法找下一个地址方法找下一个地址, ,如此反复进行，直到如此反复进行，直到某个地址单元为空某个地址单元为空( (查找失败查找失败) )或者关键字或者关键字比较相等比较相等( (查找成功查找成功) )为止 71n开放地址法一般形式的函数表示开放地址法一般形式的函数表示n  int Hash(KeyType k，，int i)n    {return (h(K)+Increment(i))％％m；； n    }n        若散列函数用除留余数法构造，并假设使若散列函数用除留余数法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数用线性探查的开放定址法处理冲突，则上述函数中的中的h(K)h(K)和和Increment(i)Increment(i)可定义为：可定义为：n  int h(KeyType K)n     { return K％％m；；n     }n  { int Increment(int i)  n     { return i;  /n     } 72n通用的开放定址法的散列表查找算法：通用的开放定址法的散列表查找算法：nint HashSearch(HashTable T，，KeyType K，，int *pos)n  { n    int i=0；；  n    do{n          *pos=Hash(K，，i)；； n          if(T[*pos].key==K) return  l；；  n          if(T[*pos].key==NIL) return  0；； n         }while(++i0)n       printf("duplicate key!")；； n     else  n       Error("hashtableoverflow!")；；  n   }   void CreateHashTable(HashTable T，，NodeType A[]，，int n)n   {  n    int in    if(n>m)  n      Error("Load factor>1")；；n    for(i=0;i

若必须在散列表中删除结点，的删除操作若必须在散列表中删除结点，则不能将被删结点的关键字置为则不能将被删结点的关键字置为NILNIL，而，而应该将其置为特定的标记应该将其置为特定的标记DELETEDDELETEDn一般情况下，当必须对散列表做删除结点一般情况下，当必须对散列表做删除结点的操作时，是采用拉链法来解决冲突的操作时，是采用拉链法来解决冲突 75n性能分析性能分析n因插入和删除的时间均取决于查找，因插入和删除的时间均取决于查找，故只要分析查找操作的时间性能故只要分析查找操作的时间性能n虽然散列表在关键字和存储位置之间虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字但键字的比较就可找到待查关键字但是由于冲突的存在，散列表的查找过是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，不程仍是一个和关键字比较的过程，不过散列表的平均查找长度比顺序查找、过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的二分查找等完全依赖于关键字比较的查找要小得多查找要小得多。