数据结构-C语言版：DS08-查找

1、 第 八 章 查 找 第 八 章 查 找 第 八 章 查 找 第 八 章 查 找 第 八 章 查 找 niiicp1 第 八 章 查 找 第 八 章 查 找 第 八 章 查 找 第 八 章 查 找 niiicp1 第 八 章 查 找 第 八 章 查 找 第 八 章 查 找 high)/2(low 第 八 章 查 找 例：设算法的输入实例中有序的关键字序列例：设算法的输入实例中有序的关键字序列为：为： 05，13，19，21，37，56，64，75，80，88，92。查找的关键字。查找的关键字K=21 第一步：这里的n=11,mid=(1+11)/2=605，13，19，21，37，56，64，

2、75，80，88，92 lowmidhigh 第 八 章 查 找 第二步：mid=(1+5)/2=305，13，19，21，37，56，64，75，80，88，92 lowmidhigh第三步： mid=(4+5)/2=405，13，19，21，37，56，64，75，80，88，92此时Rmid.keyK，return mid4。 lowhighmid 第 八 章 查 找 确定新的查找区间确定新的查找区间 第 八 章 查 找 第 八 章 查 找 如对表如对表R3，7，11，19，30，115，136，141的查找过程：的查找过程： 3 7 11 19 30 115 136 141 3 7 1

3、1 19 30 115 136 141Low mid highLow mid high46782135 第 八 章 查 找 如如k=115k=115的记录结点编号为的记录结点编号为6 6，处于第二层，则比，处于第二层，则比较次数只有两次就可找到（这样的记录共有两个较次数只有两次就可找到（这样的记录共有两个2 21 1=2=2）；查找第三层的记录需要三次比较（这样的记录共有四；查找第三层的记录需要三次比较（这样的记录共有四个个2 22 2=4 =4 ）；查找第）；查找第k k层的记录需要层的记录需要k k次比较（这样的记次比较（这样的记录共有录共有2 2k-1k-1个）个）; ;等等。假定每个记

4、录的查找概率相等，等等。假定每个记录的查找概率相等，即为即为1/n1/n，则其平均查找次数为：，则其平均查找次数为：niiicp1niiicp1niiicp1kniiicp1又根据二叉树的性质：又根据二叉树的性质：k=log2(n+1)故：故： 第 八 章 查 找 二分查找的平均查找长度二分查找的平均查找长度 n二分查找成功时的平均查找长度二分查找成功时的平均查找长度为：为： ASLASLbnbnloglog2 2(n) (n) n二分查找在查找失败时所需比较的关二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超坏情

5、况下查找成功的比较次数也不超过判定树的深度。即为：过判定树的深度。即为：) 1lg( n 第 八 章 查 找 二分查找的优点和缺点二分查找的优点和缺点 虽然二分查找的效率高，但是要虽然二分查找的效率高，但是要将表按关键字排序（有序表）。将表按关键字排序（有序表）。 二分查找二分查找只适用顺序存储结构只适用顺序存储结构。为保持表的有序性，在顺序结构里为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。插入和删除都必须移动大量的结点。 第 八 章 查 找 三、分块查找三、分块查找（索引顺序查找索引顺序查找 ） 分块分块查找表查找表存储结构存储结构 分块分块查找的特点是：按表内记录的某种查

6、找的特点是：按表内记录的某种属性把表（文件）分成属性把表（文件）分成b b个块（子表），个块（子表），并建立一个相应的并建立一个相应的“索引表索引表”，索引表，索引表中每个元素对应一个块，而在索引表中中每个元素对应一个块，而在索引表中是按其关键字有序，但是每一块中的记是按其关键字有序，但是每一块中的记录的存放是任意的，块与块之间必须是录的存放是任意的，块与块之间必须是有序的。即有序的。即分块查找的前提是：分块查找的前提是：文件由文件由 分块有序分块有序 的线性表和索引表组成的线性表和索引表组成。 第 八 章 查 找 分块查找表由分块查找表由 分块有序分块有序 的线性表和索引表组成。的线性表和索

7、引表组成。（1 1） 分块有序分块有序 的线性表的线性表将表（文件）将表（文件）R1.nR1.n平均分为平均分为b b块；每一块中的关键字不块；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是小关键字，即表是 分块有序分块有序 的。的。（2 2）索引表）索引表抽取各块中的抽取各块中的最大关键字及其起始位置最大关键字及其起始位置构成一个索引表构成一个索引表IDl.bIDl.b，即：，即：IDi(1ib)IDi(1ib)中存放第中存放第i i块的最大关键字块的最大关键字及该块在表及该块在表R R中的起始位置。

8、由于表中的起始位置。由于表R R是分块有序的，所以索是分块有序的，所以索引表是一个递增有序表。引表是一个递增有序表。1 1、分块查找表的存储结构、分块查找表的存储结构 第 八 章 查 找 分块查找的基本思想是：分块查找的基本思想是：（1 1）首先查找索引表）首先查找索引表索引表是有序表，可采用二分查找或顺序查找索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。，以确定待查的结点在哪一块。 （2 2）然后在已确定的块中进行顺序查找）然后在已确定的块中进行顺序查找 由于块内无序（也可有序），只能用顺序由于块内无序（也可有序），只能用顺序查找。查找。2 2、分块查找的基本思想、分块

9、查找的基本思想 第 八 章 查 找 例例： 图图8.2所示的表及其索引表是满足上述要求的分块查所示的表及其索引表是满足上述要求的分块查找表，其中找表，其中R只有只有18个结点，被分成个结点，被分成3块，每块中有块，每块中有6个结个结点，第一块中最大关键字点，第一块中最大关键字22小于第二块中最小关键字小于第二块中最小关键字24，第二块中最大关键字第二块中最大关键字48小于第三块中最小关键字小于第三块中最小关键字49。 22488617132212138920334244382448605874498653ID块内最大键值块内最大键值块内第一个元素序号块内第一个元素序号 第 八 章 查 找 （1

10、 1）先在索引表中查找）先在索引表中查找,来确定关键字等于给定值来确定关键字等于给定值K=24K=24的的结点所在的块结点所在的块 因为因为索引索引表小，不妨用表小，不妨用顺序查找顺序查找方法查找索引表。即首方法查找索引表。即首先将先将K K依次和索引表中各关键字比较，直到找到第依次和索引表中各关键字比较，直到找到第1 1个关个关键字大小等于键字大小等于K K的结点，由于的结点，由于K48K48，所以关键字为，所以关键字为2424的的结点若存在的话，则必定在第二块中；然后，由结点若存在的话，则必定在第二块中；然后，由ID2.addrID2.addr找到第二块的起始地址找到第二块的起始地址7 7

11、，从该地址开始在，从该地址开始在R R7.12中进行顺序查找，直到中进行顺序查找，直到R11.key=K为止。为止。（2）在所确定的块内查找关键字等于给定值）在所确定的块内查找关键字等于给定值K=30的结点的结点 在第二块内查找。因在该块中查找不成功，故说明表中在第二块内查找。因在该块中查找不成功，故说明表中不存在关键字为不存在关键字为30的结点。的结点。进行下列查找：进行下列查找： 第 八 章 查 找 算法分析算法分析 分块查找是两次查找过程。整个查找过程分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长的平均查找长度是两次查找的平均查找长度之和。度之和。 以二分查找来

12、确定块，分块查找成功时以二分查找来确定块，分块查找成功时的平均查找长度的平均查找长度( (在索引表中用二分查找，在块内用顺序查找在索引表中用二分查找，在块内用顺序查找) ) ASLASLblkblk= ASL= ASLbnbn+ASL+ASLsqsqloglog2 2(b+1)-(b+1)-1+(s+1)/2log1+(s+1)/2log2 2(n/s+1)+s/2(n/s+1)+s/2 以顺序查找确定块，分块查找成功时的以顺序查找确定块，分块查找成功时的平均查找长度平均查找长度 ASLASLblkblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)=(b+1)/2+(s+1)

