Ch.9 查找 查找和排序是两个重要的运算 §9.1 基本概念 对象：表、文件等。其中每个结点（记录）由多个数据项构成，假设每个结点有1个能唯一标识该结点的key。 定义：给定1个值K，在含有n个结点的表中找出关键字等于K的结点，若找到（查找成功），则返回该结点信息或它在表中的位置；否则（查找失败），返回相关指示信息。 分类： 查找过程中是否修改表？动态查找、静态查找 查找过程是否均在内存中进行？内部查找、外部查找 效率：与存储结构、文件状态（有序、无序）有关 平均查找长度(ASL)，即平均的比较次数，作为衡量查找效率的标准： Pi：查找第i个结点的概率 Ci：查找第i个结点的比较次数 设Pi＝1/n, 1≤i≤n 约定：typedef int KeyType;

§ 9.2 线性表的查找 §9.2.1 顺序查找 对象：用线性表作为表的组织形式。 分类：静态查找、内部查找 方式：顺序查找、二分查找、分块查找 ＃define n 100// §9.2.1 顺序查找 基本思想 从表的一端开始，顺序扫描线性表，依次将扫描到的结点的Key与给定值K进行比较，若当前扫描到结点Key＝K，则查找成功返回；若扫描完整个表后，仍未找到，则查找失败。 适用范围：顺序表、链表 算法：

