第10章 查找 10.1 查找的基本概念 10.2 顺序表查找 10.3 索引表查找 10.4 树表查找 10.5 哈希表查找.

Presentation on theme: "第10章 查找 10.1 查找的基本概念 10.2 顺序表查找 10.3 索引表查找 10.4 树表查找 10.5 哈希表查找."— Presentation transcript:

1 第10章 查找 10.1 查找的基本概念 10.2 顺序表查找 10.3 索引表查找 10.4 树表查找 10.5 哈希表查找

2 10.1 查找的基本概念 查找（Searching）也称检索，是在数据元素（或称对象）集合中查找是否存在关键码等于某个给定关键码的数据元素。查找问题和数据元素集合的数量有很大的关系，本章讨论的查找问题主要是大数据量的查找问题。

3 在基本的计算机系统中使用查找的地方就有许多。例如，要在DOS系统的文件分配表中查找某个文件，要向Windows系统申请使用某种资源时系统对资源分配表的查找等。在计算机应用系统中使用查找的地方也有许多，如在数据库应用系统中对数据库中某个记录或满足某种条件记录的查找，在高考学生录取应用系统的高考学生成绩表中查找考生号码等于某个值的考生成绩或查找并统计总分超过某个数值的考生人数等。

4 在第9章我们讨论过，关键码有主关键码和次关键码。主关键码是能够惟一区分各个不同对象的关键码，次关键码通常不能惟一区分各个不同对象。以主关键码进行的查找是最经常、也是最重要的查找，我们后边讨论的查找数据结构（除倒排索引表外）都是用主关键码进行的查找。

5 在第3章我们讨论过数据元素的集合构成表，表的存储结构有顺序表和链式表，链式表在大数据量查找时效率很低，并且链式表结构不便进一步重新构造新的存储结构。此外，我们在各种链表类成员函数的设计中也多次使用了链式表的查找方法，所以本章我们不再讨论链式表的查找方法。

6 顺序表的查找效率也不高，为了提高查找效率，我们可以在顺序表的基础上进一步构造新的存储结构，这样的存储结构就是本章要重点讨论的索引表存储结构和树表存储结构。有些树表（如B-树）可用于构造适合动态插入和动态删除的动态索引表。此外，哈希表（或称散列表）存储结构也是一种高效的查找存储结构。

7 查找的结果有成功和不成功两种：查找成功时，返回查找到的对象在对象集合中的位置；查找不成功时的处置，根据下面讨论的查找方法的不同而不同。查找过程按查找使用的操作主要分为两种类型：一种是只在对象集合中查找是否存在某个等于给定关键码的对象，查找成功时返回查找到的对象在对象集合中的位置，查找不成功时返回失败标志，我们称这种查找为静态查找；

8 另一种是不仅在对象集合中查找是否存在某个关键码等于给定关键码的对象，而且当对象集合中不存在关键码等于给定关键码的对象时，把给定关键码的对象插入到对象集合中，我们称这种查找为动态查找。顺序表和等长索引表存储结构适合于静态查找问题；树表和不等长索引表存储结构适合于动态查找问题；哈希表对静态查找问题和动态查找问题均适合。

9 这里讨论的查找问题的对象集合中的对象数据类型与第9章排序问题讨论的对象集合中的对象数据类型类同，即一个对象由若干个数据域组成，其中用作当前查找的数据域称作关键码。为方便读者阅读，我们在这里再次给出对象的数据类型定义如下： typedef int Keytype; struct Datatype { Keytype key; //构造函数 Datatype(){}

10 Datatype(Keytypeitem):key(item){}
//逻辑比较运算符 intoperator<=(constDatatype&item) {returnkey<=item.key;} intoperator<(constDatatype&item) {returnkey<item.key;} intoperator==(constDatatype&item) {returnkey==item.key;}

11 intoperator>=(constDatatype&item)
{returnkey>=item.key;} intoperator>(constDatatype&item) {returnkey>item.key;} intoperator!=(constDatatype&item) {returnkey!=item.key;} }; 上述抽象类型定义存放在文件Datatype.h中。

12 衡量查找算法效率的标准是平均查找长度。平均查找长度（ASL）的定义是查找某对象在对象集合中是否存在所需要进行的对象关键码比较次数的期望值。平均查找长度（ASL）的数学定义为
其中，Pi是要查找对象的出现概率，Ci是要进行的查找次数。查找成功和查找失败的平均查找长度通常不同。查找成功时的平均查找长度用ASL成功表示，查找失败时的平均查找长度用ASL失败表示。

13 10.2 顺序表查找   无序顺序表顺序查找 无序顺序表顺序查找算法的思想是：对于有n个对象的对象集合，从顺序表的一端开始，用给定对象的关键码逐个与顺序表中各对象的关键码比较，若在顺序表中查找到某个对象的关键码和给定对象的关键码相等，则查找成功，否则查找失败。无序顺序表顺序查找算法的C++函数如下：

14 Int SeqSeach(Datatypea［］,intn,Keytypekey)
//在a［0］--a［n-1］中顺序查找关键码为key的对象 //查找成功时返回该对象的下标序号；失败时返回-1 { inti=0; while(i<n&&a［i］.key!=key)i++; if(a［i］.key==key)returni; elsereturn-1; }

15 一个测试程序如下： ＃include<iostream.h> ＃include"Datatype.h"  voidmain(void) { Datatypetest［］={710,342,45,686,6,841,429,134,68,264}; intn=10,key=686,i;  if((i=SeqSeach(test,n,key))!=-1) cout<<"查找成功!该对象是下标为"<<i<<"的对象"; else cout<<"查找失败!该对象在对象集合中不存在"; }

16 运行该测试程序的结果为 查找成功!该对象是下标为3的对象 无序顺序表顺序查找算法使用监视哨技术的C++函数如下： intSeqSeach2(Datatypea［］,intn,Keytypekey) //在a［0］--a［n-1］中顺序查找关键字为key的记录 //查找成功时返回该记录的下标序号；失败时返回-1 { inti=0; a［n］.key=key; //a［n］为监视哨 while(a［i］.key!=key)i++;