13、/2=(s2+2s+n)/(2s) 第 八 章 查 找 在表中插入或删除一个记录时，在表中插入或删除一个记录时，只要找到该记录所属的块，就在该只要找到该记录所属的块，就在该块内进行插入和删除运算。块内进行插入和删除运算。 因块内记录的存放是任意的，所因块内记录的存放是任意的，所以插入或删除比较容易，无须移动以插入或删除比较容易，无须移动大量记录。大量记录。 分块查找的优点分块查找的优点 第 八 章 查 找 8.3 8.3 树表的查找树表的查找1 1、二叉排序树的、二叉排序树的定义定义 二叉排序树二叉排序树(Binary Sort Tree)(Binary Sort Tree)又称又称二叉查找二

14、叉查找( (搜搜索索) )树树(Binary Search Tree)(Binary Search Tree)。其定义为：二叉排。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：序树或者是空树，或者是满足如下性质的二叉树：（1 1）若它的左子树非空，则左子树上所有结点的值）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；均小于根结点的值；（2 2）若它的右子树非空，则右子树上所有结点的值）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；均大于根结点的值；（3 3）左、右子树本身又各是一棵二叉排序树）左、右子树本身又各是一棵二叉排序树。 第 八 章 查 找 （1

15、1） 二叉排序树中任一结点二叉排序树中任一结点x x，其左，其左( (右右) )子树中任一结点子树中任一结点y(y(若存在若存在) )的关键字必的关键字必小小( (大大) )于于x x的关键字。的关键字。（2 2） 二叉排序树中，各结点关键字是惟二叉排序树中，各结点关键字是惟一的。一的。（3 3） 按中序遍历该树所得到的中序序列按中序遍历该树所得到的中序序列是一个递增有序序列。是一个递增有序序列。二叉排序树的特点二叉排序树的特点 第 八 章 查 找 要查找键值等于要查找键值等于k的记录，最先与的记录，最先与根根结点的键值比较，若二者相等，则结点的键值比较，若二者相等，则查找成功查找成功 。若。

