第九章查找

9.1.基本概念 9.2顺序表 9.2.1顺序查找 9.2.2二分法查找 9.2.3分块查找

9.3散列表 9.3.1概述 9.3.2散列函数的构造方法 9.3.3处理冲突的方法 9.3.4散列表的性能分析

9.4 .树表 9.4.1 二叉排序树 9.4.2 平衡的二叉排序树 9.4.3 B－树 小结

9.1 基本概念 ◆查找表：由同一类型的数据元素（记录）组成的集合，可以由任意的数据结构实现。 ◆查找表的操作：（1）查询某个“特定的”数据元素是否在查找表中；（2）查找某个“特定的”数据元素的属性；（3）在查找表中插入一个数据元素；（4）从查找表中删除某个数据元素。 ◆静态查找表:若对查找表只作前两种操作，此类查找表称静态查找表。 ◆动态查找表:若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素， 此类查找表为动态查找表。

◆关键字：数据元素中某个数据项的值，用它可以标示查找表中的一个数据元素。主关键字可以唯一地标识一个记录，次关键字用以识别若干记录。 ◆查找：就是根据给定的关键字值，在特定的查找表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在查找表中的位置。如果找到数据元素，则称查找成功，否则查找失败。 ◆平均查找长度：为了确定数据元素在查找表中的位置需要和给定值进行比较的关键字个数期望值，称为查找算法在查找成功时的平均查找长度。

•对于长度为n的查找表，查找成功的平均查找长度为： •其中Pi为查找表中第i个数据元素的概率，Ci为找到查找表中第i个元素时，已经进行的比较次数。由于查找算法的基本元素是关键字之间的比较操作，所以可以平均查找长度来衡量查找算法的性能。

9.2顺序表 顺序表中相邻的两个记录Ri和Ri+1在存储器中的物理位置也是相邻的，因此存储结构采用的是顺序结构。 顺序结构有关C++语言描述的数据类型定义 ：（为了简单起见，我们假设记录的排序码为整型，在本章以后讨论的顺序表中均采用这样的向量存储结构）

#define maxn 30 // 文件中最大记录数 typedef struct { int key; // 假设记录排序码为整数 char *other; // 记录中其它信息域，暂不用 } record; typedef record recordfile[maxn]; •顺序表的查找方法分为顺序查找法、二分法（折半）查找法以及分块（索引）查找法。

9.2.1顺序查找 顺序查找（sequential search)用待查的关键字值与线性表里各结点的关键字值逐个比较， 44 32 11 查找76 44 32 11 23 76 69 87 56 0 1 2 3 4 5 6 7 8 查找次数＝5 ↑i ↑i ↑i ↑i ↑i 监视哨 •查找第n个元素：比较次数1 查找第n-1个元素：比较次数2 ………. 查找第1个元素：比较次数 n 查找第i个元素：比较次数n+1-i 查找失败：比较次数n+1

顺序查找的算法:查找前对结点之间并没有排序要求.用C++语言描述的顺序查找算法如下 ： int seqserch(recordfile r,int k,int n) //k为给定值,n为表长; //返回0表明查找不成功,否则返回关键字等于k的记录在表r中的序号. { int i=n; r[0].key=k; while(r[i].key!=k) i--; return i;}

在此算法中，查找之前，先对r[0]的关键字赋值为k，目的在于免去查找过程中每一步都要检测整个表是否查找完毕。在此r[0]起了监视哨的作用 这种改进能使顺序查找在n≥1000时进行一次查找所需要的平均时间几乎减少一半，从而提高查找效率。 •顺序查找方法的ASL： ••有n个记录的表，查找成功时的平均查找长度为

ASL = np1 +(n-1)p2 + … + 2pn-1 + pn 。 在顺序查找时，ci取决于所查记录在表中的位置。如查找记录r[n]时，仅需比较一次，而查找记录r[1]时，则需比较n次。一般地，ci=n-i+1。故顺序查找的平均查找长度为： ASL = np1 +(n-1)p2 + … + 2pn-1 + pn 。 ••假设每个记录的平均查找概率相等即：Pi = 1/n 。 。