17 if(a［i］.key==key)returni;
else return-1; } 监视哨技术是多设置一个单元存放要查找对象的关键码，这样while循环的i<n条件可取消，带监视哨技术的无序顺序表顺序查找算法与不带监视哨技术的无序顺序表顺序查找算法相比，由于前者每次比较的条件少了一半而效率提高近一倍。下面给出使用监视哨技术的测试程序，注意使用监视哨技术的程序需多定义一个单元。

18 ＃include<iostream.h>
＃include"Datatype.h" voidmain(void) { //注意，使用监视哨技术需多定义一个单元 Datatypetest［11］={710,342,45,686,6,841,429,134,68,264}; intn=10,key=686,i; if((i=SeqSeach2(test,n,key))!=-1)

19 cout<<"查找成功!该对象是下标为"<<i<<"的对象"; else
} 设要查找的对象在对象集合中出现的概率均相等，则无序顺序表顺序查找算法查找成功时的平均查找长度ASL成功为 成功

20 无序顺序表顺序查找算法查找失败时的平均查找长度ASL失败为

21 有序顺序表查找 1.有序顺序表顺序查找 对于有序的顺序表进行顺序查找时,不需要比较完所有对象就可知道要查找的对象是否在对象集合中。例如,设顺序表为非递减有序，对象集合为{2,4,6,8,10}，要查找的对象为5，当顺序地同值为6的对象比较完后就可判定对象集合中不存在要查找的对象。 有序顺序表顺序查找算法的C++函数如下： int SeqSSeach(Datatypea［］,intn,Keytypekey) //在有序表a［0］--a［n-1］中顺序查找关键码为key的对象

22 //查找成功时返回该对象的下标序号；失败时返回-1
{ inti=0; while(i<n&&a［i］.key<key)i++; if(a［i］.key==key)returni; elsereturn-1; }

23 有序顺序表顺序查找算法使用监视哨技术的C++函数如下：intSeqSSeach2(Datatypea［］,intn,Keytypekey)
//在有序表a［0］--a［n-1］中顺序查找关键码为key的对象 //查找成功时返回该对象的下标序号；失败时返回-1 { int i=0; a［n］.key=key; //a［n］为监视哨 while(a［i］.key<key)i++;  if(a［i］.key==key)returni; elsereturn-1; }

24 但有序顺序表顺序查找算法查找失败时的平均查找 长度ASL失败为
设要查找的对象在对象集合中出现的概率均相等，则有序顺序表顺序查找算法查找成功时的平均查找长度ASL成功和无序顺序表顺序查找算法查找成功时的平均查找长度ASL成功相同，即 成功 但有序顺序表顺序查找算法查找失败时的平均查找 长度ASL失败为 失败

25 2. 二分查找 二分查找也称作折半查找。二分查找算法的基本思想是：在一个循环过程中，确定出查找区间的中心位置，用待查找对象的关键码和中心位置上对象的关键码比较，若两者相等则查找成功并结束；否则，若前者小于后者，则把查找区间定为原查找区间的前半段继续循环；若前者大于后者，则把查找区间定为原查找区间的后半段继续循环。这样的循环过程一直进行到查找区间的上界小于查找区间的下界为止。  

26 二分查找算法的C++函数如下： intBiSeach(Datatypea［］,intn,Keytypekey) //在有序表a［0］--a［n-1］中二分查找关键码为key的对象 //查找成功时返回该对象的下标序号；失败时返回-1 { intlow=0,high=n-1; //确定初始查找区间上下界 intmid; while(low<=high)

27 mid=(low+high)/2; //确定初始查找区间中心位置
if(a［mid］.key==key)returnmid; //查找成功 elseif(a［mid］.key<key)low=mid+1; elsehigh=mid-1; } return-1; //查找失败

28 对于一个有n个对象的有序表，显然，二分查找算法构造了一棵完全二叉树，其根结点数值为n，每一个二叉分支结点数值为双亲结点数值除2，所有叶结点是数值为1的结点。
n=20+21+…+2k-1=2k-1 则相应的二叉树深度为 k=lb(n+1)

29 在满二叉树的第i层上总共有2i-1个结点，查找该层上的每个结点需要进行的比较次数和该结点所在层的深度（值为i）相同，因此，当假设有序表中每个对象的查找概率相等时，查找成功的平均查找长度为

30 10.3 索引表查找 10.3.1索引表结构 当顺序表中的对象个数非常大时，无论使用顺序表上哪种查找算法都需要很长的时间，可在顺序表上建立索引表提高查找速度。计算机中建立的索引表和我们通常使用的教科书前面的索引用途相同，都是为了提高查找速度，其构造方法也类同。

31 图9―1是一个主表为学生成绩表的例子，查找问题和排序问题所针对的数据结构相同，我们在这里不再重复给出。图10―1是一个主表和一个按关键码key建立的索引表的结构示意图。作为示意，我们只给出了主表中的关键码key值，其他的域名和域值均未给出。索引表中的对象由两个域构成，key域为被索引的若干个对象中关键码的最大值，link域为被索引的若干个对象中第一个对象的下标序号。

32 图10―1 索引表结构示意图

33 当主表上只建立了一个索引表时，满足上述建立索引表的要求是很容易的。但是，当还要对主表建立若干个次关键码的索引表时，要按所有索引表的要求对主表排序是不可能的，因为不同的关键码排序结果会完全不相同。因此，建立索引表的一般方法是先在主表上建立一个和主表项完全相同，但只包含索引关键码和该对象在主表中位置信息的表称作完全索引表，再在完全索引表上建立索引表。

34 主表通常存放在外存，此处的位置即为对象在外存中的地址。图10―2给出了这种带完全索引表的索引表结构示意图。图中完全索引表link域到主表位置的索引关系只象征性地画出了一条，其余的未画出。

35 图10―2 带完全索引表的索引表结构示意图

