第9章 查找 静态查找表 二叉排序树 平衡二叉树（AVL树） 小结 B树 哈希表

静态查找表 查找(Search)的概念 查找：就是在数据集合中寻找满足某种条 件的数据对象。 查找表：是由同一类型的数据元素(或记录) 组成的数据集合。 查找的结果通常有两种可能： 查找成功，即找到满足条件的数据对象。 查找不成功，或查找失败。作为结果， 报告一些信息，如失败标志、失败位置等。

静态查找表（p214） 关键字：数据元素中某个数据项的值，用以 标识一个数据元素。 主关键字：可唯一地标识一个数据元素的关 键字。 次关键字：用以识别若干记录的关键字。 使用基于主关键字的查找，查找结果应是 唯一的。 静态查找表（p214） 动态查找表

9.1 静态查找表 基本操作： Create(&ST,n); //构造含有n个元素的静态查找表ST Destroy(&ST); //销毁表 Search(ST,key); //查找关键字为key的数据元素 Traverse(ST,visit()); //遍历查找表

衡量一个查找算法的时间效率的标准是：在查找过程中关键字的平均比较次数或平均读写磁盘次数(只适合于外部查找)，这个标准也称为平均查找长度ASL(Average Search Length)，通常它是查找结构中对象总数 n 或文件结构中物理块总数 n 的函数。 另外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题。 在静态查找表中，数据对象存放于数组中，利用数组元素的下标作为数据对象的存放地址。查找算法根据给定值x，在数组中进行查找。直到找到x在数组中的存放位置或可确定在数组中找不到x为止。

9.1.1顺序表的查找 (Sequential Search) 所谓顺序查找，又称线性查找，主要用于在线性结构中进 行查找。 存储结构： typedef struct{ ElemType *elem; int length; } SSTable; 查找过程：从表中最后一个元素开始，顺序用各元素的关键字与给定值x进行比较，若找到与其值相等的元素，则查找成功，给出该元素在表中的位置；否则，若直到第一个记录仍未找到关键字与x相等的对象，则查找失败。

算法9.1 （p217） Search_Seq(SSTable ST, KeyType key){ //顺序查找的算法，0号元素为监视哨 int i； ST.elem[0].key=key; for (i=ST.length; !EQ(ST.elem[i].key,key);--i); return i; }

顺序查找的平均查找长度 设查找第 i 个元素的概率为 pi，查找到第 i 个元素所需比较次数为 ci，则查找成功的平均查找长度: 在顺序查找情形，ci = n-i +1, i = 1, , n，因此 在等概率情形，pi = 1/n, i = 0, 1, , n-1。

9.1.2 有序表的查找 折半查找：先求位于查找区间正中的对象的下标mid，用其关键字与给定值x比较: Element[mid].getKey( ) = x，查找成功； Element[mid].getKey( ) > x，把查找区间缩小到表的前半部分，再继续进行对分查找； Element[mid].getKey( ) < x，把查找区间缩小到表的后半部分，再继续进行对分查找。 每比较一次，查找区间缩小一半。如果查找区间已缩小到一个对象，仍未找到想要查找的对象，则查找失败。

9.1.2 有序表的查找 折半查找： （1）mid= (low+high)/2」 （2）比较 ST.elem[mid].key = = key? 如果 ST.elem[mid].key = = key，则查找成功， 返回mid值 如果 ST.elem[mid].key > key，则置high=mid-1 如果 ST.elem[mid].key < key，则置low=mid+1 (3) 重复计算mid 以及比较ST.elem[mid].key与 key， 当low>high时，表明查找不成功，查找结束。

查找成功的例子 查找失败的例子

算法9.2(p220) int Search_Bin(SSTable ST,KeyType key) //折半查找 { int low,high,mid; 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;

从有序表构造出的二叉查找树(判定树) 查找成功的情形 查找不成功的情形 若设 n = 2h-1，则描述对分查找的二叉查找树是高度为 h 的满二叉树。2h = n+1, h = log2(n+1)。 第1层结点有1个，查找第1层结点要比较1次；第2层结点有2个，查找第2层结点要比较2次；…，

9.1.2 索引顺序表的查找——分块查找 typedef struct { int key;} Eletype; 1）分块有序（升序或降序） ——第I块中的最大（小）值小（大）于第i+1块中的最（大）小值 2）查找 （1）先查索引表——折半查找 （2）再查顺序表——顺序查找 块间有序，块内无序 typedef struct { int key;} Eletype; typedef struct { Elemtype *elem; int length; } SSTable; # define BLOCK_NUM 3

Typedef struct { int Maxkey; int next; } BLKNode,IT[BLOCK_Num]; int Search_Bin(SSTable ST,int key) //折半查找 { int i,p,low,high,mid; printf(“Create index table,Input Maxkey& nex\n”) for(i=1;i<=BLOCK_NUM;i++) scanf(“%d,%d”,&IT[i].Maxkey,&IT[i].next) if(key>IT[BLOCK_NUM].Maxkey) return(0); low = 1; high=BLOCK_NUM; while (low < =high) { mid = (low+high)/2; if (IT[mid].Maxkey>=key)) high=mid-1; else low=mid+1; }

i=IT[low].next; ST.ele[0].key = key; If(low!=BLOCK_NUM) p=IT[low+1].next; else p=ST.length+1; while(ST.elem[i%p].key != key ) i++ ; return( i%p ) ; } 性能分析： ASL（bls）=Lb+Lw=(b+1/)2 +(s+1)/2 =(b+s+2)/2 =(n/s+s)/2+1 b —— 分块的个数 b=n/2 s —— 每块中的记录个数 n —— 记录的总个数 Lb —— 确定所在的块 Lw —— 块内查找