16、若k值值小于小于根结点的键值，根结点的键值，则继续查找则继续查找左左子树，反之查找右子树子树，反之查找右子树。若沿某条路经碰到一个端点。若沿某条路经碰到一个端点（叶子）（叶子）还末还末查到，则查找不成功，这也是静态表查到，则查找不成功，这也是静态表的查找。的查找。二叉排序树的查找算法：二叉排序树的查找算法： 第 八 章 查 找 二叉排序树的存储结构二叉排序树的存储结构typedef int KeyTypetypedef int KeyType； typedef structtypedef struct node node KeyTypeKeyType key key； / /* *关键字类型关

17、键字类型* */ / infoType otherinfoinfoType otherinfo； / /* *结点其它信息类结点其它信息类型型* */ / struct node struct node * *lchildlchild，* *rchildrchild； BSTNode BSTNode； / /* *二叉排序树的结点类型二叉排序树的结点类型* */ /typedef BSTNode typedef BSTNode * *BSTreeBSTree； lchildlchildkeykey otherinfootherinfo rchildrchild 第 八 章 查 找 在二叉排序树

18、中插入新结点，要保证插入后仍满足在二叉排序树中插入新结点，要保证插入后仍满足BSTBST性质。其性质。其插入过程是：插入过程是： 1)1)若二叉排序树若二叉排序树T T为空，则为待插入的关键字为空，则为待插入的关键字keykey申请一个新结点，并令其为根；申请一个新结点，并令其为根； 2)2)若二叉排序树若二叉排序树T T不为空，则将不为空，则将keykey和根的关键字和根的关键字比较：比较： (a)(a)若二者相等，则说明树中已有此关键字若二者相等，则说明树中已有此关键字keykey，无，无须插入。须插入。 (b)(b)若若keyTkeykeyTkeykeyTkey，则将它插入根的右子树中。

19、，则将它插入根的右子树中。 二叉排序树插入新结点的过程二叉排序树插入新结点的过程 第 八 章 查 找 二叉排序树插入新结点的算法二叉排序树插入新结点的算法 void InsertBST(BSTree Tptr，Keytype key) BSTNode *f，*p=Tptr； while(p) /*p不空不空*/ if(p-key=key) return； /*找到了，则不插入找到了，则不插入*/ f=p； /*f是是p的双亲的双亲*/ p=(keykey)?p-lchild:p-rchild; 第 八 章 查 找 p=(BSTNode*)malloc(sizeof(BSTNode)； p-ke

20、y=key； p-lchild=p-rchild=NULL； if(TPtr=NULL) /*是空树是空树*/ Tptr=p； /*新结点作为根插入新结点作为根插入*/ else /*不是空树不是空树*/ if(keykey) f-lchild=p；/*新结点作为左孩子插入新结点作为左孩子插入*/ else f-rchild=p； /*新结点作为右孩子插入新结点作为右孩子插入*/ 第 八 章 查 找 从空的二叉排序树开始，每输从空的二叉排序树开始，每输入一个结点数据，就调用一次入一个结点数据，就调用一次插入算法将它插入到当前已生插入算法将它插入到当前已生成的二叉排序树中。成的二叉排序树中。 二

21、叉排序树的生成二叉排序树的生成 第 八 章 查 找 BSTree CreateBST(void) BSTree T=NULL； KeyType key； scanf(“d”，&key)；/*输入一个键值为输入一个键值为key的结点的结点*/ while(key) InsertBST(&T，key)；/*将键值为将键值为key的结点插入到二叉树中的结点插入到二叉树中*/ scanf(d，&key)； /*输入一个键值为输入一个键值为key的结点的结点*/ return T； 第 八 章 查 找 输入实例输入实例(5(5，3 3，7 7，2 2，4 4，8)8)，根据生成二

22、叉排，根据生成二叉排序树算法序树算法生成二叉排序树的过程生成二叉排序树的过程 553253753725374253748 第 八 章 查 找 二叉排序树的删除二叉排序树的删除 从二叉排序树中删除一个结点，从二叉排序树中删除一个结点，不能把以该结点为根的子树都删不能把以该结点为根的子树都删去，并且还要保证删除后所得的去，并且还要保证删除后所得的二叉树仍然满足二叉树仍然满足BSTBST性质。性质。 第 八 章 查 找 1) 1) 进行查找进行查找（去找被删结点）（去找被删结点） 查找时，令工作指针查找时，令工作指针p p指向当指向当前访问到的结点，前访问到的结点，parentparent指向指向p

23、 p的双亲的双亲( (其初值为其初值为NULL)NULL)。若树中。若树中找不到被删结点则返回，否则被找不到被删结点则返回，否则被删结点是删结点是* *p p。删除操作的删除操作的一般步骤一般步骤 第 八 章 查 找 2) 2) 删去删去* *p p。 删删* *p p时，应将时，应将* *p p的子树的子树( (若有若有) )仍连接在树上仍连接在树上且保持且保持BSTBST性质不变。按性质不变。按* *p p的孩子数目分三种的孩子数目分三种情况进行处理。情况进行处理。 删除删除* *p p结点的三种情况结点的三种情况 a)a)* *p p是叶子是叶子( (即它的孩子数为即它的孩子数为0)0)