§9.2.1 顺序查找 typedef struct{ KeyType key; InfoType otherinfo; //应用相关 }NodeType, SeqList[n+1]; //0号单元作为哨兵 int SeqSearch( SeqList R, KeyType K) { //在R[1..n]中查找，成功时返回结点位置，失败时返回0 int n; R[0].key=K; //设置哨兵 for ( i=n; R[i].key != K; i-- ); //从后往前找 return i; //若i为0，则失败 }

§9.2.1 顺序查找 哨兵的作用 for中省略了下标越界i>=1判定,节约了约一半时间 时间分析 优缺点 成功：ASLss=(n+1)/2，key的平均比较次数约为表长的一半 失败：n+1次比较 优缺点 优点：简单，对存储结构、Key之间的关系均无特殊要求 缺点：效率低，当n较大时不宜用

§ 9.2.2 二分（折半）查找 适用范围：顺序表、有序 基本思想（分治法） （1）设R[low..high] 是当前查找区间，首先确定该区间的中点 位置：mid= (low+high)/2 //整除 （2）将待查的K值与R[mid]比较， ① K＝R[mid].key：查找成功，返回位置mid ② K＜R[mid].key：则左子表R[low..mid-1]是新的查找区间 ③ K＞R[mid],key：则右子表R[mid+1..high]是新的查找区间 初始的查找区间是R[1..n]，每次查找比较K和中间点元素，若查找成功则返回；否则当前查找区间缩小一半，直至当前查找区间为空时查找失败。

§ 9.2.2 二分（折半）查找 算法： int BinSearch( SeqList R, KeyType K ) { int mid, low=1, high=n; while ( low < high ) { //当前查找区间R[low..high]非空 mid= (low+high)/2； //整除 if ( R[mid].key==K ）return mid; //成功返回位置mid if ( K＜R[mid].key ) //两个子问题求解其中的一个 high=mid-1; //在左区间中查找 else low=mid+1；//在右区间中查找 } // endwhile return 0; //当前查找区间为空时失败 }

§ 9.2.2 二分（折半）查找 查找过程 判定(比较)树：分析查找过程的二叉树，形态只与结点数相关，与输入实例的取值无关（为什么？）。例如n＝11的形态如下图所示。 1 2 3 4 5 6 7 8 9 10 11 （05,13,19,21,37,56,64,75,80, 88, 92），找21成功，找85失败。 内部结点 R[1..11] 6 外部结点 R[1..5] R[7..11] ＝ ＜ ＞ 9 3 R[10..11] R[1..2] R[4..5] R[7..8] 1 7 10 4 R[11..11] Φ R[2..2] R[8..8] Φ R[5..5] Φ Φ 11 2 8 5 9-10 3-4 6-7 -1 Φ Φ Φ Φ Φ Φ Φ Φ 11- 1-2 2-3 4-5 5-6 7-8 8-9 10-11

§ 9.2.2 二分（折半）查找 时间分析 查找R[6]：比较1次; 查找R[3]、R{9]：比较2次; 查找R[1]、R[4]、R[7]、R[10]：比较3次; 查找R[2]、R[5]、R[8]、R[11]：比较4次 6 R[1..11] 1 9 4 3 7 10 2 R[1..5] R[7..11] R[10..11] R[5..5] Φ R[11..11] -1 4-5 1-2 2-3 3-4 R[1..2] R[2..2] 5 8 R[4..5] 5-6 6-7 7-8 11 R[7..8] R[8..8] 8-9 9-10 11- 10-11 ＝ ＞ ＜

§ 9.2.2 二分（折半）查找 时间分析 总结：查找过程走了一条从判定树的根到被查结点的路径。 成功：终止于一个内部结点，所需的Key比较次数恰为该结点在树中的层数; 失败：终止于一个外部结点，所需的Key比较次数为该路径上内部结点总数。（层数－1） 平均查找长度（ASL）： 设n＝2h-1, 则树高h＝lg(n+1) //不计外部结点的满二叉树 第k层上结点数为2k－1，找该层上每个结点的比较次数为k，在等概率假设下： 最坏时间：查找失败，不超过树高 lg(n+1) 在链表上可做折半查找吗？

§ 9.2.2 分块查找（索引顺序查找） 22 48 86 1 7 13 最大关键字 起始地址 存储结构 关键字状态 将R[1..n]均分成b块，前b－1块中结点数为s＝ n/b ，最后一块中的结 点数可能小于s，引入索引表标记块。 关键字状态 分块有序：块间有序，块内不一定有序; 例子：n＝18，b＝3，s＝6 22 48 86 1 7 13 最大关键字 起始地址 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53

§ 9.2.2 分块查找（索引顺序查找） 查找过程（两步查找） 性能分析 索引表查找：确定块。n较大时用折半查找，n较小时用顺序查找。 块内查找：只能顺序查找。 性能分析 以折半查找确定块： ASL＝ ASLbs＋ASLss＝lg(b＋1) －1＋(s＋1)/2≈lg(n/s＋1)＋s/2 以顺序查找确定块： ASL＝ ASLss＋ASLss＝(b＋1)/2＋(s＋1)/2＝(s2＋2s＋n)/(2s) 当s＝ 时，ASL取极小值 ＋1 块不一定等分

§ 9.3 树上的查找（动态查找） 折半查找效率最高，但它不适应插删操作。本节讨论适用于动态查找，即查找过程中动态维护表结构。 § 9.3.1 二叉查找树（BST） 定义：二叉查找树或是空树，或满足下述BST性质的二叉树： ①若它的左子树非空，则左子树上所有结点的keys均小于根的key ②若它的右子树非空，则右子树上所有结点的keys均大于根的key ③左右子树又都是二叉查找树 Note：性质1或2中，可以将“﹤” 改为“≤”；或“﹥”改为“≥” BST性质 二叉查找树的中序序列是一个递增有序序列

§ 9.3.1 二叉查找树（BST） 5 3 7 2 9 4 举例 存储结构： typedef struct node { KeyType key; InfoType otherinfo; struct node *lchild, *rchild; } BSTNode, *BSTree; 5 3 7 2 9 4

BSTNode *SearchBST( BSTree T, KeyType key ){ 5 3 7 2 9 4 1.查找 基本思想 从根结点开始比较，若当前结点的key与待查的key相等，则查找成功，返回该结点的指针；否则在左子树或右子树中继续查找。若树中没有待查结点，则失败于某个空指针上。 算法 BSTNode *SearchBST( BSTree T, KeyType key ){ //在T上查找key=K的节点，成功时返回该节点，否则返回NULL if ( T==NULL || key==T->key ) return T; //若T为空，查找失败；否则成功 if ( key < T->key ) return SearchBST ( T->lchild, key ); //查找左子树 else return SearchBST ( T->rchild, key ); //查找右子树 }

§ 9.3.1 二叉查找树（BST） 5 3 7 2 9 4 1.查找 时间 若成功，则走了一条从根到待查节点的路径 若失败，则走了一条从根到叶子的路径？（不一定） 上界：O(h) 分析：与树高相关 ①最坏情况：单支树，ASL=(n+1)/2,与顺序查找相同 ②最好情况：ASL≈lgn，形态与折半查找的判定树相似 ③平均情况：假定n个keys所形成的n!种排列是等概率的，则可证明由这n!个序列产生的n!棵BST（其中有的形态相同）的平均高度为O(lgn)，故查找时间仍为O(lgn)

2、BST的插入和生成 插入 算法思想 保证新结点插入后满足BST性质，基本思想如下： 若T为空，则为待插入的Key申请一个新结点，并令其为根； 否则，从根开始向下查找插入位置，直到发现树中已有Key，或找到一个空指针为止； 将新结点作为叶子插入空指针的位置。 查找过程是一个关键字的比较过程，易于写出递归或非递归算法，也可以调用查找操作。 算法实现

2、BST的插入和生成 } //注意：树为空时，无须查找 void InsertBST( BSTree *T, KeyType key ) { //*T是根 BSTNode *f, *p=*T; //p指向根结点 while( p ) { //当树非空时，查找插入位置 if ( p->key==key ) return; //树中已有key，不允许重复插入 f＝p；// f和p为父子关系 p＝( key < p->key ) ? p->lchild; p->rchild; } //注意：树为空时，无须查找 p = (BSTNode *) malloc(sizeof(BSTNode)); p->key=key; p->lchild=p->rchild=NULL; //生成新结点 if ( *T ==NULL ) * T=p; //原树为空,新结点为根 else //原树非空, 新结点作为*f的左或右孩子插入 if ( key < f->key ) f->lchild=p; else f->rchild=p; } //时间为O（h）

2、BST的插入和生成 生成 } 算法： 从空树开始，每输入一个数据就调用一次插入算法。 算法： 从空树开始，每输入一个数据就调用一次插入算法。 BSTree CreateBST( void ) { BSTree T＝NULL; //初始时T为空 KeyType key; scanf( “%d”, &key ); while( key ) { //假设key＝0表示输入结束 InsertBST ( &T, key ) ; //将key插入树T中 scanf( “%d”, &key )；// 读入下一个关键字 } return T；// 返回根指针

2、BST的插入和生成 举例 输入实例 {10， 18， 3， 8， 12， 2， 7， 3} 10 18 3 8 12 2 7

不同的输入实例（数据集不同、或排列不同），生成的树的形态一般不同。对n个结点的同一数据集，可生成n！棵BST。 一般情况 不同的输入实例（数据集不同、或排列不同），生成的树的形态一般不同。对n个结点的同一数据集，可生成n！棵BST。 例外情况 但有时不同的实例可能生成相同的BST，例如：（2，3，7，8，5，4）和（2，3，7，5，8，4）可构造同一棵BST。 排序树名称的由来 因为BST的中序序列有序，所以对任意关键字序列，构造BST的过程，实际上是对其排序。 生成n个结点的BST的平均时间是O(nlgn), 但它约为堆排序的2－3倍，因此它并不适合排序。

3、BST的删除 保证删一结点不能将以该结点为根的子树删去，且仍须满足BST性质。即：删一结点相当于删有序序列中的一个结点。 基本思想 查找待删结点*p，令parent指向其双亲（初值NULL）；若找不到则返回，否则进入下一步。 在删除*p时处理其子树的连接问题，同时保持BST性质不变。 case1:*p是叶子，无须连接子树，只需将*parent中指向*p的指针置空 case2:*p只有1个孩子，只须连接唯一的1棵子树，故可令此孩子取代*p与 其双亲连接（4种状态） parent p child parent p child child parent p parent p child *p只有左孩子 *p只有右孩子

3、BST的删除 基本思想 case3: *p有2个孩子，有2种处理方式： ①找到*p 的中序后继(或前驱)*s，用*p的右(或左)子树取代*p与其双亲*parent连接；而*p的左(或右)子树PL则作为*s的左(或右)子树与*s连接。缺点：树高可能增大。 PL sR p parent s pr PL sR s pr parent

3、BST的删除 基本思想 ②令q=p，找*q的中序后继*p，并令parent指向*p的双亲，将*p的右子树取代*p与其双亲*parent连接。将*p的内容copy到*q中，相当于删去了*q，将删*q的操作转换为删*p的操作。对称地，也可找*q的中序前驱 因为*p最多只有1棵非空的子树，属于case2。实际上case1也是case2的特例。因此，case3采用该方式时，3种情况可以统一处理为case2。 q=p parent p child q=p p child *q的中序后继就是其右孩子

3、BST的删除 算法 void DelBSTNode( BSTree *T, KeyType key) { //*T是根 BSTree *q, *child, *parent=NULL, *p=*T; while ( p ) { //找待删结点 if ( p->key ==key ) break; //已找到 parent=p; //循环不变式是*parent为*p的双亲 p＝( key < p->key ) ? p->lchild; p->rchild; } if ( !p ) return; //找不到被删结点，返回 q=p; //q记住被删结点*p if (q->lchild && q->rchild ) //case3，找*q的中序后继 for(parent=q,p=q->rchild; p->lchild; parent=p, p=p->lchild);

3、BST的删除 //现在3种情况已统一到情况2，被删结点*p最多只有1个非空的孩子 child=(p->lchild)？p->lchild; p->rchild; //case1时child空，否则非空 If ( !parent ) //*p的双亲为空，说明 *p是根，即删根结点 *T=child; //若是情况1，则树为空；否则*child取代*p成为根 else { //*p非根，它的孩子取代它与*p的双亲连接，即删 *p if ( p==parent->lchild ) parent->lchild=child; else parent->rchild=child; if ( p != q ) //情况3，将*p的数据copy到*q中 q->key=p->key; //若有其他数据亦需copy } free( p ); //删除*p } //时间O(h)

4、 平衡二叉树(AVL) BST是一种查找效率比较高的组织形式，但其平均查找长度受树的形态影响较大，形态比较均匀时查找效率很好，形态明显偏向某一方向时其效率就大大降低。因此，希望有更好的二叉排序树，其形态总是均衡的，查找时能得到最好的效率，这就是平衡二叉排序树。 平衡二叉排序树(Balanced Binary Tree或Height-Balanced Tree)是在1962年由Adelson-Velskii和Landis提出的，又称AVL树。

平衡二叉树的定义 平衡二叉树或者是空树，或者是满足下列性质的二叉树。 ⑴：左子树和右子树深度之差的绝对值不大于1； ⑵：左子树和右子树也都是平衡二叉树。 平衡因子(Balance Factor) ：二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。 因此，平衡二叉树上每个结点的平衡因子只可能是-1、0和1，否则，只要有一个结点的平衡因子的绝对值大于1， 该二叉树就不是平衡二叉树。 如果一棵二叉树既是二叉排序树又是平衡二叉树，称为平衡二叉排序树(Balanced Binary Sort Tree) 。

{ KeyType key ; /* 关键字域 */ int Bfactor ; /* 平衡因子域 */ … /* 其它数据域 */ 结点类型定义如下： typedef struct BNode { KeyType key ; /* 关键字域 */ int Bfactor ; /* 平衡因子域 */ … /* 其它数据域 */ struct BNode *Lchild , *Rchild ; }BSTNode ; 16 24 12 4 15 18 平衡二叉树 在平衡二叉排序树上执行查找的过程与二叉排序树上的查找过程完全一样，则在AVL树上执行查找时，和给定的K值比较的次数不超过树的深度。 设深度为h的平衡二叉排序树所具有的最少结点数为Nh，则由平衡二叉排序树的性质知：

N0=0，N1=1，N2=2，… ，Nh= Nh-1+Nh-2+1 该关系和Fibonacci数列相似。根据归纳法可证明，当h≥0时，Nh=Fh+2-1，…而 φh √5 Fh≈ 2 1+√5 其中φ= 则Nh≈ -1 这样，含有n个结点的平衡二叉排序树的最大深度为 h≈ √5 ㏒φ( (n+1))-2 则在平衡二叉排序树上进行查找的平均查找长度和㏒2n是一个数量级的，平均时间复杂度为O(㏒2n)。

平衡化旋转 一般的二叉排序树是不平衡的，若能通过某种方法使其既保持有序性，又具有平衡性，就找到了构造平衡二叉排序树的方法，该方法称为平衡化旋转。 在对AVL树进行插入或删除一个结点后，通常会影响到从根结点到插入(或删除)结点的路径上的某些结点，这些结点的子树可能发生变化。以插入结点为例，影响有以下几种可能性 ◆ 以某些结点为根的子树的深度发生了变化； ◆ 某些结点的平衡因子发生了变化； ◆ 某些结点失去平衡。

1 LL型平衡化旋转 ⑴ 失衡原因 ⑵ 平衡化旋转方法 沿着插入结点上行到根结点就能找到某些结点，这些结点的平衡因子和子树深度都会发生变化，这样的结点称为失衡结点。 1 LL型平衡化旋转 ⑴ 失衡原因 在结点a的左孩子的左子树上进行插入，插入使结点a失去平衡。a插入前的平衡因子是1，插入后的平衡因子是2。设b是a的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1(否则b就是失衡结点)。 ⑵ 平衡化旋转方法 通过顺时针旋转操作实现。

⑶ 插入后各结点的平衡因子分析 ① 旋转前的平衡因子 用b取代a的位置，a成为b的右子树的根结点，b原来的右子树作为a的左子树。 设插入后b的左子树的深度为HbL，则其右子树的深度为HbL-1； a的左子树的深度为HbL+1。 a的平衡因子为2，则a的右子树的深度为： HaR=HbL+1-2=HbL-1。 a b bR aR bL x a b bR aR bL x LL型平衡化旋转示意图

② 旋转后的平衡因子 a的右子树没有变，而左子树是b的右子树，则平衡因子是：HaL- HaR=(HbL-1)-(HbL-1)=0 即a是平衡的，以a为根的子树的深度是HbL。 b的左子树没有变化，右子树是以a为根的子树，则平衡因子是： HbL-HbL=0 即b也是平衡的，以b为根的子树的深度是HbL+1，与插入前a的子树的深度相同，则该子树的上层各结点的平衡因子没有变化，即整棵树旋转后是平衡的。

⑷ 旋转算法 void LL_rotate(BBSTNode *a) { BBSTNode *b ; b=a->Lchild ; a->Lchild=b->Rchild ; b->Rchild=a ; a->Bfactor=b->Bfactor=0 ; a=b ; }

2 LR型平衡化旋转 ⑴ 失衡原因 ⑵ 插入后结点c的平衡因子的变化分析 在结点a的左孩子的右子树上进行插入，插入使结点a失去平衡。a插入前的平衡因子是1，插入后a的平衡因子是2。设b是a的左孩子，c为b的右孩子， b在插入前的平衡因子只能是0，插入后的平衡因子是-1；c在插入前的平衡因子只能是0，否则，c就是失衡结点。 ⑵ 插入后结点c的平衡因子的变化分析 ①插入后c的平衡因子是1：即在c的左子树上插入。设c的左子树的深度为HcL，则右子树的深度为HcL-1；b插入后的平衡因子是-1，则b的左子树的深度为HcL，以b为根的子树的深度是HcL+2。

因插入后a的平衡因子是2 ，则a的右子树的深度是HcL。 ② 插入后c的平衡因子是0：c本身是插入结点。设c的左子树的深度为HcL，则右子树的深度也是HcL；因b插入后的平衡因子是-1，则b的左子树的深度为HcL，以b为根的子树的深度是HcL+2；插入后a的平衡因子是2 ，则a的右子树的深度是HcL。 ③ 插入后c的平衡因子是-1：即在c的右子树上插入。设c的左子树的深度为HcL，则右子树的深度为HcL+1 ，以c为根的子树的深度是HcL+2；因b插入后的平衡因子是-1，则b的左子树的深度为HcL+1，以b为根的子树的深度是HcL+3；则a的右子树的深度是HcL+1。

⑶ 平衡化旋转方法 先以b进行一次逆时针旋转(将以b为根的子树旋转为以c为根)，再以a进行一次顺时针旋转，如图所示。将整棵子树旋转为以c为根，b是c的左子树，a是c的右子树；c的右子树移到a的左子树位置， c的左子树移到b的右子树位置。 a b bL aR cL x cR c a c bL aR cL x cR b LR型平衡化旋转示意图

⑷ 旋转后各结点(a,b,c)平衡因子分析 ① 旋转前 (插入后)c的平衡因子是1： a的左子树深度为HcL-1 ，其右子树没有变化，深度是HcL，则a的平衡因子是-1；b的左子树没有变化，深度为HcL，右子树是c旋转前的左子树，深度为HcL，则b的平衡因子是0； c的左、右子树分别是以b和a为根的子树，则c的平衡因子是0 。 ② 旋转前 (插入后)c的平衡因子是0： 旋转后a，b，c的平衡因子都是0 。 ③ 旋转前 (插入后)c的平衡因子是-1： 旋转后a，b，c的平衡因子分别是0，-1，0 。 综上所述，即整棵树旋转后是平衡的。

⑸ 旋转算法 void LR_rotate(BBSTNode *a) { BBSTNode *b,*c ; b=a->Lchild ; c=b->Rchild ; /* 初始化 */ a->Lchild=c->Rchild ; b->Rchild=c->Lchild ; c->Lchild=b ; c->Rchild=a ; if (c->Bfactor==1) { a->Bfactor=-1 ;b->Bfactor=0 ; } else if (c->Bfactor==0) a->Bfactor=b->Bfactor=0 ; else { a->Bfactor=0 ;b->Bfactor=1 ; } }

3 RL型平衡化旋转 ⑴ 失衡原因 ⑵ 插入后结点c的平衡因子的变化分析 在结点a的右孩子的左子树上进行插入，插入使结点a失去平衡，与LR型正好对称。对于结点a，插入前的平衡因子是-1，插入后a的平衡因子是-2。设b是a的右孩子，c为b的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1；同样，c在插入前的平衡因子只能是0，否则，c就是失衡结点。 ⑵ 插入后结点c的平衡因子的变化分析 ① 插入后c的平衡因子是1：在c的左子树上插入。设c的左子树的深度为HcL，则右子树的深度为HcL-1。

因b插入后的平衡因子是1，则其右子树的深度为HcL，以b为根的子树的深度是HcL+2；因插入后a的平衡因子是-2 ，则a的左子树的深度是HcL。 ② 插入后c的平衡因子是0：c本身是插入结点。设c的左子树的深度为HcL，则右子树的深度也是HcL；因b插入后的平衡因子是1，则b的右子树的深度为HcL，以b为根的子树的深度是HcL+2；因插入后a的平衡因子是-2 ，则a的左子树的深度是HcL。 ③ 插入后c的平衡因子是-1：在c的右子树上插入。设c的左子树的深度为HcL，则右子树的深度为HcL+1 ，以c为根的子树的深度是HcL+2；因b插入后的平衡因子是1，则b的右子树的深度为HcL+1，以b为根的子树的深度是HcL+3；则a的右子树的深度是HcL+1。

⑶ 平衡化旋转方法 先以b进行一次顺时针旋转，再以a进行一次逆时针旋转，如图所示。即将整棵子树(以a为根)旋转为以c为根，a是c的左子树，b是c的右子树；c的右子树移到b的左子树位置，c的左子树移到a的右子树位置。 a b bR aL cL x cR c b c bR aL cL x cR a RL型平衡化旋转示意图

⑷ 旋转后各结点(a,b,c)的平衡因子分析 ① 旋转前 (插入后)c的平衡因子是1： a的左子树没有变化，深度是HcL，右子树是c旋转前的左子树，深度为HcL，则a的平衡因子是0；b的右子树没有变化，深度为HcL，左子树是c旋转前的右子树，深度为HcL-1 ，则b的平衡因子是-1； c的左、右子树分别是以a 和b为根的子树，则c的平衡因子是0 。 ② 旋转前 (插入后)c的平衡因子是0： 旋转后a，b，c的平衡因子都是0 。 ③ 旋转前 (插入后)c的平衡因子是-1： 旋转后a，b，c的平衡因子分别是1，0，0 。 综上所述，即整棵树旋转后是平衡的。

⑸ 旋转算法 Void LR_rotate(BBSTNode *a) { BBSTNode *b,*c ; b=a->Rchild ; c=b->Lchild ; /* 初始化 */ a->Rchild=c->Lchild ; b->Lchild=c->Rchild ; c->Lchild=a ; c->Rchild=b ; if (c->Bfactor==1) { a->Bfactor=0 ; b->Bfactor=-1 ; } else if (c->Bfactor==0) a->Bfactor=b->Bfactor=0 ; else { a->Bfactor=1 ;b->Bfactor=0 ; } }

4 RR型平衡化旋转 ⑴ 失衡原因 ⑵ 平衡化旋转方法 在结点a的右孩子的右子树上进行插入，插入使结点a失去平衡。要进行一次逆时针旋转，和LL型平衡化旋转正好对称。 ⑵ 平衡化旋转方法 设b是a的右孩子，通过逆时针旋转实现，如图所示。用b取代a的位置，a作为b的左子树的根结点，b原来的左子树作为a的右子树。 a b bL aL bR x b a bL aL bR x RR型平衡化旋转示意图

⑶ 旋转算法 BBSTNode *RR_rotate(BBSTNode *a) { BBSTNode *b ; b=a->Rchild ; a->Rchild=b->Lchild ; b->Lchild=a ; a->Bfactor=b->Bfactor=0 ; a=b ; } 对于上述四种平衡化旋转，其正确性容易由“遍历所得中序序列不变”来证明。并且，无论是哪种情况，平衡化旋转处理完成后，形成的新子树仍然是平衡二叉排序树，且其深度和插入前以a为根结点的平衡二叉排序树的深度相同。所以，在平衡二叉排序树上因插入结点而失衡，仅需对失衡子树做平衡化旋转处理。

平衡二叉排序树的插入 平衡二叉排序树的插入操作实际上是在二叉排序插入的基础上完成以下工作： ⑴：判别插入结点后的二叉排序树是否产生不平衡? ⑵：找出失去平衡的最小子树； ⑶：判断旋转类型，然后做相应调整。 失衡的最小子树的根结点a在插入前的平衡因子不为0，且是离插入结点最近的平衡因子不为0的结点的。

1 算法思想(插入结点的步骤) 2 算法实现 ①：按照二叉排序树的定义，将结点s插入； ②：在查找结点s的插入位置的过程中，记录离结点s最近且平衡因子不为0的结点a，若该结点不存在，则结点a指向根结点； ③： 修改结点a到结点s路径上所有结点的； ④：判断是否产生不平衡，若不平衡，则确定旋转类型并做相应调整。 2 算法实现

void Insert_BBST(BBSTNode *T, BBSTNode *S) { BBSTNode *f,*a,*b,*p,*q; if (T==NULL) { T=S ; T->Bfactor=0 ; return ; } a=p=T ; /* a指向离s最近且平衡因子不为0的结点 */ f=q=NULL ; /* f指向a的父结点,q指向p父结点 */ while (p!=NULL) { if (EQ(S->key, p->key) ) return ; /* 结点已存在 */ if (p->Bfactor!=0) { a=p ; f=q ; } q=p ; if (LT(S->key, p->key) ) p=p->Lchild ; else p=p->Rchild ; /* 在右子树中搜索 */ } /* 找插入位置 */

if (LT(S->key,q->key)) q->Lchild=S ;/* s为左孩子 */ else q->Rchild=S ; /* s插入为q的右孩子 */ p=a ; while (p!=S) { if (LT(S->key, p->key) ) { p->Bfactor++ ; p=p->Lchild ; } else { p->Bfactor-- ; p=p->Rchild ; } } /* 插入到左子树,平衡因子加1,插入到左子树,减1 */ if (a->Bfactor>-2&& a->Bfactor<2) return ; /* 未失去平衡,不做调整 */ if (a->Bfactor==2) { b=a->Lchild ;

if (b->Bfactor==1) p=LL_rotate(a) ; else p=LR_rotate(a) ; } else { b=a->Rchild ; if (b->Bfactor==1) p=RL_rotate(a) ; else p=RR_rotate(a) ; } /* 修改双亲结点指针 */ if (f==NULL) T=p ; /* p为根结点 */ else if (f->Lchild==a) f->Lchild=p ; else f->Lchild=p ;

例： 设要构造的平衡二叉树中各结点的值分别是(3, 14, 25, 81, 44)，平衡二叉树的构造过程如下。 (a) 插入不超过两个结点 (b) 插入新结点失衡,RR平衡旋转 3 14 25 81 44 3 14 44 81 25 3 14 25 81 (c) 插入新结点未失衡 (d) 插入结点失衡,RL平衡旋转 平衡二叉树的构造过程