第 i (1  i  h) 层结点有 2i -1个，查找第 i 层结点要比较 i次，…。假定每个结点的查找概率相等，即pi = 1/n，则查找成功的平均查找长度为 可以用归纳法证明 这样

9.2 动态查找表 表结构本身是在查找过程中动态生成的。 基本操作： InitDSTable(&DT); //构造一个空的动态查找表DT DestroyDSTable(&DT); //销毁表 SearchDSTable(DT,key); //查找关键字为key的数据元素 InsertDSTable(&DT,e); DeleteDSTable(&DT,key); TraverseDSTable(DT,visit()); //遍历查找表

9.2.1二叉排序树 ( Binary Sort Tree ) 定义 二叉排序树（二叉查找树） 或者是一棵空树，或者是具有下列性质的二叉树：  每个结点都有一个作为查找依据的关键字(key)，所有结点的关键字互不相同。  左子树(若非空)上所有结点的关键字都小于根结点的关键字。  右子树(若非空)上所有结点的关键字都大于根结点的关键字。  左子树和右子树也是二叉排序树。

几个二叉排序树的例子 如果对一棵二叉排序树进行中序遍历，可以按从小到大的顺序，将各结点关键字排列起来。

二叉排序树上的构建 ——如何构造二叉排序树 二叉排序树上的构建 ——如何构造二叉排序树 1) 构造过程： 从空树出发，依次插入R1～ Rn各数据值： （1）如果二叉排序树是空树，则插入结点就是 二叉排序树的根结点； （2）如果二叉排序树是非空的，则插入值与 跟结点比较，若小于根结点的值，就插 入到左子树中去；否则插入到右子树中。 示例： { 45，24，53，12，22，90 }

2) 二叉排序树的数据类型描述 3) 二叉排序树上插入结点的算法 typedef struct { int key; } ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; } BiTNode, * BiTree; 3) 二叉排序树上插入结点的算法 （1）在二叉排序树上插入一个结点的算法； （2）依次输入一组数据元素，并插入到二叉排 序树中的算法