24、 无须连接无须连接* *p p的子树，只需将的子树，只需将* *p p的双亲的双亲* *parentparent中指向被删结点中指向被删结点* *p p的指针域置空即可。的指针域置空即可。 b)b)* *p p只有一个孩子只有一个孩子* *childichildi不论是左孩子还是右孩子 只需将只需将* *childchild和和* *p p的双亲直接连接后，即可的双亲直接连接后，即可删去删去* *p p。 第 八 章 查 找 c)c)* *p p有两个孩子有两个孩子 先令先令q = pq = p，将被删结点的地址保存在，将被删结点的地址保存在q q中；中；然后找然后找* *q q的中序后继的中

25、序后继* *p p。并在查找过程中。并在查找过程中仍用仍用p p为工作指针，为工作指针，parentparent记住记住* *p p的双亲的双亲位置。位置。* *q q的中序后继的中序后继* *p p一定是一定是* *q q的右子树的右子树中最左下的结点中最左下的结点，它无左子树。因此，可它无左子树。因此，可以将删去以将删去* *q q的操作转换为删去的的操作转换为删去的* *p p的操作，的操作，即在释放结点即在释放结点* *p p之前将其数据复制到之前将其数据复制到* *q q中，中，就相当于删去了就相当于删去了* *q,q,并将并将* *p p的子树嫁接到的子树嫁接到树上树上. . 第

26、八 章 查 找 回顾：二叉排序树的特点二叉排序树的特点1.1.若它的左子树非空，则左若它的左子树非空，则左子树上所有结点的值均子树上所有结点的值均小于根结点的值；小于根结点的值；2.2.若它的右子树非空，则右若它的右子树非空，则右子树上所有结点的值均子树上所有结点的值均大于根结点的值；大于根结点的值；3.3.按中序遍历该树所得到的按中序遍历该树所得到的中序序列是一个递增有中序序列是一个递增有序序列。序序列。 805012060110150557053中序遍历（LVR）：50，53，55，60，70，80，110，120，150 第 八 章 查 找 二叉排序树的删除二叉排序树的删除 删除操作的一

27、般步骤删除操作的一般步骤: :1. 1. 查找要删的结点查找要删的结点 查找时，令工作指针查找时，令工作指针p p指向当前访问指向当前访问到的结点，到的结点，parentparent指向指向p p的双亲的双亲( (其其初值为初值为NULL)NULL)。若树中找不到被删结。若树中找不到被删结点则返回，否则被删结点是点则返回，否则被删结点是* *p p。2.2.如果找到删除结点如果找到删除结点* *p p 应将应将* *p p的子树的子树( (若有若有) )仍连接在树上仍连接在树上且保持且保持二叉排序树的性质不变性质不变FPCPRCLQQLSLS坚持的基本原则：坚持的基本原则：删结点时，保证二叉排

28、序树的性质不变。 第 八 章 查 找 想：想：从一棵二叉排序树中删除一个从一棵二叉排序树中删除一个结点会出现哪几种情况？结点会出现哪几种情况？分析：分析：要删除二叉排序树中的要删除二叉排序树中的* *p p结结点，分三种情况：点，分三种情况：q* *p p是叶子是叶子 q* *p p只有一个子树只有一个子树FPCPRCLQQLSLS注意：注意：此时有四种情况（此时有四种情况（* *p p本身本身可以为左、右子树，且可以为左、右子树，且* *p p的子树的子树也可以为左、右子树）也可以为左、右子树）* *p p有两个子树有两个子树 第 八 章 查 找 1 1* *p p只有左子树，只有左子树，用

29、用* *p p的左子树的的左子树的根代替根代替* *p p SQPLP中序遍历：Q S PL PSQPL中序遍历：Q S PL(2)SPPLQ中序遍历：PL P S QSPLQ中序遍历：PL S Q(1)if(!p-rchild)/右子树空则只需重接它的左子树 tmp=p; p=p-lchild ; free(tmp);* *p p只有一个子树的情况只有一个子树的情况： 第 八 章 查 找 中序遍历：P PR S QSPRQ中序遍历：PR S Q(3)SPPRQ中序遍历：Q S P PRSQPR中序遍历：Q S PR(4)SQPRP2.2.* *p p只有右子树，用只有右子树，用* *p p的

30、右子树的根代替的右子树的根代替* *p pif(!p-lchild)/左子树空则只需重接它的右子树 tmp=p; p=p-rchild ; free(tmp); 第 八 章 查 找 * *p p有两个子树的情况：有两个子树的情况： 分析分析： 针对针对* *p p有两个子树的情有两个子树的情况，把况，把* *p p的两个子树合并为的两个子树合并为一棵树，然后将其连接到一棵树，然后将其连接到* *p p的双亲上。的双亲上。 1.1.删除问题就转化为删除问题就转化为第第种情种情况况。 2.2.要解决的问题转化为要解决的问题转化为如何将如何将两棵二叉排序树合并为一棵二叉两棵二叉排序树合并为一棵二叉排