算法的评价 顺序查找法和后面将要讨论的其它查找法相比，其缺点是平均查找长度较大，特别是当 n 很大时，查找效率低。然而，它有很大的优点：算法简单且适用面广。它对表的结构无任何要求，无论记录是否按关键字有序均可应用，而且上述所有讨论对线性链表也同样适用。

9.2.2二分法查找 查找过程：每次将待查记录所在区间缩小一半， 适用条件：采用顺序存储结构的有序表 •算法实现: 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值 初始时，令low=1,up=n,mid=(low+up)/2 让k与mid指向的记录比较 若k==r[mid].key，查找成功 若k<r[mid].key，则up=mid-1 若k>r[mid].key，则low=mid+1 重复上述操作，直至low>up时，查找失败

例：查找21 95 89 80 75 63 56 34 21 19 15 5 1 2 3 4 5 6 7 8 9 10 11 ↑low ↑mid (1+11)/2=6 ↑up 95 89 80 75 63 56 34 21 19 15 5 1 2 3 4 5 6 7 8 9 10 11 ↑low ↑mid (1+5)/2=3 ↑up 95 89 80 75 63 56 34 21 19 15 5 1 2 3 4 5 6 7 8 9 10 11 low ↑ ↑mid (4+5)/2=4 ↑up

例：查找83 95 89 80 75 63 56 34 21 19 15 5 1 2 3 4 5 6 7 8 9 10 11 ↑low ↑mid (7+11)/2=9 ↑up 95 89 80 75 63 56 34 21 19 15 5 1 2 3 4 5 6 7 8 9 10 11 low↑ ↑mid (10+11)/2=10 ↑up 95 89 80 75 63 56 34 21 19 15 5 1 2 3 4 5 6 7 8 9 10 11 up ↑ ↑ low Up <low 查找失败

二分查找的算法用C++语言描述如下 int bins(recordfile r, int K, int n) //二分查找 { int l=1,u=n,m; // 置区间初值 while(l<=u) { m=(l+u)/2; if(K>r[m].key) l=m+1; // 修改下界 l 值 else if(K<r[m].key) u=m-1; // 修改上界u值 else return m; // 查找成功 } return 0; // 脱离while,则 l>u 查找不成功

算法查找的性能 判定树：描述查找过程的二叉树叫判定树。有n个结点的判定树的深度为log2n+1 ； 二分查找成功时比较次数最多不超过树的深度 ；二分查找在查找不成功时和关键字比较的次数最多不超过 log2n +1； 二分查找的ASL 表的长度为：n=2h-1(h=log2(n+1)) 每个元素的查找概率相等Pi=1/n 平均查找长度 :

算法的评价 二分查找的效率比顺序查找高，但二分查找只能适用于有序表，且存储结构仅限于向量（对线性链表无法进行折半查找），当表经常需要插入或删除一个元素时，就需要来回移动元素。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

9.2.3分块查找 将查找表分成若干个块（子表）块内无序，但块与块之间应有序构造一个索引表。其中每个索引项对应一个块并记录每个块的起始位置，以及每块中的最大关键字（或最小关键字）。索引表按关键字有序排列 查找过程：先根据索引表确定待查记录所在块，再在块内顺序查找 适用条件：分块有序表

例：查找37 75 45 22 47 58 61 48 26 37 42 33 08 09 15 12 查找表 索引表

平均查找长度为: Lb为查找索引表确定所在块的平均查找长度，Lw为在块中查找元素的平均查找长度。 长度为n的表分成b块，每块含有s个记录，即b=n/s；表中每个记录的查找概率相等，则每块查找的概率为1/b，块中每个记录的查找概率为1/s 用顺序查找确定所在块，则平均查找长度为： 用二分查找确定所在块，则查找长度为：