36 由于索引表和主表的密切关系，所以这种索引表结构不适合于动态查找问题，因为这时会由于每次增加或减少一个对象而要重新构造索引表。
当主表中的对象个数非常庞大时，索引表本身可能也很庞大，此时可按照建立索引表的同样方法对索引表再建立索引表，这样的索引表称作二级索引表。按照同样的方法，还可以在主表上建立三级索引表等。二级以上的索引结构称作多级索引结构。

37 图10―3 不等长索引表结构示意图

38 以上给出的索引表例子都是等长索引表的例子，即索引表中的每个索引项对主表中的对象个数是相等的，如图10―2中的索引表对主表中的对象个数都是5。索引表中的索引项对主表中的对象个数也可以是不相等的，这种索引表称作不等长索引表。图10―3是一个不等长索引表结构示意图。不等长索引表要增加一个数据域存放各个长度值。

39 索引结构查找的效率分析 由于索引表是一种有序顺序表，所以各种有序顺序表上的查找算法都可用于索引表上的查找。在索引结构的对象集合上的查找算法是索引表上的查找算法加上顺序表上的查找算法。其中，索引表上的查找算法和顺序表上的查找算法可以根据关键码有序和无序选用前面所述的相同类型中的任何一种查找算法。

40 在索引结构的对象集合上查找算法的比较次数等于查找索引表的比较次数和查找相应子表的比较次数之和。假设主表中对象的个数为n,索引表的长度为m，相应子表的长度为s，假设在有序的索引表上采用顺序查找算法，则在索引结构的对象集合上查找算法的平均查找长度为

41 倒排索引表 当查找的关键码是次关键码时，用前面的图10―1、图10―2或图10―3所示的索引表结构进行查找就存在问题，因为用次关键码进行查找时查找到的对象个数可能多于一个。倒排索引表是查找次关键码的常用结构。

42 倒排索引表有链式和单元式两种结构。在链式倒排索引表中，先建立一个主关键码的完全索引表，然后对次关键码每一个取值的对象集合建立一个有序静态链表的索引项。这样的索引项结构应包括次关键码、链表长度和静态链表三部分。设有一个包括职工编号和性别等域的职工表，其中职工编号为主关键码，性别为次关键码，性别次关键码的链式倒排索引表的例子如图10―4（a）所示。

43 图中,左部为职工编号主关键码的完全索引表;右部是性别次关键码的倒排索引表。其中，链表长度给出了性别的某个取值所对应的对象个数，静态链表由职工编号主关键码组成，从得到的职工编号主关键码值就可通过图中左部的完全索引表找到该对象，这样的职工编号主关键码有序依次存放，链表的长度又已知，实际上是省去了静态指针域的静态链表。该静态链表的第一个次关键码值指针（即性别为男的头指针）总是0，性别为

44 女的头指针可由基址0和性别为男次关键码的索引长度6求出。图10―4（a）的倒排索引表中有一个链表，所以也称作链式倒排索引表。链式倒排索引表中各个链表的长度不同，使得管理起来比较麻烦，为此有人又提出了单元式倒排索引表结构。在单元式倒排索引表中，索引项中不存放对象的存储地址，而是存放该对象所在外存区域中的标识。为使索引空间最小，索引中的标识使用一个能够转换成地址的二进制数。

45 这样整个次关键码索引就形成了一个二进制数的位矩阵。图10―4（b）给出了图10―4（a）的单元式倒排索引表结构，图中二进制的值为1标识相应的外存区域中具有该次关键码的对象，与二进制的值为0标识相应的外存区域中不具有该次关键码的对象。

46 图10―4 倒排索引表 （a）链式倒排索引表；（b）单元式倒排索引表

47 10.4 树表查找 10.4.1二叉排序树 二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：
树表查找   10.4.1二叉排序树 二叉排序树或者是一棵空树；或者是具有下列性质的二叉树： （1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）每个左右子树也分别为二叉排序树。

48 图10―5是一棵二叉排序树的例子。 由定义和例子都可知，一棵二叉排序树一定是一棵二叉树。 图10―5 一棵二叉排序树

49 二叉排序树类 由于一棵二叉排序树一定是一棵二叉树，所以二叉排序树类的设计和二叉树类的设计非常类同。 ＃include"BiTreeNode.h" //包含二叉树结点类  template<classT>classBiSearchTree { private: BiTreeNode<T>*root; voidPreOrder(BiTreeNode<T>*&t,void(*visit)(Titem));

50 voidInOrder(BiTreeNode<T>*&t,void(*visit)(Titem));
voidPostOrder(BiTreeNode<T>*&t,void(*visit)(Titem)); voidInsert(BiTreeNode<T>*&ptr,constT&item); voidDelete(BiTreeNode<T>*&ptr,constT&item); public: BiSearchTree():root(NULL){}; ~BiSearchTree(){}; voidPreOrder(void(*visit)(Titem)) {PreOrder(root,visit);}

51 voidInOrder(void(*visit)(Titem))
{InOrder(root,visit);} voidPostOrder(void(*visit)(Titem)) {PostOrder(root,visit);} BiTreeNode<T>*&GetRoot() {returnroot;} BiTreeNode<T>*&LeftChild(BiTreeNode<T>*&current) {returnroot!=NULL?current->Left():NULL;} BiTreeNode<T>*&RightChild(BiTreeNode<T>*&current) {returnroot!=NULL?current->Right():NULL;}

52 BiTreeNode<T>*&Find(constT&item);
VoidInsert(constT&item) {Insert(GetRoot(),item);} voidDelete(constT&item) {Delete(GetRoot(),item);} friendistream&operator>>(istream&in,BiSearchTree<T>*&tree); };

53 关于二叉树结点类BiTreeNode见7. 4. 1节。上述二叉排序树类中许多成员函数的实现方法都和7. 4

54 1.查找 template<classT> BiTreeNode<T>*&BiSearchTree<T>::Find(constT&item) { if(root!=NULL) BiTreeNode<T>*temp=root; while(temp!=NULL) if(temp->data==item)returntemp; if(temp->data<item)temp=temp->Right();

55 else temp=temp->Left();
} return NULL; 查找就是一个遍历比较的过程，这里我们只给出了查找成员函数的循环实现方法。查找成员函数的递归实现方法读者可作为作业自己完成。