31、序树排序树。 FPCPRCLQQLSLS 第 八 章 查 找 问题：问题：如何将两棵二叉排序树合并为一棵二叉排序树如何将两棵二叉排序树合并为一棵二叉排序树? ?思考思考：还有没有其它的合并方法？SFPCPRCLQQLSLFPCPRCLQQLSLS分析：分析：据二叉排序树的性质：右子树的值大于左据二叉排序树的性质：右子树的值大于左子树的值。因此，只要找到左子树中值最大的结点子树的值。因此，只要找到左子树中值最大的结点（左子树中最右边的结点，该结点一定没有右子（左子树中最右边的结点，该结点一定没有右子树），使其成为右子树的双亲。树），使其成为右子树的双亲。 第 八 章 查 找 SFPCPRCLQQ

32、LSLFPCPRCLQQLSLStmp=p-lchild; /1.要删除结点的左子树要删除结点的左子树while(tmp-rchild!=0) tmp=tmp-rchild;/2.找到左子树中最右边的结找到左子树中最右边的结/点，即最大的结点点，即最大的结点 tmp-rchild=p-rchild;/3.左子树中最右边的左子树中最右边的 成为右成为右/子树的双亲子树的双亲 tmp=p; p=p-lchild;/5.变为第二种情况处理变为第二种情况处理(删除删除) free(tmp); /6.释放要删除的结点释放要删除的结点 第 八 章 查 找 FPCPRCLQQLMS小结：小结：二叉排序树的删

33、除二叉排序树的删除要删除二叉排序树中的要删除二叉排序树中的* *p p结点结点, ,分三种情况：分三种情况：* *p p为叶子结点为叶子结点* *p p只有左子树或右子树只有左子树或右子树* *p p只有左子树，用只有左子树，用* *p p的左孩子代替的左孩子代替* *p p* *p p只有右子树，用只有右子树，用* *p p的右孩子代替的右孩子代替* *p p* *p p左、右子树均非空左、右子树均非空针对针对* *p p有子树的情况，把有子树的情况，把* *p p的两个的两个子树合并为一棵树，然后将其连接子树合并为一棵树，然后将其连接到到* *p p的双亲上。的双亲上。 第 八 章 查 找

34、 二叉排序树删除算法二叉排序树删除算法 void DelBSTNode(BSTree Tptr，KeyType key) BSTNode *parent=NUll，*p=*Tptr，*q，*child； while(p) if(p-key=key) break； parent=p； p=(keykey)?p-lchild：p-rchild； if(!p) return；/*找不到被删结点则返回找不到被删结点则返回*/ q=p； /*找到时找到时,q记住被删结点记住被删结点p*/ if(q-lchild&q-rchild) for(parent=q，p=q-rchild； p-lchil

35、d； parent=p，p=p-lchild)； /*找被删结点的后继找被删结点的后继*/ if(!parent) Tptr=child； else if(p=parent-lchild) parent-lchild=child； else parent-rchild=child； if(p!=q) q-key=p-key； free(p)； child=(p-lchild)?p-lchild：p-rchild； 第 八 章 查 找 二叉排序树上的查找二叉排序树上的查找 在二叉排序树上进行查找，和二分查找类似，在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。也是一个逐步

36、缩小查找范围的过程。递归的查找算法：递归的查找算法：BSTNode BSTNode * *SearchBST(BSTree TSearchBST(BSTree T，KeyTypeKeyType key) key) if(T=NULL|key=T-key) if(T=NULL|key=T-key) return Treturn T； if(keykey)if(keykey) returnreturn SearchBST(T-lchildSearchBST(T-lchild，key)key)； elseelse return return SearchBST(T-rchildSearchBST(T

37、-rchild，key)key)； 第 八 章 查 找 在二叉排序树上进行查找时的在二叉排序树上进行查找时的平均查找长度和二叉树平均查找长度和二叉树的形态有关：的形态有关：(a)(a)在最坏情况下，二叉排序树是通过把一个有序表的在最坏情况下，二叉排序树是通过把一个有序表的n n个结点依次插入而生成的，此时所得的二叉排序树蜕个结点依次插入而生成的，此时所得的二叉排序树蜕化为一棵深度为化为一棵深度为n n的的单支树单支树，它的平均查找长度和单链，它的平均查找长度和单链表上的顺序查找相同，也是表上的顺序查找相同，也是(n+1)/2(n+1)/2。(b)(b)在最好情况下，二叉排序树在生成的过程中，树

38、的形在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约定树相似的二叉排序树，此时它的平均查找长度大约是是loglog2 2n n。(c)(c)插入、删除和查找算法的时间复杂度均为插入、删除和查找算法的时间复杂度均为O(logO(log2 2n)n)。 第 八 章 查 找 二叉排序树和二分查找的比较二叉排序树和二分查找的比较 就平均时间性能而言，二叉排序树上的查找和就平均时间性能而言，二叉排序树上的查找和二分查找差不多。二分查找差不多。 就维护表的有序性而言，二叉

