第8章 查找 在英汉字典中查找某个英文单词的中文解释；在新华字典中查找某个汉字的读音、含义；在对数表、平方根表中查找某个数的对数、平方根；邮递员送信件要按收件人的地址确定位置等等。可以说查找是为了得到某个信息而常常进行的工作。 计算机、计算机网络使信息查询更快捷、方便、准确。要从计算机、计算机网络中查找特定的信息，就需要在计算机中存储包含该特定信息的表。如要从计算机中查找英文单词的中文解释，就需要存储类似英汉字典这样的信息表，以及对该表进行的查找操作。本章将讨论的问题即是“信息的存储和查找”。 查找是许多程序中最消耗时间的一部分。因而，一个好的查找方法会大大提高运行速度。另外，由于计算机的特性，象对数、平方根等是通过函数求解，无需存储相应的信息表。

第8章 查找 8.1 查找的基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表

8.1 查找的基本概念 查找表：是由具有同一类型（属性）的数据元素（记录）组成的集合。分为静态查找表和动态查找表两类。 静态查找表：仅对查找表进行查找操作，而不能改变的表； 　动态查找表：对查找表除进行查找操作外，可能还要进行向表中插入数据元素，或删除表中数据元素的表。 关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个数据元素， 则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时， 数据元素的值就是关键字。

查找： 根据给定的关键字值，在特定的查找表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在查找中的位置。若找到相应的数据元素， 则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。显然，查找算法中涉及到三类参量： ① 查找对象K（找什么）； ② 查找范围L（在哪找）； ③ K在L中的位置（查找的结果）。其中①、②为输入参量， ③为输出参量，在函数中，输入参量必不可少，输出参量也可用函数返回值表示。

平均查找长度：为确定数据元素在列表中的位置， 需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于长度为n的列表， 查找成功时的平均查找长度为： 其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。

数据元素类型说明 在手工绘制表格时，总是根据有多少数据项，每个数据项应留多大宽度来确定表的结构，即表头的定义。然后，再根据需要的行数，画出表来。在计算机中存储的表与手工绘制的类似，需要定义表的结构，并根据表的大小为表分配存储单元。