56 2. 插入 template<classT> voidBiSearchTree<T>::Insert(BiTreeNode<T>*&ptr,constT&item) { if(ptr==NULL) //插入新结点。注意ptr一定是某次递归的左子树指针或右子树指针

57 ptr=newBiTreeNode<T>(item);
if(ptr==NULL) { cerr<<"空间不够!"<<endl; exit(1); } elseif(item<ptr->data)Insert(ptr->Left(),item); //在左子树插入  

58 elseif(item>ptr->data)Insert(ptr->Right(),item);
//在右子树插入   //否则就是item已在二叉排序树中的情况，不做任何操作返回 } 插入操作的要求是首先查找数据元素item是否已在二叉排序树中存在。若已存在，则返回；若不存在，则把该数据元素插入到合适的位置上。实际上，插入过程首先是一个遍历查找过程，这里把这个遍历查找过程设计成递归函数形式；当查找不存在数据元素item时，在当前叶结点的左子树指针位置上或右子树指针位置上插入存放数据元素item的新结点。

59 3.删除 template<classT> voidBiSearchTree<T>::Delete(BiTreeNode<T>*&ptr,constT&item) { BiTreeNode<T>*temp; if(ptr!=NULL) if(item<ptr->data)Delete(ptr->Left(),item); / /在左子树删除 elseif(item>ptr->data)Delete(ptr->Right(),item); //在右子树删除

60 //查找到且为左右子树都存在情况 elseif(ptr->Left()!=NULL&&ptr->Right()!=NULL) { BiTreeNode<T>*min; //寻找值大于当前结点的最小值，即寻找右子树的最左结点 min=ptr->Right(); while(min->Left()!=NULL)min=min->Left();  //把右子树的最左结点的值拷贝到当前结点上

61 ptr->data=min->data;
 //删除右子树的最左结点 Delete(ptr->Right(),min->data); }  //查找到且为其他三种情况 else { temp=ptr; //无孩子时  //注意ptr一定是某次递归的左子树指针或右子树指针 //即要删除结点的双亲结点指针

62 if(ptr->Left()==NULL)ptr=ptr->Right();
//只有右孩子  elseif(ptr->Right()==NULL)ptr=ptr->Left(); //只有左孩子 deletetemp; //删除 } //若ptr==NULL则说明不存在要 删除的数据元素item返回

63 删除过程操作的要求是首先查找数据元素item是否在二叉排序树中存在。若不存在，则返回；若存在，再按四种不同情况分别进行不同的删除操作。这四种不同情况是：
（1）要删除结点无孩子结点； （2）要删除结点只有左孩子结点； （3）要删除结点只有右孩子结点； （4）要删除结点有左、右孩子结点。

64 对于上述四种不同情况，相应的删除方法是：
（1）要删除结点无孩子结点时，直接删除该结点。 （2）要删除结点只有左孩子结点时，删除该结点且使被删除结点的双亲结点指向被删除结点的左孩子结点，注意到算法中ptr一定是某次递归的左子树指针或右子树指针，即要删除结点的双亲结点指针，所以语句ptr=ptr→Left()就完成了链接。 （3）要删除结点只有右孩子结点时，删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点，注意到算法中ptr一定是某次递归的左子树指针或右子树指针，即要删除结点的双亲结点指针，所以语句ptr=ptr→Right()就完成了链接。

65 （4）要删除结点有左、右孩子结点时，分三步完成：首先，寻找值大于删除结点的最小值，即寻找右子树的最左结点；然后，把右子树的最左结点的值拷贝到当前结点上；最后，删除右子树的最左结点。
对于情况（1）、（2）、（3）、（4）的二叉排序树的删除见图10―6。其中:图10-6（a）是要删除结点无孩子结点，图10―6（b）是要删除结点只有左孩子结点，图10―6（c）是要删除结点只有右孩子结点，图10―6（d）是要删除结点有左、右孩子结点。图中虚线箭头所指指针为ptr指针，ptr指针所指结点是当前要删除的结点。

66 图10―6 二叉排序树的删除 （a）无孩子结点；（b）只有左孩子结点； （c）只有右孩子结点；（d）有左、右孩子结点

67 图10―6 二叉排序树的删除 （a）无孩子结点；（b）只有左孩子结点； （c）只有右孩子结点；（d）有左、右孩子结点

68 上述二叉排序树类的定义和实现放在文件BiSearchTree.h中。
二叉排序树类的测试程序如下： ＃include"BiSearchTree.h"  template<classT> voidVisit(Titem) { cout<<item<<""; } voidmain(void) BiSearchTree<int>searchTree;

69 Inta［］={10,7,6,9,20,12,22},n=7; for(inti=0;i<n;i++) searchTree.Insert(a［i］); searchTree.InOrder(Visit); searchTree.Insert(8); cout<<endl; searchTree.Delete(7); }

70 程序的运行结果如下： //初始建立的二叉排序树 //插入8后的二叉排序树 //删除7后的二叉排序树 和二叉树上的游标类设计一样，二叉排序树上也可以设计相应类似的二叉排序树上的游标类。具体设计方法这里就不再讨论，读者可作为练习自己完成。

71 二叉排序树的性能分析 从上面的测试程序可以看出，用二叉排序树的存储结构表示对象集合时，不仅容易进行动态插入和动态删除，而且对二叉排序树进行中序遍历时还可以得到对象集合的有序排列。 从前面的讨论可知，实现动态插入和动态删除算法的主体部分是查找，因此二叉排序树上的查找效率也就表示了二叉排序树的性能。对有n个结点的二叉排序树来说，我们知道，二叉排序树上的平均查找长度是二叉排序树深度的函数，即： 成功

72 从10.2.2节对二分查找算法的效率分析可知，当二叉排序树是满二叉树时有：
从10.2.2节对二分查找算法的效率分析可知，当二叉排序树是满二叉树时有：   n=20+21+…+2k-1=2k-1 则相应的二叉树深度为 k=lb(n+1) 因此，当假设对每个对象的查找概率相等时，查找成功的平均查找长度为 成功

73 但是，当二叉排序树是一棵右分支退化树时，查找成功的平均查找长度和有序顺序表的平均查找长度相同，即为
图10―7是共有7个对象的对象集合相同但形态不同的两棵二叉排序树。其中，图10-7（a）是一棵满二叉排序树，图10―7（b）是一棵右分支退化二叉排序树。 满二叉排序树查找成功的平均查找长度为 成功

74 图10―7 对象集合相同但形态不同的两棵二叉排序树
（a）满二叉排序树；（b）右分支退化二叉排序树

75 造成同样的对象集合却构成不同的二叉排序树形态的是构造二叉排序树时的对象输入次序。例如，上述测试程序中当对象的输入次序为
满二叉排序树查找成功的平均查找长度为 成功 造成同样的对象集合却构成不同的二叉排序树形态的是构造二叉排序树时的对象输入次序。例如，上述测试程序中当对象的输入次序为 a［］={10,7,6,9,20,12,22} 时，将构造出一棵完全二叉排序树。如果上述测试程序中当对象的输入次序为 a［］={6,7,9,10,12,20,22} 时，将构造出一棵右分支退化树。

76 10.4.4平衡二叉树 平衡二叉树是具有二叉排序树性能却消除了二叉排序树的左、右子树高度相差太大所造成的查找效率下降缺陷的二叉树。 若一棵二叉树中每个结点的左、右子树的高度至多相差1，则称此二叉树为平衡二叉树。在算法中，通过平衡因子来具体实现上述平衡二叉树的定义。平衡因子的定义是：平衡二叉树中每个结点有一个平衡因子域，每个结点的平衡因子是该结点左子树的高度减去右子树的高度。

77 图10―8是平衡二叉树和不平衡二叉树的例子，图中结点旁标注的数字为该结点的平衡因子。其中：图10―8（a）是一棵平衡二叉树，图中所有结点平衡因子的绝对值都小于1；图10―8（b）是一棵不平衡二叉树，图10―8（b）中结点30的平衡因子值为-2。

78 图10―8平衡二叉树和不平衡二叉树 （a）平衡二叉树；（b）不平衡二叉树

79 如何使构造的二叉树是一棵平衡二叉树，而不是一棵二叉排序树，关键是每次向二叉树中插入新结点时要保持所有结点的平衡因子满足平衡二叉树的要求。这就要求一旦哪些结点的平衡因子在插入新结点后不满足要求就要进行调整。下面我们首先分析向平衡二叉树中插入新结点后的几种情况。为方便讨论，我们定义HL为某结点左子树高度，HR为某结点右子树高度。

80 当向一棵平衡二叉树插入一个新结点时，若插入后某些结点左、右子树的高度不变就不会影响这些结点的平衡因子，因而也不会因为这些结点造成其他结点的不平衡；若插人后某些结点的左子树高度增加１，就可能影响这些结点的平衡因子，因而也可能会因为这些结点造成其他结点的不平衡。具体又分为三种情况： （1）若插入前部分结点的左子树高度HL与右子树高度HR相等，即平衡因子为0，插人新结点后将使平衡因子变为１，但仍满足平衡二叉树的要求，不需要对它们进行调整。

81 （2）若插入前部分结点的HL小于HR，即平衡因子为-1，插人新结点后将使平衡因子变为0，平衡情况更加改善，也不需要对它们进行调整。

82 若插入新结点后，某些结点的右子树高度增加１，同样也分为类似的三种情况：对于第
（1）种情况，平衡因子将由0变为-1，不需要进行调整；对于第（2）种情况平衡因子由-1变为-2，需要进行调整；对于第（3）种情况平衡因子由1变为0，平衡情况更加改善，也不需要进行调整。 下面我们讨论如何进行调整。调整的原则有两点：一要满足平衡二叉树的要求，二要保持二叉排序树的性质。

83 假定向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性，首先要找出插入新结点后失去平衡的最小子树根结点的指针，然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于１的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况：

84 （1）LL型调整。这是因在A结点的左孩子（设为B结点）的左子树上插人结点，使得A结点的平衡因子由1变为2而引起的不平衡。LL型调整的一般情况如图10―9（a）所示。图中，用长方框表示子树，用长方框的高度（并在长方框旁标有高度值h或h+1）表示子树的高度，用带阴影的小方框表示被插入的结点。

85 调整的方法是：单向右旋平衡，即将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。因调整前后对应的中序序列相同，所以调整后仍保持了二叉排序树的性质不变。LL型调整的一个例子如图10―9（b）所示。

86 （2）RR型调整。 这是因在A结点的右孩子（设为B结点）的右子树上插人结点，使得A结点的平衡因子由-1变为-2而引起的不平衡。RR型调整的一般情况如图10―10（a）所示。调整的方法是：单向左旋平衡，即将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。因调整前后对应的中序序列相同，所以调整后仍保持了二叉排序树的性质不变。RR型调整的一个例子如图10―10（b）所示。

87 （3）LR型调整。这是因在A结点的左孩子（设为B结点）的右子树上插人结点，使得A结点的平衡因子由1变为2而引起的不平衡。LR型调整的一般情况如图10―11（a）所示。调整的方法是：先左旋转后右旋转平衡，即先将A结点的左孩子(即B结点)的右子树的根结点（设为C结点）向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置。因调整前后对应的中序序列相同，所以调整后仍保持了二叉排序树的性质不变。LR型调整的一个例子如图10―11（b）所示。

88 （4）RL型调整。这是因在A结点的右孩子（设为B结点）的左子树上插人结点，使得A结点的平衡因子由-1变为-2而引起的不平衡。RL型调整的一般情况如图10―12（a）所示。调整的方法是：先右旋转后左旋转平衡，即先将A结点的右孩子(即B结点)的左子树的根结点（设为C结点）向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。因调整前后对应的中序序列相同，所以调整后仍保持了二叉排序树的性质不变。RL型调整的一个例子如图10―12（b）所示。

89 图10―9 LL型调整过程 （a）LL型调整的一般情况；（b）LL型调整的一个例子 （2）RR型调整。

90 图10―10 RR型调整过程 （a）一般情况；（b）调整的一个例子

91 图10―11 LR型调整过程 （a）一般情况；（b）调整的一个例子左旋转后

92 图10―12 RL型调整过程 （a）一般情况；（b）调整的一个例子

93 B-树 B-树又称为多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。  B-树中所有结点的孩子结点最大值称为B-树的阶，通常用m表示，从查找效率考虑，要求m≥3。一棵m阶的B-树或者是一棵空树，或者是满足下列要求的m叉树：

94 （2）除根结点外，其它结点至少有m/2的整数上界个孩子结点；
（3）若根结点不是叶结点，则根结点至少有两个孩子结点； （4）每个结点的结构为： n P0 K1 P1 K2 P2 … Kn Pn

95 （5）所有叶结点都在同一层上，即B-树是所有结点的平衡因子均等于0的多路查找树。

96 图10―13 一棵四阶B-树  

97 1.B-树的查找 在一棵B-树上查找关键码为key的方法为：将key与根结点中的Ki进行比较： （1）若key=Ki则查找成功； （2）若key<K1则沿着指针P0所指的子树继续查找； （3）若Ki<key<Ki+1则沿着指针Pi所指的子树继续查找； （4）若key>Kn则沿着指针Pn所指的子树继续查找。

98 2.B-树的插入 将关键码key插入到B-树的过程分两步完成： （1）利用前述的B-树的查找算法找出该关键码的插入结点（注意B-树的插入结点一定是叶结点）。 （2）判断该结点是否还有空位置，即判断该结点是否满足n<m-1，若该结点满足n<m-1，说明该结点还有空位置，直接把关键码key插入到该结点的合适位置上（即满足插入后结点上的关键码仍保持有序）；

99 若该结点有n=m-1，说明该结点已没有空位置，要插入就要分裂该结点。结点分裂的方法是：以中间关键码为界把结点分为两个结点，并把中间关键码向上插入到双亲结点上；若双亲结点未满则把它插入到双亲结点的合适位置上；若双亲结点已满则按同样的方法继续向上分裂。这个向上的分裂过程可一直进行到根结点的分裂，此时，B-树的高度将增1。由于B-树的插入过程或者是直接在叶结点上插入，或者是从叶结点向上的分裂过程，所以新结点插入后仍将保持所有叶结点都在同一层上的特点。

100 图10―14是在一棵三阶B-树上插入的示例。图10―14和下面的图10―15是图10―13完整图示结构形式的简略图示。
在B-树上删除关键码key的过程分两步完成： （1）利用前述的B-树的查找算法找出该关键码所在的结点。 （2）在结点上删除关键码key分两种情况：一种是在叶结点上删除关键码；另一种是在非叶结点上删除关键码。在非叶结点上删除关键码时，假设要删除关键码Ki（1≤i≤n），在删去该关键码后，

101 以该结点Pi所指子树中的最小关键码Kmin来代替被删关键码Ki所在的位置（注意Pi所指子树中的最小关键码Kmin一定是在叶结点上），然后再以指针Pi所指结点为根结点查找并删除Kmin（即再以Pi所指结点为B-树的根结点，以Kmin为要删除关键码再次调用B-树上的删除算法），这样也就把在非叶结点上删除关键码key的问题转化成了在叶结点上删除关键码Kmin的问题。

102 图10―14 一棵三阶B-树上的插入

103 在B-树的叶结点上删除关键码共有以下三种情况：
（1）假如要删除关键码结点的关键码个数n大于(m/2)-1的整数上界，说明删去该关键码后该结点仍满足B-树的定义，则可直接删去该关键码。 （2）假如要删除关键码结点的关键码个数n等于(m/2)-1的整数上界，说明删去该关键码后该结点将不满足B-树的定义，此时若该结点的左（或右）兄弟结点中关键码个数n大于(m/2)-1的整数上界，则把该结点的左（或右）兄弟结点中最大（或最小）的关键码上移到双亲结点中，同时把双亲结点中大于（或小于）上移关键码的关键码下移到要删除关键码的结点中，这样删去关键码key后该结点以及它的左（或右）兄弟结点都仍旧满足B-树的定义。

104 （3）假如要删除关键码结点的关键码个数n等于(m/2)-1的整数上界并且该结点的左和右兄弟结点（如果存在的话）中关键码个数n均等于(m/2)-1的整数上界，这时需把要删除关键码的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键码合并成一个结点。 图10―15是在一棵三阶B-树上删除的示例，其中图10―15（b）是在叶结点上删除关键码的情况（1）；图10―15（c）是在叶结点上删除关键码的情况（2）；图10―15（d）是在叶结点上删除关键码的情况（3）；图10―15（e）是在非叶结点上删除关键码的情况。

105 图10―15 一棵三阶B-树上的删除

106 哈希表查找 哈希表的基本概念 哈希表（又称散列表）是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。哈希表存储的基本思想是：设要存储的对象个数为n，设置一个长度为m（m≥n）的连续内存单元，以线性表中每个对象的关键码Ki（0≤i≤n-1）为自变量，通过一个称为哈希函数的函数h(Ki)，

107 把Ki映射为内存单元的地址（或称下标）h(Ki)并把该对象存储在这个内存单元中。h(Ki)也称为哈希地址（又称散列地址）。从数学的观点看，哈希函数实际上是关键码到内存单元地址的映射。我们把这样构造的线性表存储结构称为哈希表。

108 例10―1建立如下对象集合a的哈希表。 a={180,750,600,430,541,900,460} 分析设计：对象集合a中共有7个对象，对象的关键码为三位整数，如果我们取内存单元个数m为1000，即内存单元区间为000～999，则第一，在m个内存单元中可以存放下n个对象，第二，若取h(K)=K，则当Ki≠Kj（i≠j）时一定有h(Ki)≠h(Kj)。

109 但是，在1000个内存单元中只存储7个对象其空间存储效率太低。我们可适当减少内存单元个数。若取内存单元个数m为13，取哈希函数h(K)为
h(K)=K mod m 即哈希地址h(K)为关键码K除m所得的余数（这在C++中可用K%m运算方便地实现）。有： h(180)=11 h(750)=9 h(600)=2 h(430)=1 h(541)=8 h(900)=3 h(460)=5

110 则对象集合在哈希表中的存储映像为 430 600 900 460 541 750 108

111 若取内存单元个数m为11，仍取哈希函数h(K)为
h(K)=K mod m 有： h(180)=4 h(750)=2 h(600)=6 h(430)=1 h(541)=3 h(900)=9 h(460)=9

112 这时存在哈希冲突。若取第一次哈希冲突函数hl(K)为哈希地址加1，即
hl(K)=h(K)+1 则有 hl(460)=10 则对象集合在哈希表中的存储映像为 430 750 541 180 600 900 460

113 如何尽量避免冲突和冲突发生后如何解决冲突（即为发生冲突的待插人对象找到一个空闲单元）就成了建立哈希表的两个关键问题。在哈希存储中，虽然冲突很难避免，但发生冲突的可能性却有大有小。这主要与三个因素有关：

114 （1）与装填因子α有关。所谓装填因子是指哈希表中已存入的对象数ｎ与哈希地址空间大小ｍ的比值，即α＝ｎ/ｍ，α越小，冲突的可能性就越小;α越大（最大可取1），冲突的可能性就越大。这很容易理解，因为α越小，哈希表中空闲单元的比例就越大，所以待插入对象同已插入存在的对象发生冲突的可能性就越小；反之，α越大，哈希表中空闲单元的比例就越小，所以待插入对象同已插入存在的对象冲突的可能性就越大；另一方面，α越小，存储空间的利用率就越低；反之，存储空间的利用率也就越高。为了既兼顾减少冲突的发生，又兼顾提高存储空间的利用率这两个方面，通常使最终的α控制在0.6～0.9的范围内。

115 （2）与所采用的哈希函数有关。若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生；否则，若哈希函数选择不当，就可能使哈希地址集中于某些区域，从而加大冲突的发生。
（3）与解决冲突的哈希冲突函数有关。哈希冲突函数选择的好坏也将减少或增加发生冲突的可能性。

116 哈希函数构造方法 构造哈希函数的目标是使得到的哈希地址尽可能均匀地分布在m个连续内存单元地址上，同时使计算过程尽可能简单以达到尽可能高的时间效率。根据关键码的结构和分布的不同，可构造出许多不同的哈希函数。这里主要讨论几种常用的整数类型关键码的哈希函数构造方法。 1.直接定址法 直接定址法是以关键码K本身或关键码加上某个数值常量C作为哈希地址的方法。直接定址法的哈希函数h(K)为

117 h(K)=K+C (C≥0) 这种哈希函数计算简单，并且不可能有冲突发生。当关键码的分布基本连续时，可用直接定址法的哈希函数；否则，若关键码分布不连续将造成内存单元的大量浪费。例如，例10-1中若使用直接定址法的哈希函数则需要1000个内存单元来存放7个对象。

118 2. 除留余数法 除留余数法是用关键码K除以哈希表长度m所得的余数作为哈希地址的方法。除留余数法的哈希函数h(K)为 h(K)=K mod m 即哈希地址h(K)为关键码K除m所得的余数（这在C++中可用K%m运算方便地实现）。

119 3. 数字分析法 数字分析法是取关键码中某些取值较均匀的数字位作为哈希地址的方法。它适合于所有关键码值已知的情况。我们可对关键码中每一位的取值分布情况作出分析，从而可以把一个很大的关键码取值区间转化为一个较小的关键码取值区间。例如，要构造一个对象个数n=80，哈希表长度m=100的哈希表。不失一般性我们这里只给出其中8个关键码进行分析，8个关键码值如下所示：

120 K1= K2= K3= K4= K5= K6= K7= K8= 分析上述8个关键码可知，关键码从左到右的第1,2,3,6位取值较集中，不宜作为哈希地址，剩余的第4,5,7,8位取值较均匀，可选取其中的两位作为哈希地址。设选取最后两位作为哈希地址，则这8位关键码的哈希地址集合为（2,75,28,34,16,38,62,20）。

121 哈希冲突解决方法 解决哈希冲突的方法可分为开放定址法和链表法两大类： 1.开放定址法 开放定址法是一类以发生冲突的哈希地址为自变量，通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法。在开放定址法中，哈希表中的空闲单元（假设其下标为d）不仅允许哈希地址为d的同义词关键码使用，而且也允许发生冲突的其他关键码使用，因为这些关键码的哈希地址不为d，所以称为非同义词关键码。

122 开放定址法的名称就是来自此方法的哈希表空闲单元既向同义词关键码开放，也向发生冲突的非同义词关键码开放。至于哈希表的一个地址中存放的是同义词关键码还是非同义词关键码，要看谁先占用它，这和构造哈希表的对象排列次序有关。在开放定址法，以发生冲突的哈希地址为自变量、通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法有很多种，下面介绍常用的几种。

123 （1）线性探查法。 线性探查法是从发生冲突的地址（设为d）开始，依次探查d的下一个地址（当到达下标为m-1的哈希表表尾时，下一个探查的地址是表首地址0），直到找到一个空闲单元为止（当m≥n时一定能找到一个空闲单元）。线性探查法的数学递推描述公式为： 对m取模(1≤i≤m-1)

124 在例10―1中，m=11时产生冲突后所使用的解决冲突的方法就是线性探查法。线性探查法容易产生堆积问题。这是由于当连续出现若干个同义词后（设第一个同义词占用单元d，这连续的若干个同义词将占用哈希表的d,d+1,d+2,…单元），此时，随后任何d+1,d+2,…单元上的哈希映射都会由于前面的同义词堆积而产生冲突，尽管随后的这些关键码并没有同义词。

125 （2）平方探查法。设发生冲突的地址为d，则平方探查法的探查序列为：d+12,d+22,…。平方探查法的数学递推描述公式为：  
对m取模(1≤i≤m-1) 由于平方探查法的探查跨步很大，所以可避免出现 堆积问题。 此外，开放定址法的探查方法还有伪随机序列法、 双哈希函数法等。

126 2. 链表法 链表法是把所有的同义词用单链表链接起来的方法。在这种方法中，哈希表每个单元中存放的不再是对象，而是相应同义词单链表的头指针。由于单链表中可插入任意多个结点，所以此时装填因子α（＝ｎ/ｍ）根据同义词的多少既可以设定为大于1，也可以设定为小于或等于1，通常取α＝1。

127 例10―2用除留余数法哈希函数和链表法解决冲突方法建立如下对象集合α的哈希表。
α={16,74,60,43,54,90,46,31,29,88,77,66,55} 分析设计：对象集合α中共有13个对象，取哈希表的单元个数m=13。除留余数法的哈希函数为： h(K)=K mod m。有： h(16)=3 h(74)=9 h(60)=8 h(43)=4 h(54)=2 h(90)=12 h(46)=7 h(31)=5 h(29)=3 h(88)=10 h(77)=12 h(66)=1 h(55)=3

128 图10―16 用链表法解决冲突的哈希表存储结构

129 哈希表类 这一节我们讨论哈希表类的设计。从前面的分析我们知道，设计一个哈希表主要是要设计哈希函数和哈希冲突函数，以及决定解决哈希冲突的数据结构。下面设计哈希表类的哈希函数采用除留余数法哈希函数，解决哈希冲突的数据结构采用开放定址法，哈希冲突函数采用开放定址法中的线性探查法。

130 ＃include"Datatype.h"  enumKindOfItem{Empty,Active,Deleted}; //表项的状态类型定义 structHashItem //表项结构体定义 { Datatypedata; KindOfIteminfo; HashItem(KindOfItemi=Empty):info(i){} HashItem(constDatatype&D,KindOfItemi=Empty):data(D),info(i){}

131 intoperator==(HashItem&a)
{return data==a.data;} intoperator!=(HashItem&a) {return data!=a.data;} };