39、排序树无须移动结就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为平均的执行时间均为O(logO(log2 2n)n)，因此更有效。二分查，因此更有效。二分查找所涉及的有序表是一个向量，若有插入和删除结找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代价是点的操作，则维护表的有序性所花的代价是O(n)O(n)。当有序表是静态查找表时，宜用向量作为其存储结当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；构，而采用二分查找实现其查找操作；若有序

40、表是若有序表是动态查找表，则应选择二叉排序树作为其存储结构。动态查找表，则应选择二叉排序树作为其存储结构。 第 八 章 查 找 - - 树树 B- B- 树的定义树的定义一棵一棵m(m3)m(m3)阶的阶的B-B-树是满足如下性质的树是满足如下性质的m m叉树：叉树：(1)(1)每个结点至少包含下列数据域：每个结点至少包含下列数据域： (n(n，P0P0，KlKl，P1P1，K2K2，KiKi，Pi)Pi)其中：其中： n n为关键字总数为关键字总数 Ki(1ij) Ki(1ij)是关键字，关键字序列递增有是关键字，关键字序列递增有序：序：K1 K2K1 K2Ki key0=k ; T- ke

41、y0=k ; for(i=T-keynum for(i=T-keynum；Kkeyi;i-)Kkeyi;i-)； if(i0 & T-keyi=1) if(i0 & T-keyi=1) * *pos=ipos=i； return Treturn T； if(!T-soni) return NULL if(!T-soni) return NULL； DiskRead DiskRead(T-soni)(T-soni)； return SearchBTree return SearchBTree(T-Soni(T-Soni，k k，pos)pos)； B-B-树的查找算法树的查找算法

42、 第 八 章 查 找 B- B-树上的查找有两个基本步骤：树上的查找有两个基本步骤：在在B-B-树中查找结点，该查找涉及读盘树中查找结点，该查找涉及读盘DiskReadDiskRead操作，属外查找；操作，属外查找；在结点内查找，该查找属内查找。在结点内查找，该查找属内查找。 查找操作的时间为：查找操作的时间为：外查找的读盘次数不超过树高外查找的读盘次数不超过树高h h，故其，故其时间是时间是O(h)O(h)；内查找中，每个结点内的关键字数目内查找中，每个结点内的关键字数目keynumkeynumm(mm(m是是B-B-树的阶数树的阶数) )，故其时间为，故其时间为O(nhO(nh) )。查找