算法的评价 分块查找的优点是:在线性表中插入或删除一个结点时，只要找到该结点应属的块，然后在块内进行插入和删除运算，由于块内结点的存放是任意的，所以插入或删除比较容易，不需要移动大量的结点。分块查找的主要代价是增加一个辅助数组的存储空间和将初始线性表分块排序的运算。另外当大量的插入和删除运算使块中的结点数分布不均匀时，查找速度会下降。

9.3散列表 9.3.1 概述 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。 散列表定义： 记录的存储位置和它的关键字之间建立一个确定的对应关系h，使每个关键字和结构中一个唯一的存储位置相对应。查找时，根据h找到给定值k的映象h(k)，若结构中存在关键字和k相等的记录，则必定在h(k)的存储位置上。我们称这个对应关系h为散列（Hash）函数用散列函数建立的表称为散列表。

例如，一张全国各地区的各民族人口统计表 ······· 1 2 上海 北京 回族 汉族 总人数 地区名 编号 满族 以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2

9.3.2 散列函数的构造方法 直接定址法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=a·key+b 特点：直接定址法所得地址集合与关键字集合大小相等，不会发生冲突。实际中能用这种哈希函数的情况很少。 特征位抽取法 构造：抽取关键字中某几位随机性较好的数位，然后把这些数位拼接起来作为散列地址。

分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机 所以：取任意两位或两位 与另两位的叠加作散列 地址

平方取中法 构造：取关键字平方后中间几位作哈希地址适用于当无法确定关键字中哪几位分布比较均匀时 K的内部编码为11，E的内部编码为05，Y的内部编码为25，A的内部编码为01，B的内部编码为02。关键字“KEYA”的内部代码为11052501，同理得到关键字“KYAB”、“AKEY”的内部编码，然后进行对关键字平方运算，取出第7到第9位作为该关键字的散列地址

折叠法构造： 将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做散列地址移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况如国际标准图书编号 0-442-20586-4采用这两种折叠法求得的散列地址分别如下所示： 5 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088 移位叠加 0 2 2 4 6 0 9 2 H(key)=6092 间界叠加

除留余数法构造： 取关键字被某个不大于散列表表长m的数p除后所得余数作散列地址，即H(key)=key MOD p，m特点：简单、常用，可与上述几种方法结合使用 表（18，75，60，43，54，90，46） m=p=13 H（18）＝ 18 ％ 13＝5 H（75）＝ 75 ％ 13＝10 0 1 2 3 4 5 6 7 8 9 10 11 12 54 43 18 46 60 75 90 H（60）＝ 60 ％ 13＝8 H（43）＝ 43 ％ 13＝4 H（54）＝ 54 ％ 13＝2 H（90）＝ 90 ％ 13＝12 H（46）＝ 46 ％ 13＝7

随机数法 构造：取关键字的随机函数值作散列地址，即H(key)=random(key) 适于关键字长度不等的情况 选取散列函数，考虑以下因素： ⑴ 计算散列函数所需的时间( 包括硬件指令的因素 )； ⑵ 关键字的长度； ⑶ 散列表的大小； ⑷ 关键字的分布情况； ⑸ 记录的查找频率

9.3. 3 处理冲突的方法 1、开放定址法： 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,……k(km-1) 其中：H(key)——散列函数 m——散列表表长 di——增量序列 分类： 线性探测再散列：di=1,2,3,……m-1 二次探测再散列：di=1²,-1²,2²,-2²,3²,……±k²(k≤m/2) 伪随机探测再散列：di=伪随机数序列

例 表长为16的散列表中已填有关键字为19，70，33和38的记录，H(key)=key MOD 13, 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 18 18 18 25 冲突 冲突 不冲突 不冲突 线性探测再散列 不冲突 冲突 冲突 不冲突 插入第六个记录，其关键字为18 ， H(18)=5 线性探测再散列 用二次探测再散列 伪随机探测再散列