132 Datatype结构体中的逻辑等于和逻辑不等于操作符重载见10.1节的Datatype定义。
classHashTable //哈希表类 { private: HashItem*ht; //哈希表数组 intTableSize; //数组的个数 intcurrentSize; //数组当前的表项个数 voidAllocateHt() //分配哈希表数组空间

133 {ht=newHashItem［TableSize］;}
intFindPos(constDatatype&x)const; //定位 public: //构造函数和析构函数 HashTable(intm):TableSize(m) {AllocateHt();currentSize=0;} ~HashTable(void) {delete［］ht;} intFind(constDatatype&x); //查找 intInsert(constDatatype&x); //插入

134 intDelete(constDatatype&x); //删除
intIsIn(constDatatype&x) //是否已存在 {inti=Find(x);returni>=0?1:0;} DatatypeGetValue(inti)const //取值 {returnht［i］.data;} voidClear(void); //清空 };

135 定位成员函数有两种情况：一种情况是插入时寻找空闲单元的定位；另一种是在查找、删除等操作时，寻找是否该对象在哈希表中已存在。我们可以把这两种情况的定位设计成一个成员函数。插入时寻找空闲单元定位的特征是哈希表中不存在该对象，设计定位成员函数返回寻找到的空闲单元地址的负值；查找、删除等操作时寻找该对象是否在哈希表中已存在的特征是哈希表中已存在该对象，设计定位成员函数返回寻找到的存放该对象单元地址的正值；