43、操作的时间开销查找操作的时间开销 第 八 章 查 找 B- B-树的生成是从空树起，逐个插入关键字树的生成是从空树起，逐个插入关键字而得到的。而得到的。 （1 1）插入关键字插入关键字K K的方法的方法 首先在树中查找首先在树中查找K K，若找到则直接返回，若找到则直接返回( (假假设不处理相同关键字的插入设不处理相同关键字的插入) )；否则查找操；否则查找操作必失败于某个叶子上，然后将作必失败于某个叶子上，然后将K K插入该叶插入该叶子中。若该叶子结点原来是非满子中。若该叶子结点原来是非满( (指指keynumkeynumMaxkeynumx-keynumMinMin，则只需删去，则只需删去

44、K K及其右指针及其右指针( (* *x x是叶子，是叶子，K K的右指针为空的右指针为空) )即可使删除操作结束。即可使删除操作结束。 情形二情形二：若：若x-keynumx-keynum=Min=Min，该叶子中的关键字个数已，该叶子中的关键字个数已是最小值，删是最小值，删K K及其右指针后会破坏及其右指针后会破坏B-B-树的性质树的性质(3)(3)。若。若* *x x的左的左( (或右或右) )邻兄弟结点邻兄弟结点* *y y中的关键字数目大于中的关键字数目大于MinMin，则将则将* *y y中的最大中的最大( (或最小或最小) )关键字上移至双亲结点关键字上移至双亲结点* *pare

45、ntparent中，而将中，而将* *parentparent中相应的关键字下移至中相应的关键字下移至x x中。中。 第 八 章 查 找 情形三情形三：若：若* *x x及其相邻的左及其相邻的左右兄弟右兄弟( (也可能只有一个兄也可能只有一个兄弟弟) )中的关键字数目均为最中的关键字数目均为最小值小值MinMin，则上述的移动操，则上述的移动操作就不奏效，此时须作就不奏效，此时须* *x x和左和左或右兄弟合并。或右兄弟合并。 第 八 章 查 找 B B树中删除关键字树中删除关键字6 6，7 7的过程的过程 12 689 75 215 1312 79 85 215 13 1258 9 215

46、13 第 八 章 查 找 n n个结点的平衡的二叉排序的高度个结点的平衡的二叉排序的高度H H（即（即lgnlgn）比）比B-B-树的高度树的高度h h约大约大lgtlgt倍。倍。 例如例如m=1024m=1024，则，则lgtlgt=lg512=9=lg512=9。此时若。此时若B-B-树高度为树高度为4 4，则平衡的二叉排序树的高度约为则平衡的二叉排序树的高度约为3636。显然，若。显然，若m m越越大，则大，则B-B-树高度越小。树高度越小。 若要作为内存中的查找表，若要作为内存中的查找表，B-B-树却不一定比平衡树却不一定比平衡的二叉排序树好，尤其当的二叉排序树好，尤其当m m较大时更

47、是如此。较大时更是如此。 因为查找等操作的因为查找等操作的CPUCPU计算时间在计算时间在B-B-树上是树上是 O(mlogtnO(mlogtn)=0(lgn)=0(lgn(m/lgt)(m/lgt) 性能分析性能分析 第 八 章 查 找 8.48.4散列散列(Hash)(Hash)技术技术设所有可能出现的关键字集合记为设所有可能出现的关键字集合记为U(U(简简称全集称全集) )。实际发生。实际发生( (即实际存储即实际存储) )的关键字集的关键字集合记为合记为K K（|K|K|比比|U|U|小得多）。小得多）。 散列方法是散列方法是: :使用函数使用函数h h将将U U映射到表映射到表T0.

48、m-1T0.m-1的下标上的下标上。 这样以这样以U U中关键字为自变量，以中关键字为自变量，以h h为函数的为函数的运算结果就是相应结点的存储地址。从而达运算结果就是相应结点的存储地址。从而达到在到在O(1)O(1)时间内就可完成查找。时间内就可完成查找。散列表散列表(Hash Table)(Hash Table) 第 八 章 查 找 其中：其中： 称称h h为为散列函数散列函数(Hash Function)(Hash Function)。散列。散列函数函数h h的作用是压缩待处理的下标范围，使的作用是压缩待处理的下标范围，使待处理的待处理的|U|U|个值减少到个值减少到m m个值，从而降低

49、个值，从而降低空间开销。空间开销。 T T为为散列表散列表(Hash Table)(Hash Table)。 h(K h(Ki i)(K)(Ki iU)U)是关键字为是关键字为K Ki i结点存储地结点存储地址址( (亦称散列值或亦称散列值或散列地址散列地址) )。 将结点按其关键字的散列地址存储到散将结点按其关键字的散列地址存储到散列表中的过程称为列表中的过程称为散列散列(Hashing)(Hashing) 第 八 章 查 找 冲突：冲突： 两个不同的关键字，由于散列函数值相同，两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置因而被映射到同一表位置( (存储地址存储地址) )上。

50、该现上。该现象称为冲突象称为冲突(Collision)(Collision)或碰撞。发生冲突的或碰撞。发生冲突的两个关键字称为该散列函数的同义词两个关键字称为该散列函数的同义词(Synonym)(Synonym)。 散列表的冲突现象散列表的冲突现象 第 八 章 查 找 其一是其一是记录的个数记录的个数存储空间的大小存储空间的大小 其二是其二是选择合适的散列函数选择合适的散列函数。怎么样才能完全避免冲突？怎么样才能完全避免冲突？最理想的解决冲突的方法是安全避免冲最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：突。要做到这一点必须满足两个条件： 第 八 章 查 找 通常，哈希函

51、数通常，哈希函数h h是一个压缩映是一个压缩映像。虽然实际发生的键值个数像。虽然实际发生的键值个数|K|m|K|m，但，但|U|m|U|m，故无论怎样，故无论怎样设计设计h h，也不可能完全避免冲突。，也不可能完全避免冲突。 冲突不可能完全避免冲突不可能完全避免 第 八 章 查 找 冲突除了与冲突除了与h h相关外，还与表的填满程相关外，还与表的填满程度相关。度相关。 设设m m为表长，为表长，n n为表中填入的结点数为表中填入的结点数（记录数），则将（记录数），则将=n/m=n/m定义为散列表的定义为散列表的装填因子装填因子(Load Factor)(Load Factor)。越大，表越满，

52、越大，表越满，冲突的机会也越大。通常取冲突的机会也越大。通常取11。 影响冲突的因素影响冲突的因素 因此：要尽量减少冲突，就要选择好的因此：要尽量减少冲突，就要选择好的哈希函数哈希函数h(key)和选择恰当的哈希表的长度和选择恰当的哈希表的长度m（既选择好的（既选择好的=n/m=n/m ）。）。 第 八 章 查 找 常用散列函数常用散列函数 平方取中法平方取中法 取关键字的平方值的中间几位数取关键字的平方值的中间几位数 先通过求先通过求关键字的平方值关键字的平方值扩大相近数扩大相近数的差别，然后根据表长度取中间的几位的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的数作为散列

53、函数值。又因为一个乘积的中间几位数中间几位数和乘数的每一位都相关，所和乘数的每一位都相关，所以由此产生的散列地址较为均匀。以由此产生的散列地址较为均匀。 第 八 章 查 找 int Hash(int key) /*假设假设key是是4位整数位整数*/ key* = key； key/=100； /*先求平方值，后去掉末尾的两位数先求平方值，后去掉末尾的两位数*/ return key1000； /*取中间三位数作为散列地址返回取中间三位数作为散列地址返回*/ 平方取中法平方取中法用用C程序实现如下：程序实现如下： 第 八 章 查 找 取关键字或关键字的某个线性函数为哈希地址取关键字或关键字的某

54、个线性函数为哈希地址 即：即：H(k)=key 或或H(k)=a*key+b 其中其中a，b为常数为常数直接定址法直接定址法 第 八 章 查 找 是简单常用的一种方法。它是是简单常用的一种方法。它是以以表长表长m m来除关键字，取其余数作来除关键字，取其余数作为散列地址为散列地址, ,即即 h(key)=keyh(key)=keym m 该方法的该方法的关键是选取关键是选取m m。选取的。选取的m m应使得散列函数值尽可能与关应使得散列函数值尽可能与关键字的各位相关。键字的各位相关。m m最好为素数最好为素数除余法除余法 第 八 章 查 找 该方法包括两个步骤：该方法包括两个步骤： 首先用关键

55、字首先用关键字keykey乘上某个常数乘上某个常数A(0A1)A(0A1)，并抽取出，并抽取出keykeyA A的小数的小数部分；部分； 然后用然后用m m乘以该小数后取整。乘以该小数后取整。 相乘取整法相乘取整法 第 八 章 查 找 相乘取整法的相乘取整法的C C程序如下：程序如下：int Hash(intint Hash(int key) key) double d=key double d=key * *A A； /*不妨设A和m已有定义*/ return (intreturn (int)(m)(m* *( (d-(intd-(int)d)d)； /* (int)表示强制转换后面的表达式

56、为整数*/ 第 八 章 查 找 选择一个随机函数，取关键字选择一个随机函数，取关键字的随机函数值为它的散列地址的随机函数值为它的散列地址 即即 h(key)=random(key)h(key)=random(key)其中其中randomrandom为伪随机函数，但为伪随机函数，但要保证函数值是在要保证函数值是在0 0到到m-1m-1之间。之间。随机数法随机数法 第 八 章 查 找 处理冲突的方法处理冲突的方法 一、一、开放地址法解决冲突的方法开放地址法解决冲突的方法 假设假设哈希表的地址集为哈希表的地址集为0 0m-1m-1，当冲突发生时，即由关，当冲突发生时，即由关键字得到的哈希地址为键字得

57、到的哈希地址为j(0jm-1)j(0jm-1)的位置上已存有的位置上已存有记录，则处理冲突就是为该关键字的记录找到另一个记录，则处理冲突就是为该关键字的记录找到另一个“空空”的哈希地址。的哈希地址。为此为此在处理冲突的过程中，需采在处理冲突的过程中，需采用某种探测技术在散列表中形成一个探测序列用某种探测技术在散列表中形成一个探测序列H Hi ,i ,i=1,2,3,i=1,2,3,，k(Hk(Hi i00,m-1)m-1) 。沿此序列逐个单。沿此序列逐个单元地查找，直到找到给定的或者碰到一个开放的地址元地查找，直到找到给定的或者碰到一个开放的地址( (即该地址单元为即该地址单元为“空空”) )

58、为止（若要插入，在探查到为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单开放的地址，则可将待插入的新结点存人该地址单元）。元）。查找时查找时探查到开放的地址则表明表中无待查的探查到开放的地址则表明表中无待查的关键字，即查找失败。关键字，即查找失败。 第 八 章 查 找 开放地址法的一般形式为：开放地址法的一般形式为： H Hi i=(h(key)+d=(h(key)+di i) )m m 1im-11im-1 其中其中h(key)h(key)为哈希函数，为哈希函数，m m为哈希表长，为哈希表长，d d为增量序列，它可有下列几种取法：为增量序列，它可有下列几种取法： d di

59、 i=1=1，2 2，3 3，m-1m-1 d di i=1=12 2，-1-12 2,2,22 2，-2-22 2,3,32 2，k k2 2 ;(k=m/2);(k=m/2) d di i= =伪随机数序列伪随机数序列 第 八 章 查 找 按照形成探查序列的方法不同，可将开放定址法按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。区分为线性探查法、二次探查法、双重散列法等。线性探查法线性探查法(Linear Probing)(Linear Probing) 该方法的基本思想是：该方法的基本思想是：将散列表将散列表T0.m-1T0.m-1看成是一个循环向量

60、，若初始看成是一个循环向量，若初始探查的地址为探查的地址为d(d(即即h(key)=d)h(key)=d)，则最长的探查序列为：，则最长的探查序列为： d d，d+ld+l，d+2d+2，m-1m-1，0 0，1 1，d-1d-1即即: :探查时从地址探查时从地址d d开始，首先探查开始，首先探查TdTd，然后依，然后依次探查次探查Td+1Td+1，直到，直到Tm-1Tm-1，此后又循环到，此后又循环到T0T0，T1T1，直到探查到，直到探查到Td-1Td-1为止。为止。形成探测序列的方法形成探测序列的方法开放地址法解决冲突开放地址法解决冲突 第 八 章 查 找 双重散列法双重散列法(Double Hashing)(Double Has