2、再散列法 方法：构造若干个散列函数，当发生冲突时，计算下一个散列地址，即：Hi=Rhi(key) i=1,2,……k 其中：Rhi——不同的散列函数。 特点：计算时间增加。 3、链地址法： 方法：将所有关键字为同义词的记录存储在同一线性链表中并用一维数组存放头指针 用链地址法解决冲突的散列造表算法 ：

#include <iostream.h> #define listlen 13 struct record { int key; record *next; }; typedef record RECF[listlen]; int modh (int ); //Hash函数(除留余数法) void chainh(int ,RECF ,int (*hash)(int )); prhashlist(RECF ); //输出散列表

void main(void) { int i,x; RECF r; for(i=0;i<listlen;i++){ r[i].key=0; r[i].next=NULL; } cin>>x; while(x){ chainh(x,r,modh); cin>>x; } prhashlist(r); } // 其中参数int(*hash)(int)是指向函数的指针，它返回一个整数（散列地址） //用链地址法解决冲突的散列造表算法 //根据(*hash)函数造散列表

void chainh(int k,RECF r,int (*hash)(int)) { int addr; record *p,*q; //用链地址法解决冲突 addr=(*hash)(k); if (!r[addr].key)r[addr].key=k; else if(r[addr].key!=k) {p=r[addr].next; q=&r[addr]; while(p && p->key!=k) { q=p; p=p->next; } if(!p){ p=new record; p->key=k; p->next=NULL; q->next=p; } }

int modh (int k) //Hash函数(除留余数法) { return(k % listlen); } prhashlist(RECF r) //输出散列表 { int i; record *p; cout<<"no.\tkey\t link\n"; for(i=0;i<listlen;i++) { if(!r[i].key) cout<<i<<"\t\t^\n"; else{ cout<<i<<"\t"<<r[i].key<<"\t-->"; p=r[i].next; while(p){ cout<<p->key<<"-->"; p=p->next; } cout<<"^"<<endl; }}}

例：已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），散列表表长为13，散列函数为H（key）＝key％13，则用链地址法处理冲突的结果

9.3.4 散列表性能分析 散列查找过程仍是一个给定值与关键字进行比较的过程 评价散列查找效率仍要用ASL 9.3.4 散列表性能分析 散列查找过程仍是一个给定值与关键字进行比较的过程 评价散列查找效率仍要用ASL 散列查找过程与给定值进行比较的关键字的个数取决于： 1、散列函数 2、处理冲突的方法 3、散列表的填满因子ą=表中填入的记录数/散列表长度

已有散列表a[16]如图所示（上面是地址，最下一行是插入/查找某记录所需的关键字比较次数），Hash函数 H(key)=key  13，处理冲突用二次探测再散列 平均查找长度分别为 ：ASL=(1*6+2*2+3*3+5)/12=2

用链地址法处理冲突的散列表 平均查找长度为 ：ASL=(1*7+2*4+3)/12=1.5

α=表中的记录数/表长 直观地看，α越小，发生冲突的可能性就越小；α越大，即表越满，发生冲突的可能性就越大，查找时所用的比较次数就越多。因此散列表查找成功的平均查找长度Sn和α有关。 在线性探测再散列时： Snl≈(1+1/(1-α))/2 在伪随机探测再散列，二次探测再散列及再散列时： Snr≈-Ln(1-α)/α 在链地址法中： Snc≈1+α/2

9.4 树表 二叉排序树又称为二叉查找树，它是一种特殊结构的二叉树，其定义为：二叉排序树或者是一个空树，或是具有下面性质的二叉树 9.4 树表 9.4.1 二叉排序树 二叉排序树又称为二叉查找树，它是一种特殊结构的二叉树，其定义为：二叉排序树或者是一个空树，或是具有下面性质的二叉树 1、若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 2、若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 3、它的左右子树也分别为二叉排序树。

二叉排序树的一个重要性质：中序遍历一个二叉排序树时可以得到一个递增有序序列。上图所示二叉树是个二叉排序树。若中序遍历，得到一个递增的有序序列：1，2，3，4，5，6，7，8，9。

二叉排序树的操作中，使用二叉链表作为存储结构，其结点说明如下： //treenode.h #define NULL 0 template<class T> class TreeNode //声明二叉树结点类 {public: T data; TreeNode<T>* lchild; TreeNode<T>* rchild; TreeNode(){} //缺省构造函数

TreeNode(const T& item, TreeNode<T>. lptr=NULL,TreeNode<T> TreeNode(const T& item, TreeNode<T> *lptr=NULL,TreeNode<T> *rptr=NULL); void FreeTreeNode(TreeNode<T> *p){delete p;} //释放二叉树的一个结点存储空间 }; template<class T> TreeNode<T>:: // 构造函数 TreeNode(const T& item, TreeNode<T> *lptr,TreeNode<T> *rptr) :data(item),lchild(lptr),rchild(rptr){ }

用C++描述二叉排序树如下 #include <iostream.h> #include "treenode.h" #define endmark –999 // 输入-999则表示结束本次建立二叉排序树的输入 template<class T> class SortBinTree:public TreeNode<T> { public: TreeNode<T>* root; //二叉排序树根结点指针 TreeNode<T>* f; //二叉排序树某结点的双亲结点指针 SortBinTree():root(NULL),f(NULL){}

void ins_bs(TreeNode<T>*, TreeNode<T>* &); //向二叉排序树中插入结点 void ins_bs_nr(TreeNode<T>*, TreeNode<T>* &); //插入结点的非递归算法 void creat_bst(TreeNode<T>* &r); //从空树出发，依次插入结点建立二叉排序树 void del_bst(TreeNode<T>* p); //二叉排序树删除结点 //二叉排序树中查找关键字为K的结点. TreeNode<T>* Search_bst(TreeNode<T>* t,T K); void inorder(TreeNode<T>* r ); // 中序遍历以r为根结点指针的二叉排序树};

二叉排序树的插入 插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子 template<class T> // 将s所指结点插入到以t为根结点指针的二叉排序树中 void SortBinTree<T>::ins_bs(TreeNode<T>* s, TreeNode<T>* &t) { if(t==NULL) t=s; //s所指结点插入到“空”二叉排序树中 else if(s->data<t->data)ins_bs(s,t->lchild); // s所指结点插入到左子树中else ins_bs(s, t->rchild); // s所指结点插入到右子树中 }

二叉排序树的生成 整棵树的构成只要从空树出发，依次插入结点即可。例如，已知序列 45，24，53，12，28，90 整棵树的构造过程 ：

二叉排序树的删除： 要删除二叉排序树中的p结点，分三种情况： 1、p为叶子结点，修改p双亲f的指针f->lchild=NULL 或 f->rchild=NULL 2、p只有左子树或右子树： p只有左子树，用p的左孩子代替p p只有右子树，用p的右孩子代替p

3、p左、右子树均非空 在删除P之前，中序遍历该二叉树得到的序列为{ … ClC … QlQSlSPPrF … }，在删除P之后，为保持其它元素之间的相对位置不变，可以有两种做法：其一是令P的左子树为F 的左子树，而P的右子树为S的右子树，如图 (c)所示 ；其二是令P的直接前驱（或直接后继）替代P，然后再从二叉排序树中删除它的直接前驱（或直接后继），图 (d)所示 。

删除算法如下所示 ： template<class T> //二叉排序树中删除结点 void SortBinTree<T>::del_bst(TreeNode<T>* p) // p指向二叉排序树上将被删除结点，数据成员f为p所指结点的双亲结点指针 { TreeNode<T>* s; if(p->lchild==NULL) // *p无左子树 if(f==NULL)root=p->rchild; // *p是根结点 else if(f->lchild==p)f->lchild=p->rchild; // *p是*f的左孩子 else f->rchild=p->rchild; // *p是*f的右孩子

else if(p->rchild==NULL) // *p有左子树，但无右子树 if(f==NULL)root=p->lchild; // *p是根结点 else if(f->lchild==p)f->lchild=p->lchild; else f->rchild=p->lchild; else // *p既有左子树，也有右子树 { s=p->lchild; //令s指向p的左子树中最大结点 while(s->rchild!=NULL) s=s->rchild; if(f==NULL){ root=p->lchild; s->rchild=p->rchild; } else if(f->lchild==p){f->lchild=p->lchild; s->rchild=p->rchild;} else{f->rchild=p->lchild; s->rchild=p->rchild; }} FreeTreeNode(p);}

二叉排序树的查找 查找过程： 首先将待查关键字k与根结点关键字t进行比较，如果： (1)k=t，则返回根结点地址； (2)k<t，则进一步查找左子树； (3)否则，进一步查找右子树； 二叉排序树的查找的递归算法：

template<class T> //二叉排序树中查找关键字为K的结点. // 若查找成功，数据成员f是所查得结点的双亲结点指针 TreeNode<T>* SortBinTree<T>::Search_bst(TreeNode<T>* t,T K) // 在以t为根指针的二叉排序树中检索关键字为K的结点，返回结点指针 { TreeNode<T>*p; p=t; if(p==NULL||p->data==K)return p; // 此处返回“空”则查找不成功 else{ f=p; if(K<p->data)p=Search_bst(p->lchild,K); // 到左子树中查找 else p=Search_bst(p->rchild,K); // 到右子树中查找 }}

在二叉排序树上进行查找的平均查找长度和二叉排序树的形态有关 a: ASL＝（1+2+2+3+3+3）/ 6＝ 14/6 b:ASL＝（1+2+3+4+5+6）/ 6＝ 21/6

在最坏情况下，二叉排序树是为一棵深度为n的单支树，它的平均查找长度是（n+1）/2。 在最好的情况下，二叉排序树是一棵形态与二分查找的判定树形似，此时他的平均查找长度大约是log2n。 考虑n个结点有n！种二叉排序树（其中有形态相同的）可能，可以证明，对这些二叉排序树的查找长度进行平均，得到的平均查找长度仍然是O(log2n)

9.4.2平衡的二叉排序树(AVL树) 起因：提高查找速度，避免最坏情况出现。虽然完全 二叉树的树型最好，但构造困难。常使用平衡二叉树。 定义：平衡二叉排序树（又称AVL树），或者是一棵 空树，或者是具有下列性质的二叉树：它的左子树和 右子树都是平衡二叉树，且左子树和右子树的深度之 差的绝对值不超过1。 平衡因子定义：该结点的左子树的深度减去它的右子 树的深度 。 平衡二叉树上所有结点的平衡因子只可能是-1，0和1

平衡二叉树失衡的情况和相应的调整方法 一般情况下，假设由于在二叉排序树上插入结点而失 去了平衡的最小子树的根结点指针为A（即A是离插 入键最近，且平衡因子绝对值超过1的祖先结点）， 则失去平衡之后进行调整的规律可以归纳为下列四种 情况：（结点外的值是该结点的平衡因子） LL型： 如图在A的左子树B的左子树插入新结点S，由于A 的平衡因子由1增加到2，导致失衡。为了恢复二叉 排序树的平衡性，需要进行一次顺时针的旋转操作

LL型失衡特点为：A－>bf＝2，B－>bf＝1。相应调整操作可用如下语句完成： BL BR AR S (b)调整后恢复平衡 (a)插入新结点S后失去平衡 二叉排序树的LL型平衡旋转 2 1 H-1 H LL型失衡特点为：A－>bf＝2，B－>bf＝1。相应调整操作可用如下语句完成： B＝A－>lchild；A－>lchild＝B－>rchild；B－>rchild＝A； A－>bf＝0；B－>bf＝0；

最后，将调整后的二叉排序树的根结点B“接到”A处。 令A原来的父指针为FA如果FA非空，则用B代替A做 FA的左子树或者右子树；否则原来A就是根结点，此 时应该令根指针t指向B。相应调整操作可用如下语句 if(FA==NULL) t＝B； else if (A==FA－>lchild) FA－>lchild＝B； else FA—>rchild＝B；

LR型： 由于在A的左子树的B的右子树上插入结点，使A的 平衡因子由1增至2而失去了平衡，需进行两次旋转 操作（先逆时针，后顺时针），如图所示。

LR型失衡特点为：A－>bf＝2，B－>bf＝-1。相应调整操作可用如下语句完成： B＝A－>lchild；C＝B－>rchild； B－>rchild＝C－>lchild；A－>lchild＝C－>rchild； C－>rchild＝A；C－>lchild＝B； 新结点S的插入位置有三种情况：1、在CL下插入S。2、在CR下插入S。3、B 的右子树为空，C本身就是插入的新的结点S。针对上述三种不同情况，修改A、B、C的平衡因子：

if(S->key < C->key) //在CL下面插入S { A－>bf＝－1；B－>bf＝0；C－>bf＝0} if(S->key > C->key) // 在CR下面插入S { A－>bf＝0；B－>bf＝1；C－>bf＝0} if(S->key == C->key) //C是新的插入结点S { A－>bf＝0；B－>bf＝0；} 最后，将调整后的二叉排序树的根结点C接到A处。令A原来的父指针为FA如果FA非空，则用C代替A做FA的左子树或者右子树；否则原来A就是根结点，此时应该令根指针t指向C： if (FA == NULL) t＝C；else if (A == FA－>lchild) FA－>lchild＝C；else FA—>rchild＝C；

RR 型： 由于在a的右子树的右子树上插入结点，使a的平衡因子由-1减至-2而失去平衡，需进行一次逆时针旋转操作。如图所示。

由于在a的右子树的左子树上插入结点，使a的平衡因子由-1 减至-2而失去平衡，需进行两次旋转操作（先顺时针，后逆时针）。如图所示。 RL 型： 由于在a的右子树的左子树上插入结点，使a的平衡因子由-1 减至-2而失去平衡，需进行两次旋转操作（先顺时针，后逆时针）。如图所示。

LL型与RR型对称，LR型与RL型对称 综上所述插入一个新的结点S时，主要包括以下三步： 1）查找应该插入位置，同时记录距离插入位置最近的可能失衡结点A（A的平衡 因子不等于0）。 2）插入新的结点S，并修改从A到S路径上各个结点的平衡因子。 3）根据A、B的平衡因子，判断是否失衡以及失衡类型，并做相应的处理。

平衡树结点类(AVL_NODE) 及平衡树类(AVLtree)的声明： #define NULL 0 template<class T> class AVL_Node //平衡树(AVL)结点类的定义(AVLnode.h) { public:T data; int bf; AVL_Node<T> *lchild,*rchild; AVL_Node(){} //缺省构造函数 AVL_Node(const T& item, int b=0,AVL_Node<T> *lptr=NULL,AVL_Node<T> *rptr=NULL):data(item),bf(b),lchild(lptr),rchild(rptr){ }};

//AVL树根结点指针 template<class T> class AVLtree:public AVL_Node<T> { public: AVL_Node<T>* root; AVLtree():root(NULL){ }; void inorder(AVL_Node<T>* t); // 中序遍历AVL树 void LL_rotation(AVL_Node<T>*, AVL_Node<T>*); // LL型旋转 void LR_rotation(AVL_Node<T>*&, AVL_Node<T>*); // LR型旋转 void RR_rotation(AVL_Node<T>*,AVL_Node<T>*); //

void RL_rotation(AVL_Node<T>*&,AVL_Node<T>*); // RL型旋转 RR型旋转 void RL_rotation(AVL_Node<T>*&,AVL_Node<T>*); // RL型旋转 void AVL_ins(AVL_Node<T>*, AVL_Node<T>*&); // 在平衡树上插入结点 void creat_AVL(AVL_Node<T>* &r); // 建立平衡树的算法 };

void RL_rotation(AVL_Node<T>*&,AVL_Node<T>*); // RL型旋转 RR型旋转 void RL_rotation(AVL_Node<T>*&,AVL_Node<T>*); // RL型旋转 void AVL_ins(AVL_Node<T>*, AVL_Node<T>*&); // 在平衡树上插入结点 void creat_AVL(AVL_Node<T>* &r); // 建立平衡树的算法 };

创建AVL树算法： template<class T> void AVLtree<T>::creat_AVL(AVL_Node<T>* &r) // 创建一棵AVL树{ AVL_Node<T> *s; T x; r=NULL; cin>>x;while(x!=in_end) // in_end代表输入终止的符号{ s=new AVL_Node<T>(x); // 为插入结点申请空间AVL_ins(s,r); // 逐个插入结点并令保持平衡cin>>x;}}

（n，A0，K1，A1，K2，A2，…，Kn，An） 9.4.3B－树 B- 树定义 一棵m阶的B- 树，或为空树，或满足下列特性的m叉树： 1、每个结点至多有m棵子树； 2、除根结点和叶结点外其它个结点至少有m/2棵子树； 3、除非根结点为最低层非终端结点否则至少有两子树； 4、所有非终端结点中包含有下列信息： （n，A0，K1，A1，K2，A2，…，Kn，An） 其中，Ki（1 i n）为关键字，且Ki<Ki+1（1 i <n），Ai（0 i n）为指向子树根结点的指针，且指针Ai（0 i<n）所指子树中所有结点的关键字均小于Ki+1，指针An 所指子树中的关键字均大于Kn，n（m/2-1  n  m-1）为关键字的个数；

5、缩有的叶子结点都出现在同一层上，并且不带信息（可以看作是外部结点或查失败的结点,实际上这些结点不存在,指向这些结点的指针为空）

B-树的查找 设查找一个给定值K，首先从根开始，若根结点中有K，则查找成功，否则必是下述三种情况之一： ① ki<K<ki+1，(1 i<n)。继续到 Ai 所指结点中去查找； ② K>kn，则到An所指结点继续查找； ③ K<k1，则转到A0所指结点中去查找。 重复上述过程，直到查找成功或下一个要查找结点的指针Ai（0 i n）为“空”（或指向叶子结点F），则查找失败，关键字为K的记录不在树中。

例如：上面查找图的4阶B-树的53的过程如下： 首先由根指针找到根结点A，因为53>35，所以找到结点C，又因为43<53<78，所以找到结点G，最后在结点G中找到53。 在B-树上进行查找所需时间取决于两个因素： ① 等于给定值的关键字所在结点的层次； ② 结点中关键字的数目。当结点中关键字数目较大时可采用折半查找以提高效率。

深度为L+1的m阶B-树具有的最少结点数 ： B- 树的定义，第一层至少有1个结点，第二层至少有2个结点。由于除根之外的每个非终端结点至少有m/2棵子树，则第三层至少有2*「m/2个结点，依次类推… ，第L+1层至少有2*(m/2)i-1个结点。而L+1层的结点为叶子结点（外部结点），若m 阶B-树中具有N个关

B－树的插入：

B－树的插入：

B－树的插入：

B-树的创建 ：

B-树的删除： 在最下面结点中删除一个关键字

B-树的删除：在非最下层结点中删除一个关键字

B+ 树 B+树和m阶的B-树差异在于：（这儿不再考虑外部结点，而直接称最低层内部结点为叶结点） 　　①　有n棵子树的结点中含有n个关键字； 　　②　所有的叶子结点中包含了全部关键字的信息及指向相应记录的指针，且叶结点本身依关键字的大小自小而大顺序链接。 　　③ 所有的非终端结点可以看成是索引部分，结点中仅含有其子树的最大（或最小）关键字。

小结 本章介绍了顺序表的三种查找方法：顺序查找、二分法查找、分块查找，散列表的查找，以及树表：二叉排序树、AVL树、以及B-树的定义、特点和存储结构。并且讨论了各种查找方法的效率――平均查找长度。