136 intHashTable::FindPos(constDatatype&x)const
{inti=x.key%TableSize; intj=i; while(ht［j］.info==Active&&ht［j］.data!=x) { j=(j+1)%TableSize; if(j==i)return-TableSize; } if(ht［j］.info==Active)returnj; elsereturn-j;

137 } intHashTable::Find(constDatatype&x) { inti=FindPos(x),j=i; if(j>=0) while(ht［j］.info==Active&&ht［j］.data!=x) j=(j+1)%TableSize; if(j==i)return-TableSize;

138 if(ht［j］.info==Active)returnj;
elsereturn-j; } elsereturnj; intHashTable::Insert(constDatatype&x) { inti=FindPos(x); if(i>0)return0; elseif(i!=-TableSize&&ht［-i］.info!=Active)

139 ht［-i］.data=x; ht［-i］.info=Active; currentSize++; return1; } elsereturn0; intHashTable::Delete(constDatatype&x) { inti=FindPos(x); if(i>=0)

140 ht［i］.info=Deleted; currentSize--; return1; } elsereturn0; voidHashTable::Clear(void) { for(inti=0;i<TableSize;i++) ht［i］.info=Empty; currentSize=0;

141 上述哈希表类放在文件HashTable.h中。
我们以例10―1中的数据集合为例子，当设计m=13时的测试程序如下： ＃include<iostream.h> ＃include"HashTable.h" voidmain(void) { HashTablemyHashTable(13); Datatypea［］={180,750,600,430,541,900,460}; intj,n=7; Datatypeitem;

142 for(inti=0;i<n;i++)
myHashTable.Insert(a［i］); for(i=0;i<n;i++) { j=myHashTable.Find(a［i］); item=myHashTable.GetValue(j); cout<<"j="<<j<<"ht［］="<<item.key<<endl; } intk=myHashTable.IsIn(430); if(k>0)cout<<"OK"; elsecout<<"Failed";

143 myHashTable.Delete(430);
k=myHashTable.IsIn(430); if(k>0)cout<<endl<<"OK"; elsecout<<endl<<"Failed"; }

144 测试程序的运行结果如下： j=11ht［］=180 j=9ht［］=750 j=2ht［］=600 j=1ht［］=430 j=8ht［］=541 j=3ht［］=900 j=5ht［］=460

145 这和我们前面分析给出的对象集合在哈希表中的存储映像图完全一样。即对象集合在哈希表中的存储映像图为：
430 600 900 460 541 750 180 若设计m=11时，只要把测试程序中的哈希表定义语 句改为 Hash Table my Hash Table (11); 即可。