本章以后讨论中，涉及的关键字类型和数据元素类型统一说明如下： typedef float KeyType; typedef int KeyType; typedef char* KeyType; typedef struct { KeyType key；// 关键域 …… // 其它字段 } ElemType

对两个关键字的比较约定如下： //对数值型关键字 #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) //对字符型关键字 #define EQ(a,b) (!strcmp((a),(b))) #define LT(a,b) (strcmp((a),(b))<0) #define LQ(a,b) (strcmp((a),(b))<=0)

8.2 静态查找表 静态查找表结构 静态查找表是数据元素的线性表，可以是基于数组的顺序存储或以线性链表存储。 /* 顺序存储结构 */ typedef struct{ ElemType *elem； /* 数组基址 */ int length； /* 表长度 */ }SSTABLE；

//链式存储结构结点类型 typedef struct NODE{ ElemType elem；// 结点的值域 struct NODE *next；// 下一个结点指针域 }NodeType；

8.2.1 顺序查找 顺序查找又称线性查找，是最基本的查找方法之一。其查找方法为：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，并给出数据元素在表中的位置；反之，若直至第一个记录，其关键字和给定值比较都不等，则查找失败，给出失败信息。

以顺序存储为例，数据元素从下标为1的数组单元开始存放，0号单元留空。 int Search _ Seq (SSTable ST，KeyType key) { /*在表ST中查找关键字为kex的数据元素，若找到返回该元素在数组中的下标，否则返回0 */ ST.elem[0].key = key；//”哨兵“ for( i = ST.length ; !EQ(ST.elem[i].key , key)； -- i)； /* 从标尾端向前找 */ return i； }// Search _ Seq

性能分析 就上述算法而言，对于n个数据元素的表，给定值key与表中第i个元素关键码相等，即定位第i个记录时，需进行n-i+1次关键码比较，即Ci=n-i+1。则查找成功时，顺序查找的平均查找长度为： 设每个数据元素的查找概率相等，即 Pi=1/n，则等概率情况下有 查找不成功时，关键码的比较次数总是n+1次。 算法中的基本工作就是关键码的比较，因此，查找长度的量级就是查找算法的时间复杂度，其为O(n)。

许多情况下，查找表中数据元素的查找概率是不相等的。为了提高查找效率，查找表需依据查找概率越高，比较次数越少；查找概率越低，比较次数就较多的原则来存储数据元素。 顺序查找缺点是当n很大时，平均查找长度较大，效率低；优点是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。

8.2.2 有序表的折半查找 有序表即是表中数据元素按关键码升序或降序排列。 折半查找的思想为：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键码相等，则查找成功；若给定值小于中间元素的关键码，则在中间元素的左半区继续查找；若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。

【步骤】 ① low=1；high=length； // 设置初始区间 ② 当low>high时，返回查找失败信息 // 表空，查找失败 ③ low≤high，mid=(low+high)/2; // 取中点 a. 若key<ST.elem[mid].key，high=mid-1；转② // 查找在左半区进行 b. 若key>ST.elem[mid].key，low=mid+1；转② // 查找在右半区进行 c. 若key=ST.elem[mid].key，返回数据元素在表中位置 // 查找成功

算法描述： int Search _ Bin(SSTable ST，KEY key) int mid，flag=0； low=1；high=ST.length； /* ①设置初始区间 */ while(low<=high) /* ②表空测试 */ {mid=(low+high)/2； /* ③得到中点 */ if(EQ(key,ST.elem[mid].key) return mid； //找到待查元素 else if(LT(key,ST.elem[mid].key) high=mid-1；// 调整到左半区 else low=mid+1; } return 0; }// Search _ Bin

折半查找的性能分析 从折半查找过程看，以有序表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续这种操作。所以，对表中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的二叉树为判定树。

折半查找的性能分析 关键字序列：05，13，19，21，37，56，64，75，80，88，92 显然，找到有序表中任一记录的过程，对应判定树中从根结点到与该记录相应的结点的路径，而所做比较的次数恰为该结点在判定树上的层次数。因此，折半查找成功时，关键字比较次数最多不超过判定树的深度。 56 19 05 80 21 64 88 13 37 75 92 查找key=21 由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为［log2n］+1。这样，折半查找成功时，关键字比较次数最多不超过［log2n］+1。

折半查找的性能分析 相应地，折半查找失败时的过程对应判定树中从根结点到某个含空指针的结点的路径，因此，折半查找失败时，关键字比较次数最多也不超过判定树的深度［log2n］+1。 56 19 05 80 21 64 88 13 37 75 92 查找key=85 折半查找时查找不成功的过程就是走了一条从根结点到外部结点的路径，和给定值进行比较的关键字个数等于该路径上内部结点个数。

折半查找的性能分析 为便于讨论，假定表的长度n=2h-1，则相应判定树必为深度是h的满二叉树，h=log2(n+1)。又假设每个记录的查找概率相等， 则折半查找成功时的平均查找长度为

8.2.3静态树表的查找 当有序表中各记录的查找概率相等时，用折半查找其性能最优。如果有序表中各记录的查找概率不等，情况又如何呢？

静态树表的查找 例如：假设有序表中含5个记录，并且各记录的查找概率分别为p1=0.1, p2=0.2, p3=0.1, p4=0.4, p5=0.2。对此有序表进行折半查找，查找成功时的平均查找长度为2.3，但如果在查找时令给定值先和第4个记录的关键字进行比较，比较不相等时再继续在左或右子序列中进行折半查找，则查找成功的平均查找长度为1.8。说明当有序表中各记录的查找概率不等时，按判定树进行折半查找，其性能未必是最优的，此时应如何进行查找呢？

静态树表的查找 如果只考虑查找成功的情况，则使查找性能最佳的判定树是其带权内路径长度之和PH值 取最小值的二叉树。其中n为二叉树上结点的个数（即有序表的长度）；hi为第i个结点在二叉树上的层次数；结点的权wi=cpi(i=1,2,…n)，其中pi为结点的查找概率，c为某个常量。称PH值去最小的二叉树为静态最优查找树。由于构造它花费的时间代价较高，我们来构造近似最优查找树（次优查找树）的有效算法。

构造次优查找树的方法 设按关键字有序的记录序列为： rl, rl+1,… rh (1) 与每个记录相应的权值为 wl, wl+1,… wh 在（1）中取第i个记录构造根结点ri,使得 取最小值，然后分别对子序列rl, rl+1,… ri-1和ri+1, ri+2,… rh构造两可次优查找树，分别设为根结点的左右子树。

=|（swh-swi)-(swi-1-swl-1)| =|(swh+swl-1)-swi-swi-1| 为便于计算 ，引入累计权值和 并设wl-1=0和swl-1=0,则 =|（swh-swi)-(swi-1-swl-1)| =|(swh+swl-1)-swi-swi-1|

构造次优查找树的递归算法 void SecondOptimal(BiTree &T,ElemType R[],float sw[],int low,int high) {i=low; mon=abs(sw[high]-sw[low]; dw=sw[high]+sw[low-1]; for(j=low+1;j<=high;++j) if(abs(dw-sw[j]-sw[j-1])<min) { i=j; min=abs(dw-sw[j]-sw[j-1]) } T=(BiTree)malloc(sizeof(BiNode)); T->data=R[i]; //生成结点 If(i==low) T->lchild=NULL; //左子树为空 Else SecondOptimal(T->lchild,R,sw,low,i-1); //构造左子树 If(i==high) T->rchild=NULL; //右子树为空 Else SecondOptimal(T->rchild,R,sw,i+1,high); //构造右子树 }// SecondOptimal

8.2.4索引顺序表的查找 分块查找又称索引顺序查找，这是顺序查找的一种改进方法。 条件：1、将表分为若干子表； 2、建立一个索引表，每个索引项包含关键字项和指针项； 3、索引表按关键字有序，表或者有序或者分块有序（指第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中所有记录的关键字均大于第二个子表中的最大关键字，依次类推） 。

查找方法： 1、先确定待查记录所在的块（可以顺序查找也可折半查找）。 2、在块中查找记录（只能顺序查找）。

性能分析： 一般情况下，为进行分块查找，可以将长度为n的表均匀地分成b块，每块含s个记录，即b=n/s;又假定表中每个记录的查找概率相等，若用顺序查找确定所在的块，则

8.3动态查找表 动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录

8.3.1二叉排序树 一、二叉排序树定义 二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树： 　⑴ 若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。 ⑵ 左右子树也都是二叉排序树 二叉排序树（BST）又称二叉搜索树，二叉查找树或二叉检索树。

二、二叉排序树查找过程 从其定义可见，二叉排序树的查找过程为： ① 若查找树为空，查找失败。 　　从其定义可见，二叉排序树的查找过程为： 　① 若查找树为空，查找失败。 　② 查找树非空，将给定值key与查找树的根结点关键码比较。 　③ 若相等，查找成功，结束查找过程，否则， a．当key小于根结点关键码，查找将在以左子女为根的子树上继续进行，转① b．当给key大于根结点关键码，查找将在以右子女为根的子树上继续进行，转①

BiTree SearchBST(BiTreeT, KeyType key) 以二叉链表作为二叉排序树的存储结构，则查找过程算法程序描述如下： BiTree SearchBST(BiTreeT, KeyType key) { /*在根指针T所指二叉排序树中， 递归查找某关键字等于key的元素， 若查找成功，则返回指向该元素结点指针， 否则返回空指针 */ if( (!T) ||EQ(key,T->data.key)) return NULL; //查找结束 else if LT(key ,T->data. key) return( SearchBST(T->lchild, key)); //在左子树中继续查找 else return (SearchBST(T->rchild, key)); //在右子树中继续查找 }// SearchBST

三、二叉排序树插入操作和构造一棵二叉排序树 先讨论向二叉排序树中插入一个结点的过程：设待插入结点的关键码为key，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。 构造一棵二叉排序树则是逐个插入结点的过程。

二叉排序树插入操作和构造一棵二叉排序树 例：记录的关键码序列为：63，90，70，55，67，42，98，83，10，45则构造一棵二叉排序树的过程如下： 插入63 插入90 63 90 70 63 90 55 70 67 插入70 插入55 63 90 55 70 插入42 63 90 55 70 67 42 φ 63 90 插入67 63 插入98 63 90 55 70 67 42 98 插入83 63 90 55 70 67 42 98 83 10 63 90 55 70 67 42 98 83 插入10 10 63 90 55 70 67 42 98 83 45 插入45

二叉排序树插入操作和构造一棵二叉排序树 已知一个关键字值为key的结点s， 若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。插入可以用下面的方法进行： ① 若二叉排序树是空树，则key成为二叉排序树的根；② 若二叉排序树非空， 则将key与二叉排序树的根进行比较，如果key的值等于根结点的值，则停止插入；如果key的值小于根结点的值，则将key插入左子树；如果key的值大于根结点的值，则将key插入右子树。相应的递归算法如下：

二叉排序树插入操作和构造一棵二叉排序树 void InsertBST(BiTree *bst, KeyType key) { if (*bst==NULL) /*递归结束条件*/ { s=(BSTree)malloc(sizeof(BSTNode)); /*申请新的结点s*/ s-> key=key;  s->lchild=NULL; s->rchild=NULL;  *bst=s; return; } else if EQ(key ,(*bst)->key) return; else if LT(key ,(*bst)->key) InsertBST(&((*bst)->lchild), key); /*将s插入左子树*/ else if (key > (*bst)->key)  InsertBST(&((*bst)->rchild), key); /*将s插入右子树*/ }

四.二叉排序树删除操作 从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去， 只能删掉该结点，并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。也就是说，在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。 删除操作首先要查找，已确定被删结点是否在二叉排序树中。若不在 ，则不做任何操作；否则，假设要删除的结点为p，结点p的双亲结点为f，并假设结点p是结点f的左孩子（右孩子的情况类似）。以下分三种情况进行讨论。

⒈ *p结点为叶结点，由于删去叶结点 后不影响整棵树的特性，所以，只 需将被删结点的双亲结点相应指针 　 域改为空指针。

⒉若p结点只有左子树，或只有右子树，则可将p的左子树或右子树直接改为其双亲结点f的左子树，即：f->lchild=p->lchild（或f->lchild=p->rchild）； free(p)； F P Pl *f *p F P *f *p pr F *f *p Pl F *f *p Pr 删除p 删除p

⒊ *p结点既有左子树Pl又有右子树Pr，可按中序遍历保持有序进行调整。 首先找到p结点在中序序列中的直接前驱s结点， 然后用s结点的值替代p结点的值，再将s结点删除，原s结点的左子树改为s的双亲结点q的右子树：p->data=s->data；q->rchild= s->lchild；free(s)； F P C Q S Cl Ql Sl PR f p c q s F S C Q Cl Ql Sl PR f p c q s 删除结点P

BiTNode * DelBST(BiTree t, KeyType k) /*在二叉排序树t中删去关键字为k的结点*/ { BiTNode *p=t, *f=NULL, *s , *q;  while(p) /*查找关键字为k的待删结点p*/ { if EQ(p->key,k ) break; /*找到， 则跳出查找循环*/ f=p; /*f指向p结点的双亲结点*/ if LT（ k, p->key ） p=p->lchild;  else p=p->rchild;  }  if (p==NULL) return t; /*若找不到， 返回原来的二叉排序树*/

if(p->lchild==NULL) /*p无左子树*/ { if(f==NULL) t=p->rchild; /*p是原二叉排序树的根*/ else if (f->lchild==p) /*p是f的左孩子*/ f->lchild=p->rchild ； /*将p的右子树链到f的左链上*/ else /*p是f的右孩子*/ f->rchild=p->rchild ; /*将p的右子树链到f的右链上*/ free(p); /*释放被删除的结点p*/ }

else /*p有左子树*/ { q=p; s=p->lchild;  while(s->rchild) /*在p的左子树中查找最右下结点*/ {q=s; s=s->rchild; } if(q==p) q->lchild=s->lchild ; /*将s的左子树链到q上*/ else q->rchild=s->lchild;  p->key=s->key; /*将s的值赋给p*/ free(s);  } return t;  } /*DelBST*/

二叉排序树的查找分析 在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根到该结点的过程，和给定值比较的关键字个数等于结点所在的层次数，因此，和折半查找类似，与给定值比较的关键字个数不超过树的深度。然而，折半查找长度为n的表的判定树是唯一的，而含有n个结点的二叉排序树却不唯一。即含有n个结点的二叉排序树的平均查找长度和树的形态有关。 思考：含有n个结点的二叉排序树的最好平均查找长度是多少？最差又是多少？ 最好：log2n 最差:(n+1)/2

8.3.2平衡二叉树(AVL树) 平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过1。 平衡因子:结点的左子树深度减去它的右子树深度。 引入平衡二叉排序树的目的是为了提高查找效率。

在平衡二叉树上插入或删除结点后，可能使树失去平衡，因此，需要对失去平衡的树进行平衡化调整。设a结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来有以下四种情况：

一. 右单旋转（LL型） LL rc=p->lchild; p->lchild=lc->rchild; A B BL x BR AR p h-1 A 2 B 1 BL BR x AR p LL rc=p->lchild; p->lchild=lc->rchild; Lc->rchild=p;p=lc; 具体算法P236 :算法9.9 【调整策略】 调整后的子树除了各结点的平衡因子绝对值不超过1，还必须是二叉排序树。 LL型失衡的特点是：A->bf=2，B->bf=1。

二. 左单旋转 RR rc=p->rchild; p->rchild=lc->lchild; A B AL BL BR x P A -2 B -1 BL BR x AL h-1 p RR rc=p->rchild; p->rchild=lc->lchild; Lc->lchild=p;p=rc; 具体算法P236 :算法9.10 【调整策略】 调整后的子树除了各结点的平衡因子绝对值不超过1，还必须是二叉排序树。 RR型失衡的特点是：A->bf=-2，B->bf=-1。

三. 先左后右双向旋转(LR型） C A B BL CL CR AR x A C B BL CL CR AR x 先左旋 C BL B A 1 A 2 B -1 BL CL CR AR x h-1 h-2 A C B BL CL CR AR x 2 先左旋 C BL B A CL AR CR x -1 再右旋

四. 先右后左双向旋转(RL型） B A AL CL x CR BR C A C BR CR AL CL x B 先右旋 A C AL B -1 A -2 AL h-1 CL x CR h-2 BR C A -2 C 1 h-1 BR CR h-2 AL CL x B 先右旋 A C AL h-1 B -1 CL x CR h-2 BR 再左旋

在平衡的二叉排序树T上插入一个关键码为key的新元素，递归算法可描述如下： ⒈　若T为空树，则插入一个数据元素为key的新结点作为T的根结点，树的深度增1； ⒉　若key和T的根结点关键码相等，则不进行插入；

⒊　若key小于T的根结点关键码，而且在T的左子树中不存在与key有相同关键码的结点， 则将新元素插入在T的左子树上，并且当插入之后的左子树深度增加1时，分别就下列情况进行处理：

⒋　若key大于T的根结点关键码，而且在T的右子树中不存在与key有相同关键码的结点，则将新元素插入在T的右子树上，并且当插入之后的右子树深度增加1时，分别就不同情况处理之。其处理操作和 (3.) 中所述相对称.

typedef struct BSTNODE{ ElemType data; /*数据元素*/ int bf; /*平衡因子*/ struct BSTNODE *lchild,*rchild; /*左右子女指针*/ }BSTNode,*BSTree; /*结点类型*/

右旋算法 void R_Rotate(BSTree &p) { /*对以*p为根的子树作右单旋转处理，处理之后，p指向新的树根结点，即旋转处理之前的左子树的根结点*/ lc=p->lcild; /*lc指向*p左子树根结点*/ p->lchild=lc->rchild; /*lc的右子树挂接*p的左子树*/ lc->rchild=p; p=lc; /* p指向新的根结点*/ } //R_Rotate 算法9.9

左旋算法 void L_Rotate(BSTree &p) { /*对以*p为根的子树作左单旋转处理，处理之后，p指向新的树根结点，即旋转处理之前的右子树的根结点*/ rc=p->rchild; /*rc指向*p左子树根结点*/ p->rchild=lc->lchild; /*rc的左子树挂接*p的右子树*/ lc->lchild=p; p=rc; /* p指向新的根结点*/ } //L_Rotate 算法9.10

#define LH 1 /* 左高 */ #define EH 0 /* 等高 */ #define RH 1 /* 右高 */

void LeftBalance((BSTree &T) { /*对以*p指向的结点为根的子树，作左平衡旋转处理，处理之后，*p指向的结点为子树的新根*/ lc=p->lchild; /*lc指向*T左子树根结点*/ switch(lc->bf) /*检查*T左子树平衡度，并作相应处理*/ {case LH: /*新结点插在*T左子女的左子树上，需作单右旋转处理*/ T->bf=lc->bf=EH; R_Rotate(T);break; case EH: /*原本左、右子树等高，因左子树增高使树增高*/ (*p)->bf=LH; *paller=TRUE;break; case RH: //新结点插在*T左子女的右子树上，需作先左后右双旋处理 rd=lc->rchild; /*rd指向*T左子女的右子树根结点*/ switch(rd->bf) /*修正*T及其左子女的平衡因子*/ { case LH:T->bf=RH;lc->bf=EH;break; case EH:T->bf=lc->bf=EH;break; case RH:T->bf=EH;lc->bf=LH;break; }/*switch(rd->bf)*/ rd->bf=EH; L_Rotate(&((*p)->lc)); //对*T的左子树作左旋转处理 R_Rotate(T); /*对*T作右旋转处理*/ }//switch(lc->bf) }//LeftBalance 算法9.12

在平衡的二叉排序树中插入一个元素的算法 Status InsertAVL(BST &t,ElemType e, Boolean &taller) { /*若不存在和e有相同关键码的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔型变量taller反映T长高与否*/ if(!T) /*插入新结点，树“长高”，置taller为TURE*/ {T=(BSTree)malloc(sizeof(BSTNode)); T->data=e; T->lchild=T->rchild=NULL;T->bf=EH; taller=TRUE; }//if else { if(EQ(e.key,T->data.key) )//树中存在和e有相同关键码的结点，不插入 { taller=FALSE; return 0;}

在平衡的二叉排序树中插入一个元素的算法（续） if(LT(e.key,T->data.key)) { /*应继续在*T的左子树上进行*/ if(!InsertAVL(T->lchild,e,taller)) return 0; /*未插入*/ if(taller) /*已插入到*T的左子树中，且左子树增高*/ switch(T->bf) /*检查*T平衡度*/ {case LH: /*原本左子树高，需作左平衡处理*/ LeftBalance(T); taller=FALSE;break; case EH: /*原本左、右子树等高，因左子树增高使树增高*/ T->bf=LH; taller=TRUE;break; case RH: /*原本右子树高，使左、右子树等高*/ T->bf=EH; taller=FALSE;break; }//switch(T->bf) }//if

在平衡的二叉排序树中插入一个元素的算法（续） else /*应继续在*t的右子树上进行*/ { if(!InsertAVL(T->rchild),e, taller)) return 0; /*未插入*/ if(taller) /*已插入到*T的右子树中，且右子树增高*/ switch(T->bf) /*检查*T平衡度*/ {case LH: /*原本左子树高，使左、右子树等高*/ T->bf=EH; taller=FALSE;break; case EH: //原本左、右子树等高，因右子树增高使树增高 T->bf=RH; taller=TRUE;break; case RH: /*原本右子树高，需作右平衡处理*/ RightBalance(T); taller=FALSE;break; }//switch(T->bf) }/*else*/ return 1; }/*InsertAVL*/ 算法9.11

8.3.3 B-树 B-树是一种平衡的多路查找树，它在文件系统中很有用。 定义：一棵m阶的B-树，或者为空树，或为满足下列特性的m叉树： ⑵若根结点不是叶子结点，则至少有两棵子树； ⑶除根结点之外的所有非终端结点至少有m/2 棵子树； ⑷所有的非终端结点中包含以下信息数据：（n，A0，K1，A1，K2，…，Kn，An）  其中：Ki（i=1,2,…,n）为关键码，且Ki<Ki+1，Ai为指向子树根结点的指针(i=0,1,…,n)，且指针Ai-1所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An所指子树中所有结点的关键码均大于Kn， m/2 1≤n≤m 1 ，n为关键码的个数。 ⑸所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

1 39 F 53 64 3 47 11 27 99 2 43 78 35 一棵4阶的B-树 18

B-树的插入和删除 1.插入 在B-树上插入关键码与在二叉排序树上插入结点不同，关键码的插入不是在叶结点上进行的，而是在最底层的某个非终端结点中添加一个关键码，若该结点上关键码个数不超过m-1个，则可直接插入到该结点上；否则，该结点上关键码个数至少达到m个，因而使该结点的子树超过了m棵，这与B-树定义不符。所以要进行调整，即结点的“分裂”。方法为：关键码加入结点后，将结点中的关键码分成三部分，使得前后两部分关键码个数均大于等于 -1,而中间部分只有一个结点。前后两部分成为两个结点，中间的一个结点将其插入到父结点中。若插入父结点而使父结点中关键码个数超过m-1，则父结点继续分裂，直到插入某个父结点，其关键码个数小于m。可见，B-树是从底向上生长的。

在一棵3阶B树上插入结点的演示 45 24 53 90 3 12 37 50 61 70 100 45 24 53 90 3 12 30 37 50 61 70 100 插入关键字30 插入关键字26

45 24 53 90 3 12 26 30 37 50 61 70 100 53 90 45 24 30 3 12 26 50 61 70 100 37 分裂 插入关键字85

53 90 45 24 30 3 12 26 50 61 70 85 100 37 53 70 90 45 24 30 3 12 26 50 100 37 61 85 分裂 53 45 70 24 30 3 12 26 50 100 37 61 85 90 再分裂

算法描述 Status InserBTree(Btree &t,KeyType kx,Btree q,int i) { /*在m阶B树*t上结点*q的key[i],key[i+1]之间插入关键码kx*/ /*若引起结点过大，则沿双亲链进行必要的结点分裂调整，使*t仍为m阶B树*/ x=kx;ap=NULL;finished=FALSE; while(q&&!finished) { Insert(q,i,x,ap);/*将x和ap分别插入到q->key[i+1]和q->ptr[i+1]*/ if(q->keynum<m) finished=TRUE; /*插入完成*/ else { /*分裂结点*p*/ s=m/2;split(q,s,ap);x=q->key[s]; /*将q->key[s+1…m],q->ptr[s…m]和q->recptr[s+1…m]移入新结点*ap*/ q=q->parent; if(q) i=Search(q,kx); /*在双亲结点*q中查找kx的插入位置*/ }/*else*/ }/*while*/

if(!finished) /*(*t)是空树或根结点已分裂为*q和*ap*/ NewRoot(t,q,x,ap); /*生成含信息(t,x,ap)的新的根结点*t,原*t和ap为子树指针*/ return OK } 算法9.14

2.删除 （1）被删关键字所在结点中的关键字数目不小于 则只需从该结点中删去该关键字Ki和相应指针Ai,树的其他部分不便。 删除12 45 24 53 90 3 12 37 50 61 70 100 45 24 53 90 3 37 50 61 70 100 删除12

（2）被删关键字所在结点中的关键字树木等于 -1， 而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于 -1，则需将其兄弟结点中的最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键子所在结点中。 45 24 53 90 3 37 50 61 70 100 45 24 61 90 3 37 53 70 100 删除50

（3）被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于 -1。假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到Ai所制兄弟结点中。如果因此使双亲结点中的关键字数目小于 -1，则依次类推。 45 24 90 3 37 61 70 100 45 24 61 90 3 37 53 70 100 删除53

8.4哈希表 以上讨论的查找方法，由于数据元素的存储位置与关键码之间不存在确定的关系，因此，查找时，需要进行一系列对关键码的查找比较，即“查找算法”是建立在比较的基础上的，查找效率由比较一次缩小的查找范围决定。理想的情况是依据关键码直接得到其对应的数据元素位置，即要求关键码与数据元素间存在一一对应关系，通过这个关系，能很快地由关键码得到对应的数据元素位置。

【例】11个元素的关键码分别为 18，27，1，20，22，6，10，13，41，15，25。选取关键码与元素位置间的函数为 f(key)=key mod 11。 1.通过这个函数对11个元素建立查找表 2. 查找时，对给定值key依然通过这个函数计算出地址，再将key与该地址单元中元素的关键码比较，若相等，查找成功。

8.4.1哈希表与哈希方法： 选取某个函数，依该函数按关键码计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值key计算地址，将key与地址单元中元素关键码进行比，确定查找是否成功，这就是哈希方法(杂凑法)；哈希方法中使用的转换函数称为哈希函数(杂凑函数)；按这个思想构造的表称为哈希表(杂凑表)。

对于n个数据元素的集合，总能找到关键码与存放地址一一对应的函数。若最大关键为m，可以分配m个数据元素存放单元，选取函数f(key)=key即可，但这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突(Collision)，映射到同一哈希地址上的关键码称为同义词。可以说，冲突不可能避免，只能尽可能减少。所以，哈希方法需要解决以下两个问题：

1. 构造好的哈希函数 （1）所选函数尽可能简单，以便提高转换速度。 （2）所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间 浪费。 2. 制定解决冲突的方案。

8.4.2 常用的哈希函数 一. 直接定址法 Hash(key)=a·key+b (a、b为常数) 即取关键码的某个线性函数值为哈希地址，这类函数是一一对应函数，不会产生冲突，但要求地址集合与关键码集合大小相同，因此，对于较大的关键码集合不适用。

二. 除留余数法 Hash(key)=key mod p (p是一个整数) 即取关键码除以p的余数作为哈希地址。使用除留余数法，选取合适的p很重要，若哈希表表长为m，则要求p≤m，且接近m或等于m。p一般选取质数，也可以是不包含小于20质因子的合数。

三. 数字分析法 设关键码集合中，每个关键码均由m位组成，每位上可能有r种不同的符号。 数字分析法根据r种不同的符号，在各位上的分布情况，选取某几位，组合成哈希地址。所选的位应是各种符号在该位上出现的频率大致相同。

四、平方取中法 对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。 五、折叠法(Folding) 此方法将关键码自左到右分成位数相等的几部分，最后一部分位数可以短些，然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。这种方法称为折叠法。

8.4.3 处理冲突的方法 一. 开放定址法 所谓开放定址法，即是由关键码得到的哈希地址一旦产生了冲突，也就是说，该地址已经存放了数据元素，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。 Hi=(Hash(key)+di) mod m ( 1≤i < m ) 其中：Hash(key)为哈希函数， m为哈希表长度di为增量序列 。（1） di = 1，2，……，m-1为线性探测再散列；（2） di = 1，-1，4，-4，9，-9，……，为二次探测再散列；（3） di = 伪随机数序列，称伪随机探测再散列。

【例】关键码集为 {47，7，29，11，16，92，22，8，3}，哈希表表长为11，Hash(key)=key mod 11，用线性探测法处理冲突，建哈希表。

二、再哈希法 Hi=RHi(key) Rhi均是不同的函数。 三、链地址法 四、建立一个公共溢出区

8.4.4哈希表的查找分析 哈希表的查找过程基本上和造表过程相同。一些关键码可通过哈希函数转换的地址直接找到，另一些关键码在哈希函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对哈希表查找效率的量度，依然用平均查找长度来衡量。

哈希表的查找分析 查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素： 1. 哈希函数是否均匀； 2. 处理冲突的方法； 3. 哈希表的装填因子。

哈希表的查找分析 填入表中的元素个数 哈希表的装填因子定义为：α= ──────────── 哈希表的长度 α是哈希表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

哈希表的查找分析 ■线性探测再散列 ■链址法 查找成功时 查找成功时  查找失败时 查找失败时 从以上讨论可知：哈希表的平均查找长度是装填因子α的函数，而与待散列元素数目n无关。因此，不论元素数目n有多大，都能通过调整α，使哈希表的平均查找长度较小。 ■伪随机探测再散列、 二次探测   查找成功时 查找失败时

作业 9.1, 9.3, 9.9 ,9.11, 9.14, 9.19, 9.21