（1）将指针S所指的结点插入到根结点指针为T的 二叉排序树中的算法 void Insert_BST( BiTree &T, BiTree S ) { BiTree p, q; if(!T) T=S; else { p=T; while ( p ) { q = p; if (S->data.key < p->data.key) p = p->lchild; else p = p->rchild; } if (S->data.key < q->dat.key) q->lchild = S; else q->rchild = S; return;

（2）输入一组数据元素的序列，构造二叉排序树 的算法 （2）输入一组数据元素的序列，构造二叉排序树 的算法 void Creat BST( BiTree &T ) { int x; BiTree S; T=NULL; while ( scanf ( “%d”,&x), x!=0 ) { S = (BiTNode *) malloc(sizeof(BitNode)); S->data.key = x; S->lchild = NULL; S->rchild = NULL; Insert_BST( T,S ); } return;

4) 二叉排序树上的查找（动态查找） int Searh_BST( BiTree T, int key ) { BiTree p, q, S, p = T; while ( p ) if ( p->data.key == key ) return(1); else if ( p->data.key > key) { q=p; p=p->lchild; } else {q=p; p=p->rchild; } S = (BiTNode *) malloc(sizeof(BitNode)); S->data.key = key; S->lchild=S->rchild=NULL; if (!T) T=S; else if ( q->data.key > key ) q->lchild=S; else q->rchild=S; return(0); } 说明：（1）正常情况下，返回0是未找到，但实际上已经插入； （2）也可以用return返回一个自己定义的标志值。

5) 二叉排序树的删除 （1）确定被删除结点： A. 有没有被删除的结点； B. 若有，则确定被删除的结点是根结点还 是一般结点 要求：删除一个结点后，仍然保持二叉排序树 的有序性 删除结点的算法： （1）确定被删除结点： A. 有没有被删除的结点； B. 若有，则确定被删除的结点是根结点还 是一般结点 （2）如果被删除结点是根结点，则调用删除根结点的 算法； （3）如果被删除结点是一般结点，则调用删除一般结 点的算法。

（2）如果根结点没有左子树，则以右子树的根 结点作为新的根结点； （3）如果根结点没有右子树，则以左子树的根 结点作为新的根结点 删除二叉排序树的根结点的算法 （1） 根结点有左右子树的情况下，选择根结点的 左子树中的最大结点为新的根结点；/或者是 右子树中的最小结点为新的根结点； ** 最大结点——中序遍历 （2）如果根结点没有左子树，则以右子树的根 结点作为新的根结点； （3）如果根结点没有右子树，则以左子树的根 结点作为新的根结点

（3）若被删除结点P没有右子树，则把结点P的左子 树的全部挂接在P的双亲上，且位置是P在其双 亲中原来的位置 删除二叉排序树中一般结点的算法 （1） 若被删除结点P有左、右子树，则按照中序遍历找其 左子树中的最大结点，以此最大结点的值代替P结点 的值，然后删除此最大结点（如同删除根结点） （2）若被删除结点P没有左子树，则把结点P的右子树的 全部挂接在P的双亲上，且位置是P在其双亲中原来 的位置 （3）若被删除结点P没有右子树，则把结点P的左子 树的全部挂接在P的双亲上，且位置是P在其双 亲中原来的位置 删除二叉排序树中叶子结点的算法 只需将其双亲结点指向它的指针清零，再释放它即可

int Delete_BST( BiTree &T,int key) 删除二叉排序树中结点的算法 ——寻找被删除的结点 int Delete_BST( BiTree &T,int key) { BiTree p, f ; p=T; f=NULL; while(p) { if (p->data.key == key) { delNode ( T, p, f ) ; return(1) ;} else if (p->data.key > key) { f=p; p=p->lchild; } else { f=p; p=p->rchild; } } return(0)

void delNode ( BiTree &T, BiTree p, BiTree f ) 删除二叉排序树中结点的算法 ——删除找到的结点 void delNode ( BiTree &T, BiTree p, BiTree f ) { BiTree s, q ; int tag ; tag=0; if (!p->lchild) s=p->rchild; else if (!p->rchild) s=p->lchild; else{ q=p; s=p->lchild; while(s->rchild) { q=s; s=s->rchild; } p->data=s->data; if (q==p) q->lchild=s->lchild; else q->rchild=s->lchild; free(s); tag=1; } //左右孩子中至少有一个不存在 if (!tag){ if ( !f ) T=s;; else if ( f->lchild==p ) f->lchild=s; else f->rchild=s; free(p); return; }

二叉排序树上的查找 在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。 假设想要在二叉排序树中查找关键字为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键字进行比较： 如果给定值等于根结点的关键字，则查找成功。 如果给定值小于根结点的关键字，则继续递归查找根结点的左子树； 否则。递归查找根结点的右子树。

int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){ //二叉排序树的递归查找算法 if (!T) {p=f; return FALSE;} else if (EQ(key,T->data.key)){p=T;return TRUE;} else if (LT(key,T->data.key)) return SearchBST(T->lchild,key,T,p); else return SearchBST(T->rchild,key,T,p); }

每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。 二叉排序树的查找 插入新结点88 每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。

二叉排序树的插入 为了向二叉排序树中插入一个新元素，必须先检查这个元素是否在树中已经存在。 在插入之前，先使用查找算法在树中检查要插入元素有还是没有。 查找成功: 树中已有这个元素，不再插入。 查找不成功: 树中原来没有关键字等于给定值的结点，把新元素加到查找操作停止的地方。

int InsertBST(BiTree &T,ElemType e){ //二叉排序树插入算法 BiTree s,p; if (!SearchBST(T,e.key,NULL,p)) { s=(BiTree)malloc(sizeof(BiTNode)); s->data=e; s->lchild=s->rchild=NULL; if (!p) T=s; else if (LT(e.key,p->data.key)) p->lchild=s; else p->rchild=s; return TRUE; } else return FALSE;

输入数据，建立二叉排序树的过程 输入数据序列 { 53, 78, 65, 17, 87, 09, 81, 45, 23 }

同样 3 个数据{ 1, 2, 3 }，输入顺序不同，建立起来的二叉排序树的形态也不同。这直接影响到二叉排序树的查找性能。 如果输入序列选得不好，会建立起一棵单支树，使得二叉排序树的高度达到最大，这样必然会降低查找性能。 {2, 1, 3} {1, 2, 3} {1, 3, 2} {2, 3, 1} {3, 1, 2} {3, 2, 1} 1 1 2 3 3 2 3 1 3 1 2 3 2 2 1

二叉排序树的删除 在二叉排序树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会失去。 为保证在执行删除后，树的查找性能不至于降低，还需要防止重新链接后树的高度增加。 删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。 被删结点缺右子树，可以拿它的左子女结点顶替它的位置，再释放它。 被删结点缺左子树，可以拿它的右子女结点顶替它的位置，再释放它。

被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点(关键字最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。或：在它的左子树中寻找中序下的最后一个结点，用它的值替换被删结点，再处理该结点的删除。（书上算法9.8即为第二种办法） 二叉排序树的删除递归算法（算法9.7) int DeleteBST(BiTree &T,KeyType key){ if (!T) return FALSE; else { if (EQ(key,T->data.key)) {return Delete(T);} else if (LT(key,T->data.key)) return DeleteBST(T->lchild,key); else return DeleteBST(T->rchild,key); }

int Delete(BiTree &p){//算法9.8 BiTree q,s; if (!p->rchild){ q=p; p=p->lchild; free(q); } else if (!p->lchild){ q=p; p=q->rchild; free(q); } else{ q=p; s=p->lchild; while (s->rchild){ q=s; s=s->rchild;} p->data=s->data; if (q!=p) q->rchild = s->lchild; else q->lchild = s->lchild; delete s; } return TRUE;}

最优二叉查找树 (棵) 对于有 n 个关键字的集合，其关键字有 n! 种不同的排列，可构成的不同二叉查找树有 如何评价这些二叉查找树，可以用树的查找效率来衡量。 例如，已知关键字集合 { a1, a2, a3 } = { do, if, to }，对应查找概率为 p1=0.5, p2=0.1, p3=0.05, 在各个查找不成功的间隔内查找概率又分别为 q0=0.15, q1=0.1, q2=0.05, q3=0.05。可能的二叉查找树如下所示。

(b) (a) (c) (d)

(e) 在扩充二叉查找树中 ○表示内部结点，包含了关键字集合中的某一个关键字； □表示外部结点，代表造成查找失败的各关键字间隔中的不在关键字集合中的关键字。 在每两个外部结点之间必然存在一个内部结点。

设二叉树的内部结点有 n 个，外部结点有 n+1 个。如果定义每个结点的路径长度为该结点的层次，并用 I 表示所有 n 个内部结点的路径长度之和，用 E 表示 n+1 个外部结点的路径长度之和，可以用归纳法证明，E = I+2n。 一棵扩充二叉查找树的查找成功的平均查找长度ASLsucc可以定义为该树所有内部结点上的权值p[i]与查找该结点时所需的关键字比较次数c[i] (= l[i] + 1)乘积之和：

扩充二叉查找树查找不成功的平均查找长度ASLunsucc为树中所有外部结点上权值q[j]与到达外部结点所需关键字比较次数c'[j](= l'[j])乘积之和： 扩充二叉查找树总的平均查找长度为： ASL = ASLsucc + ASLunsucc 所有内、外部结点上的权值关系为

(1) 相等查找概率的情形 若设树中所有内、外部结点的查找概率都相等： 图(a)： ASL = 15/7 图(d)：ASL = 15/7 p[i] = q[j] = 1/7，1  i  3, 0  j  3 图(a)：ASLsucc = 1/7*3+1/7*2+1/7*1 = 6/7, ASLunsucc = 1/7*3*2+1/7*2+1/7*1 = 9/7。 总平均查找长度 ASL = 6/7 + 9/7 = 15/7。 图(a)： ASL = 15/7 图(d)：ASL = 15/7 图(b)：ASL = 13/7 图(e)：ASL = 15/7 图(c)：ASL = 15/7 图(b)的情形所得的平均查找长度最小。一般把平均查找长度达到最小的扩充二叉查找树称作最优二叉查找树，

因此，最优二叉查找树的查找成功的平均查找长度和查找不成功的平均查找长度分别为: 在相等查找概率的情形下，因为所有内部结点、外部结点的查找概率都相等，把它们的权值都视为 1。同时，第 k 层有 2k 个结点，k = 0, 1, 。则有 n 个内部结点的扩充二叉查找树的内部路径长度 I 至少等于序列 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, … 的前n项的和。 因此，最优二叉查找树的查找成功的平均查找长度和查找不成功的平均查找长度分别为:

(2) 不相等查找概率的情形 设树中所有内、外部结点的查找概率互不相等，p[1] = 0.5，p[2] = 0.1，p[3] = 0.05 q[0] = 0.15，q[1] = 0.1，q[2] = 0.05，q[3] = 0.05 图(a)：ASLsucc = 0.5*3 + 0.1*2 + 0.05*1 = 1.75， ASLunsucc = 0.15*3 + 0.1*3 + 0.05*2 + 0.05*1= 0.9。ASL = ASLsucc + ASLunsucc = 2.65。 图(a)：ASL = 2.65 图(d)：ASL = 2.15 图(b)：ASL = 1.9 图(e)：ASL = 1.6 图(c)：ASL = 0.85 由此可知，图(c)的情形下树的平均查找长度达到最小，因此，图(c)的情形是最优二叉查找树。

不相等查找概率情形下的最优二叉查找树可能不同于完全二叉树的形态。 考虑在不相等查找概率情形下如何构造最优二叉查找树。 假设关键字集合放在一个有序的顺序表中 { key[1], key[2], key[3],…key[n] } 设最优二叉查找树为T[0][n]，其平均查找长度为： l [i]是内部结点 a[i] 所在的层次号，l [j] 是外部结点 j 所在的层次号。C[0][n] 是树的代价。 为计算方便，将 p[i] 与 q[j] 化为整数。

构造最优二叉查找树 要构造最优二叉查找树，必须先构造它的左子树和右子树，它们也是最优二叉查找树。 对于任一棵子树T[i][j]，它由 { key[i+1], key[i+2],…, key[j] } 组成，其内部结点的权值为 { p[i+1], p[i+2],…, p[j] } 外部结点的权值为 { q[i], q[i+1], q[i+2],…, q[j] } 使用数组W[i][j]来存放它的累计权值和： W[i][j] = q[i] + p[i+1] + q[i+1] + p[i+2] + + q[i+2]+…+ p[j] + q[j]. 0  i  j  n

计算W[i][j]可以用递推公式: W[i][i] = q[i] //不是二叉树, 只有一个外部结点 W[i][i+1] = q[i] + p[i+1] + q[i+1] = W[i][i] + p[i+1] + q[i+1] //有一个内部结点及两个外部结点的二叉树 W[i][i+2] = W[i][i+1] + p[i+2] + q[i+2] //加一个内部结点和一个外部结点的二叉树 一般地， W[i][j] = W[i][j-1] + p[j] + q[j] //再加一个内部结点和一个外部结点

对于一棵包括关键字 { key[i+1], …, key[k-1], key[k], key[k+1], …, key[j] } 的子树T[i][j]，若设它的根结点为k，i < k  j， 它的代价为： C[i][j] = p[k]+C[i][k-1]+W[i][k-1]+C[k][j]+W[k][j] C[i][k-1]是其包含关键字 { key[i+1], key[i+2],…, key[k-1] } 的左子树T[i][k-1]的代价 C[i][k-1]+W[i][k-1]等于把左子树每个结点的路径长度加1而计算出的代价 C[k][j]是包含关键字 { key[k+1], key[k+2],…, key[j] } 的右子树T[k][j]的代价 C[k][j] + W[k][j]是把右子树每个结点的路径长度加1之后计算出的代价。

因此，公式 C[i][j] = p[k]+C[i][k-1]+W[i][k-1]+C[k][j]+W[k][j] 表明：整个树的代价等于其左子树的代价加上其右子树的代价，再加上根的权值。 因为 W[i][j] = p[k] + W[i][k-1] + W[k][j]， 故有 C[i][j] = W[i][j] + C[i][k-1] + C[k][j] 可用 k = i+1, i+2, …, j 分别计算上式，选取使得C[i][j]达到最小的 k。这样可将最优二叉查找树T[i][j]构造出来。 构造最优二叉查找树的方法就是自底向上逐步构造的方法。

构造的步骤 第一步，构造只有一个内部结点的最优查找树：T[0][1]，T[1][2]，…，T[n-1][n]。 在T[i-1][i] (1  i  n) 中只包含关键字 key[i]。其代价分别是 C[i-1][i] = W[i-1][i]。另外设立一 个数组 R[0..n][0..n] 存放各最优二叉查找树的根。R[0][1] = 1, R[1][2] = 2, … , R[n-1][n] = n。 第二步, 构造有两个内部结点的最优二叉查找树：T[0][2], T[1][3], …, T[n-2][n]。在T[i-2][i] 中包含两个关键字 { key[i-1], key[i] }。其代价取分别以 key[i-1], key[i] 做根时计算出的 C[i-2][i] 中的小者。

第三步，第四步，…，构造有 3 个内部结点，有 4 个内部结点，… 的最优二叉查找树。 最后构造出包含有 n 个内部结点的最优二叉查找树。对于这样的最优二叉查找树，若设根为 k，则根 k 的值存于 R[0][n] 中，其代价存于 C[0][n] 中，左子树的根存于 R[0][k-1] 中，右子树的根存于 R[k][n] 中。

例：给出关键字集合和内、外部结点的权值序列 关键字集合 key1 key2 key3 实 例 do if to 对应 内部结点 p1=50 p2=10 p3=5 权值 外部结点 q0=15 q1=10 q2=5 q3=5 第一步

第二步 C 115 165 50 60 W 90 90 35 35 R 1 2 2 3 左子树 T[0,0] T[0,1] T[1,1] T[1,2] 右子树 T[1,2] T[2,2] T[2,3] T[3,3]

第三步 C 150 190 215 W 100 100 100 R 1 2 3 左子树 T[0,0] T[0,1] T[0,2] 右子树 T[1,3] T[2,3] T[3,3]

0 1 2 3 0 1 2 3 0 15 75 90 100 1 10 25 35 2 5 15 3 5 0 0 75 115 150 1 0 25 50 2 0 15 3 0 W[i][j] C[i][j] 0 1 2 3 3个关键字 { do, if, to } 的 最优二叉查找树 0 0 1 1 1 1 0 2 2 2 0 3 3 0 p1=50, p2=10, p3=5 q0=15, q1=10, q2= 5, q3= 5 R[i][j]

AVL树 高度平衡的二叉查找树 AVL树的定义 高度不平衡的二叉排序树 高度平衡的二叉查找树

结点的平衡因子balance (balance factor) 根据AVL树的定义，任一结点的平衡因子只能取 -1，0和 1。 如果一个结点的平衡因子的绝对值大于1，则这棵二叉查找树就失去了平衡，不再是AVL树。 如果一棵二叉查找树是高度平衡的，它就成为 AVL树。如果它有 n 个结点，其高度可保持在O(log2n)，平均查找长度也可保持在O(log2n)。

AVL树的类型定义 typedef struct BSTNode { ElemType data; struct BSTNode *lchild, *rchild; int bf; } BSTNode,*BSTree; 基本操作： void R_Rotate(BSTree &p); void L_Rotate(BSTree &p); Status InsertAVL(BSTree &T,ElemType e,Boolean &taller); void LeftBalance(BSTree &T); void RightBalance(BSTree &T);

平衡化旋转 如果在一棵平衡的二叉查找树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。 平衡化旋转有两类： 单旋转 (左旋和右旋) 双旋转 (左平衡和右平衡) 每插入一个新结点时，AVL树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子(左、右子树的高度差)。 如果在某一结点发现高度不平衡，停止回溯。

从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。 如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状相关。 如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。 右单旋转 左单旋转 左右双旋转 右左双旋转

左单旋转 (RotateLeft ) A A C B C B C A E h D h D D E E h + 1 B h h h h + 1 +1 A A C +2 +1 B C B C A E h D h D D E E h + 1 B h h h h + 1 h h (a) (b) (c) 如果在子树E中插入一个新结点，该子树高度增1导致结点A的平衡因子变成+2，出现不平衡。 沿插入路径检查三个结点A、C和E。它们处于一条方向为“\”的直线上，需要做左单旋转。 以结点C为旋转轴，让结点A反时针旋转。

void L_Rotate(BSTree &p){ BSTree rc; rc=p->rchild; p->rchild=rc->lchild; rc->lchild=p; p=rc; }

右单旋转 (RotateRight ) A A B C C B B D A D E h D E h E C h + 1 h h h + 1 -1 A A -2 B C C B B -1 D A D E h D E h E C h + 1 h h h + 1 h h h (a) (b) (c) 在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到 -2，造成了不平衡。 为使树恢复平衡，从A沿插入路径连续取3个结点A、B和D，它们处于一条方向为“/”的直线上，需要做右单旋转。 以结点B为旋转轴，将结点A顺时针旋转。

void R_Rotate(BSTree &p){ BSTree lc; lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; }

先左后右双旋转 (RotationLeftRight) 在子树F或G中插入新结点，该子树的高度增1。结点A的平衡因子变为 -2，发生了不平衡。 从结点A起沿插入路径选取3个结点A、B和E，它们位于一条形如“”的折线上，因此需要进行先左后右的双旋转。 首先以结点E为旋转轴，将结点B反时针旋转，以E代替原来B的位置，做左单旋转。 再以结点E为旋转轴，将结点A顺时针旋转，做右单旋转。使之平衡化。

-1 -2 左单 旋转 +1 插入 -1 右单 旋转 +1

void LeftBalance(BSTree &T){//左平衡化的算法 BSTree lc,rd; lc=T->lchild; switch(lc->bf){ case LH: T->bf = lc->bf = EH; R_Rotate(T); break; case RH: rd=lc->rchild; switch(rd->bf){ 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; } rd->bf=EH; L_Rotate(T->lchild); R_Rotate(T); }

先右后左双旋转 (RotationRightLeft) 右左双旋转是左右双旋转的镜像。 在子树F或G中插入新结点，该子树高度增1。结点A的平衡因子变为2，发生了不平衡。 从结点A起沿插入路径选取3个结点A、C和D，它们位于一条形如“”的折线上，需要进行先右后左的双旋转。 首先做右单旋转：以结点D为旋转轴，将结点C顺时针旋转，以D代替原来C的位置。 再做左单旋转：以结点D为旋转轴，将结点A反时针旋转，恢复树的平衡。

+1 +2 -1 +1 右单旋转 插入 左单 旋转 -1

AVL树的插入 在向一棵本来是高度平衡的AVL树中插入一个新结点时，如果树中某个结点的平衡因子的绝对值 |balance| > 1，则出现了不平衡，需要做平衡化处理。 算法从一棵空树开始，通过输入一系列对象的关键字，逐步建立AVL树。在插入新结点时使用了前面所给的算法进行平衡旋转。

例，输入关键字序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，插入和调整过程如下。 -1 -2 1 16 16 16 7 7 左右双旋 1 -1 3 3 3 16 3 16 7 11 2 1 2 7 7 7 -2 1 3 16 右单旋 3 11 3 11 -1 1 11 9 16 9 16 9 26

1 11 11 左单旋 右左双旋 1 2 7 16 7 16 -1 3 9 26 3 9 26 18 1 11 11 -1 7 18 7 18 -1 3 9 16 26 3 9 16 26 14

2 1 11 11 -2 左右双旋 -1 7 18 7 18 -2 3 9 16 26 3 9 15 26 1 14 14 16 15 从空树开始的建树过程

AVL树的删除 如果被删结点x最多只有一个子女，那么问题比较简单。如果被删结点x有两个子女，首先查找 x 在中序次序下的直接前驱 y (同样可以找直接后继)。再把 结点y 的内容传送给结点x，现在问题转移到删除结点 y。 把结点y当作被删结点x。 将结点x从树中删去。因为结点x最多有一个子女，我们可以简单地把x的双亲结点中原来指向x的指针改指到这个子女结点；如果结点x没有子女，x双亲结点的相应指针置为NULL。然后将原来以结点x为根的子树的高度减1，

必须沿 x 通向根的路径反向追踪高度的变化对路 径上各个结点的影响。 用一个布尔变量 shorter 来指明子树的高度是否被缩短。在每个结点上要做的操作取决于 shorter 的值和结点的 balance，有时还要依赖子女的 balance 。 布尔变量 shorter 的值初始化为True。然后对于从 x 的双亲到根的路径上的各个结点 p，在 shorter 保持为 True 时执行下面的操作。如果 shorter 变成False，算法终止。

case 1 : 当前结点 p 的balance为0。如果它的左子树或右子树被缩短，则它的 balance改为 1 或-1，同时 shorter 置为False。 case 2 : 结点 p 的balance不为0，且较高的子树被缩短，则 p 的balance改为0，同时 shorter 置为True。

case 3 : 结点 p 的balance不为0，且较矮的子树又被缩短，则在结点 p 发生不平衡。需要进行平衡化旋转来恢复平衡。令 p 的较高的子树的根为 q (该子树未被缩短), 根据 q 的balance，有如下 3 种平衡化操作。 case 3a : 如果 q 的balance为0，执行一个单旋转来恢复结点 p 的平衡，置shorter为False。 case 3b : 如果 q 的balance与 p 的balance相同，则执行一个单旋转来恢复平衡，结点 p 和 q 的balance均改为0，同时置shorter为True。

case 3c : 如果 p 与 q 的balance相反，则执行一个双旋转来恢复平衡，先围绕 q 转再围绕 p 转。新的根结点的balance置为0，其它结点的balance相应处理，同时置shorter为True。 在case 3a, 3b和3c的情形中，旋转的方向取决于是结点 p 的哪一棵子树被缩短。

AVL树的高度 设在新结点插入前AVL树的高度为 h，结点个数为 n，则插入一个新结点的时间是O(h)。对于AVL树来说，h 多大？ 设 Nh 是高度为 h 的AVL树的最小结点数。根的一棵子树的高度为 h-1，另一棵子树的高度为 h-2，这两棵子树也是高度平衡的。因此有 N-1 = 0 (空树) N0 = 1 (仅有根结点) Nh = Nh-1 + Nh-2 +1 , h > 0 可以证明，对于 h  0，有 Nh = Fh+3 -1 成立。

有 n 个结点的AVL树的高度不超过 在AVL树删除一个结点并做平衡化旋转所需时间为 O(log2n)。 二叉查找树适合于组织在内存中的较小的索引(或目录)。对于存放在外存中的较大的文件系统，用二叉查找树来组织索引不太合适。 在文件检索系统中大量使用的是用B_树或B+树做文件索引。

小结 需要复习的知识点 掌握 简单的查找结构： 查找的概念 查找结构 查找的判定树 平均查找长度 静态查找 顺序查找算法、分析 小结 需要复习的知识点 掌握 简单的查找结构： 查找的概念 查找结构 查找的判定树 平均查找长度 静态查找 顺序查找算法、分析 折半查找算法、分析

二叉查找树 定义 查找、平均查找长度 插入、删除、 AVL树 插入、平衡化旋转 删除、平衡化旋转 高度

查找的概念 查找结构决定查找的效率 查找算法基于查找结构 查找效率用平均查找长度衡量 平均查找长度表明查找算法的整体性能，避开偶然因素 平均查找长度分查找成功与查找不成功两种情况

静态查找结构 顺序查找 — 顺序表、链表 折半查找 — 有序顺序表 动态查找结构 二叉排序树 — 无重复关键字 AVL树 — 平衡二叉排序树

有序顺序表的顺序查找 ( 10, 20, 30, 40, 50, 60 ) 10 < > = 20 < > = 30

有序顺序表的折半查找 ( 10, 20, 30, 40, 50, 60 ) 30 < > = 10 50 < >

二叉查找树 二叉查找树的子树是二叉查找树 右子树上所有关键字大于结点关键字 结点左子树上所有关键字小于结点关键字 35 15 45 10 25 40 50 20 30

n 个结点的二叉查找树的数目 【例】3 个结点的二叉查找树 {123} {132} {213} {231} {312} {321} 1 1 {123} {132} {213} {231} {312} {321} 1 1 2 3 3 2 3 1 3 1 2 3 2 2 1

查找不成功时检测指针停留在某个外结点（失败结点）。 查找成功时检测指针停留在树中某个结点。 查找不成功时检测指针停留在某个外结点（失败结点）。 35 查找45 15 45 10 25 50 20 30 查找22

二叉查找树的高度越小，平均查找长度越小。 n 个结点的二叉查找树的高度最 大为 n-1, 最小为 log2n. A C B A D C D B E E

AVL树 理解：AVL树的子树也是AVL树 掌握：插入新结点后平衡化旋转的方法 掌握：删除结点后平衡化旋转的方法 掌握：结点高度 h 与结点数 n 的关系

（2）如果被删除结点是根结点，则调用删除根结点的 算法； （3）如果被删除结点是一般结点，则调用删除一般结 点的算法。 二叉排序树的删除 要求：删除一个结点后，仍然保持二叉排序树 的有序性 删除结点的算法： （1）确定被删除结点： A. 有没有被删除的结点； B. 若有，则确定被删除的结点是根结点还 是一般结点 （2）如果被删除结点是根结点，则调用删除根结点的 算法； （3）如果被删除结点是一般结点，则调用删除一般结 点的算法。

（2）如果根结点没有左子树，则以右子树的根 结点作为新的根结点； （3）如果根结点没有右子树，则以左子树的根 结点作为新的根结点 删除二叉排序树的根结点的算法 （1） 根结点有左右子树的情况下，选择根结点的 左子树中的最大结点为新的根结点； 最大结点——中序遍历 （2）如果根结点没有左子树，则以右子树的根 结点作为新的根结点； （3）如果根结点没有右子树，则以左子树的根 结点作为新的根结点

（3）若被删除结点P没有右子树，则把结点P的左子 树的全部挂接在P的双亲上，且位置是P在其双 亲中原来的位置 删除二叉排序树的一般结点的算法 （1） 若被删除结点P有左、右子树，则按照中序遍历找其 左子树中的最大结点，以此最大结点的值代替P结点 的值，然后删除此最大结点（如同删除根结点） （2）若被删除结点P没有左子树，则把结点P的右子树的 全部挂接在P的双亲上，且位置是P在其双亲中原来 的位置 （3）若被删除结点P没有右子树，则把结点P的左子 树的全部挂接在P的双亲上，且位置是P在其双 亲中原来的位置