数据结构--第八章 查找

1、第八章第八章 查查 找找8.1 查找的基本概念查找的基本概念列表列表：由同一类型的数据元素（或记录）构成的集由同一类型的数据元素（或记录）构成的集合，可利用任意数据结构实现。合，可利用任意数据结构实现。 关键字关键字：数据元素的某个数据项的值，用它可以标数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。识列表中的一个或一组数据元素。主关键字主关键字：如果一个关键字可以：如果一个关键字可以唯一标识唯一标识列表中的列表中的一个数据元素，则称其一个数据元素，则称其为主关键字为主关键字，否则为次关键否则为次关键字字。当数据元素仅有一个数据项时，数据元素的值。当数据元素仅有一个数据项时，

2、数据元素的值就是关键字。就是关键字。查找查找：根据给定的关键字值，在特定的列表中确定根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。数据元素在列表中的位置。 在查找算法中要用到在查找算法中要用到三类参量三类参量，即：，即：查找对象查找对象K（找什么）（找什么）查找范围查找范围L（在哪找）（在哪找）查找的结果查找的结果（K在在L中的位置）中的位置）其中其中、 为输入参量，在函数中不可缺少为输入参量，在函数中不可缺少。为输出参量，可用函数返回值表示。为输出参量，可用函数返回值表示。平均查找长度平均

3、查找长度：为确定数据元素在列表中的位置，为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。查找算法在查找成功时的平均查找长度。 对于长度为对于长度为n的列表，查找成功时的平均查找长度为：的列表，查找成功时的平均查找长度为：ASL=P1C1+ P2C2+ PnCn = i=1nPiCi其中其中Pi为查找列表中第为查找列表中第i个数据元素的概率，个数据元素的概率，Ci为找为找到列表中第到列表中第i个数据元素时，已经进行过的关键字比个数据元素时，已经进行过的关键字比较次数。较次数。 查找的基本方法

4、查找的基本方法：比较式查找法比较式查找法计算式查找法计算式查找法HASH（哈希）查找法（哈希）查找法基于线性表的查找法基于线性表的查找法基于树的查找法基于树的查找法8.2 基于线性表的查找法基于线性表的查找法具有具有顺序查找法顺序查找法、折半查找法折半查找法和和分块查找法分块查找法三种三种8.2.1 顺序查找法顺序查找法顺序查找法的特点是：用顺序查找法的特点是：用所给关键字与线性表中所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。各元素的关键字逐个比较，直到成功或失败。 存储结构：存储结构：顺序结构顺序结构链式结构链式结构顺序结构有关数据类型的定义：顺序结构有关数据类型的定义：#d

5、efine LIST_SIZE 20#define LIST_SIZE 20typedef structtypedef struct KeyType KeyType key; key; OtherType other_data OtherType other_data; ; RecordType RecordType; ;typedef structtypedef struct RecordTypeRecordType rLIST_SIZE+1; / rLIST_SIZE+1; /* * r0 r0为工作单元为工作单元 * */ / int int length; length; Record

6、List RecordList; ; 设置监视哨的顺序查找算法设置监视哨的顺序查找算法int SeqSearch（RecordList l, KeyType k）/*在顺序表在顺序表l中顺序查找其关键字等于中顺序查找其关键字等于k的元素，若找到，则的元素，若找到，则函数值为该元素在表中的位置，否则为函数值为该元素在表中的位置，否则为0*/ l.r0.key=k; i=l.length; while (l.ri.key.key!=!=k) i-; return（i）; 其中其中l.r0为监视哨，可以起到防止越界的作用。为监视哨，可以起到防止越界的作用。不设置监视哨的顺序查找算法不设置监视哨的顺序

7、查找算法int SeqSearch（RecordList l, KeyType k）/*不用监视哨法，在顺序表中查找关键字等于不用监视哨法，在顺序表中查找关键字等于k的元素的元素*/ l.r0.key=k; i=l.length; while (i=1&l.ri.key!=.key!=k) i-; if (i=1) return（i）else return (0); 循环条件循环条件i=1判断查找是否越界。判断查找是否越界。用平均查找长度分析顺序查找算法的性能。用平均查找长度分析顺序查找算法的性能。 假设假设列表长度为列表长度为n，那么查找第，那么查找第i个数据元素时需个数据元素时需进

8、行进行n-i+1次比较，即次比较，即Ci=n-i+1。又假设查找每个数据。又假设查找每个数据元素的概率相等，即元素的概率相等，即Pi=1/n，则顺序查找算法的平均，则顺序查找算法的平均查找长度为：查找长度为： ASL=i=1nPiCin1i=1nCin1i=1n(n-i+1)=21(n+1)8.2.2 折半查找法折半查找法（二分法查找法）（二分法查找法）条件条件：要求：要求待查找的列表必须是待查找的列表必须是按关键字大小有序按关键字大小有序排列的顺序表排列的顺序表。 基本过程基本过程：将表中间位置记录的关键字与查找关键将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用

9、中字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。表不存在为止，此时查找不成功。 例如用折半查找法查找例如用折半查找法查找10、50的具体过程，的具体过程，其中其中mid=(low+high)/2，当，当highlow

10、时，表示不存在这样时，表示不存在这样的子表空间，查找失败。的子表空间，查找失败。 605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=1mid=6high=11605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=1 mid=3high=5用折半查找法查找用折半查找法查找12的过程为：的过程为：605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=1mid=1high=2605846352825221815126 1 2 3 4 5 6 7 8 9 10 11l

11、ow=2mid=2high=2用折半查找法查找用折半查找法查找50的过程：的过程：605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=1mid=6high=11605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=7 mid=9high=11605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=10mid=10high=11605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=10high=9折半查找的算法如下：折半查

12、找的算法如下：int BinSrch （SqList l, KeyType k）/*在有序表在有序表l中折半查找其关键字等于中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置的元素，若找到，则函数值为该元素在表中的位置*/ low=1 ; high=l.length; /*置区间初值置区间初值*/ while ( low=high) mid=(low+high) / 2; if (k=l.rmid. key) return（mid）;/*找到待查元素找到待查元素*/ else if (k key=key; s-lchild=NULL; s-rchild=NULL; s- ke

13、y=key; s-lchild=NULL; s-rchild=NULL; * *bstbst=s;=s; else if (key ( else if (key key)-key) InsertBST(&( InsertBST(&(* *bst)-lchildbst)-lchild), key);/), key);/* *将将s s插入左子树插入左子树* */ / else if (key ( else if (key (* *bstbst)-key) )-key) InsertBST(&(InsertBST(&(* *bst)-rchildbst)-rchil

14、d), key); /), key); /* *将将s s插入右子树插入右子树* */ / 二叉排序树的生成方法：二叉排序树的生成方法： 假若给定一个元素序列，可以利用上述算法创建一假若给定一个元素序列，可以利用上述算法创建一棵二叉排序树。棵二叉排序树。将二叉排序树初始化将二叉排序树初始化为一棵空树，然后逐个读入元为一棵空树，然后逐个读入元素，每读入一个元素，就建立一个新的结点插入到素，每读入一个元素，就建立一个新的结点插入到当前已生成的二叉排序树中，即调用上述二叉排序当前已生成的二叉排序树中，即调用上述二叉排序树的插入算法将新结点插入。树的插入算法将新结点插入。 生成二叉排序树的算法：生成二

15、叉排序树的算法：void CreateBST(BSTree void CreateBST(BSTree * *bstbst) )/ /* *从键盘输入元素的值，创建相应的二叉排序树从键盘输入元素的值，创建相应的二叉排序树* */ / KeyTypeKeyType key; key; * *bstbst=NULL;=NULL; scanf(%d scanf(%d, &key);, &key); while (key!=ENDKEY) / while (key!=ENDKEY) /* *ENDKEYENDKEY为自定义常数为自定义常数* */ / InsertBST(bst Ins

16、ertBST(bst, key);, key); scanf(%d scanf(%d, &key);, &key); 设关键字的输入顺序为：设关键字的输入顺序为：45，24，53，12，28，90，按上述算法生成的二叉排序树的过程：按上述算法生成的二叉排序树的过程：空树空树45插入插入454524插入插入24452453插入插入5345245312插入插入124524531228插入插入28452453122890插入插入90对同样一些元素值，如果输入的顺序不同，则所建对同样一些元素值，如果输入的顺序不同，则所建的二叉树形态也不同。如果将上述例子中的关键字的二叉树形态也不同。如

17、果将上述例子中的关键字顺序变为：顺序变为：24，53,90,12,28,45,则生成的二叉排序树则生成的二叉排序树为：为：2412285390452. 二叉排序树的删除二叉排序树的删除删除操作：删除操作：首先确定被删除的结点首先确定被删除的结点是否在二叉排序树中是否在二叉排序树中。若不若不在在 ，则不做任何操作，则不做任何操作；否则，假设要删除的结点为否则，假设要删除的结点为p，结点，结点p的双亲结点为的双亲结点为f，并假设结点，并假设结点p是结点是结点f的的左孩子（右孩子的情况类似）左孩子（右孩子的情况类似）。 从二叉排序树中删除一个结点，必须保证删除从二叉排序树中删除一个结点，必须保证删除

18、后所得的二叉树仍然满足二叉排序树的性质不变。后所得的二叉树仍然满足二叉排序树的性质不变。下面分三种情况讨论：下面分三种情况讨论：（2）若若p结点只有左子树，或只有右子树，则可将结点只有左子树，或只有右子树，则可将p的左子树或右子树直接改为其双亲结点的左子树或右子树直接改为其双亲结点f的左子树。的左子树。即：即：f-lchild=p-lchild（或（或f-lchild=p-rchild）；）；free(p)； （1） 若若p为叶结点，则可直接将其删除：为叶结点，则可直接将其删除： f-lchild=NULL；free(p)； （3）若若p既有左子树，又有右子树，既有左子树，又有右子树， 如下图

19、如下图(a)，则，则处理的方法有两种：处理的方法有两种：FPPLPRfp(a) P的左右子树均不空的左右子树均不空方法一：方法一：首先找到首先找到p结点在中序序列中的直接前驱结点在中序序列中的直接前驱s结点，如图结点，如图 (b) 所示，然后将所示，然后将p的左子树改为的左子树改为f的左子的左子树，而将树，而将p的右子树改为的右子树改为s的右子树：的右子树：f-lchild=p- - lchild；s-rchild= p-rchild；free(p)；结果如图；结果如图 (c) 所示。所示。 FPCPRfpcSQQLSLqsCL(b) S为为P的直接前驱的直接前驱CLFCSSLPRfc(c)

20、将将P的左子树改为的左子树改为F的左子树，的左子树，将将P的右子树改为的右子树改为S的右子树。的右子树。方法二：方法二：首先找到首先找到p结点在中序序列中的直接前驱结点在中序序列中的直接前驱s结点，如图结点，如图 (b) 所示，然后用所示，然后用s结点的值，替代结点的值，替代p结点结点的值，再将的值，再将s结点删除，原结点删除，原s结点的左子树改为结点的左子树改为s的双的双亲结点亲结点q的右子树：的右子树：p-data-data=s-data-data；q-rchild= s-lchild；free(s)；结果如图；结果如图 (d) 所示。所示。 FPCPRfpcSQQLSLqsCL(b) S

21、为为P的直接前驱的直接前驱(d) 将原将原P结点的值改为结点的值改为S结点的值，删除结点的值，删除原原S结点并将原结点并将原S的左子树改为的左子树改为Q的右子树的右子树FSCPRfpcQQLSLqCL在二叉排序树中删除结点的算法在二叉排序树中删除结点的算法BSTNode * * DelBST(BSTree DelBST(BSTree t, t, KeyType k) ) /*在二叉排序树在二叉排序树t中删去关键字为中删去关键字为k的节点的节点*/ BSTNode * *p, p, * *f,f,* *s ,s ,* *q;q; p=t;f p=t;f=NULL;=NULL; while(p w

22、hile(p)/)/* *查找关键字为查找关键字为k k的待删结点的待删结点p p* */ / if(p if(p-key=k ) break;/-key=k ) break;/* *找到，则跳出查找循环找到，则跳出查找循环* */ / f=p;/ f=p;/* *f f指向指向p p结点的双亲结点结点的双亲结点* */ / if if（p-keykp-keyk） p=p-lchildp=p-lchild; ; else p=p-rchild else p=p-rchild; ; if(pif(p=NULL) return t;/=NULL) return t;/* *若找不到，返回原来的二叉

23、排序树若找不到，返回原来的二叉排序树* */ /if(p-lchildif(p-lchild=NULL)/=NULL)/* *p p无左子树无左子树* */ /if(f=NULL) t=p-rchildif(f=NULL) t=p-rchild;/;/* *p p是原二叉排序树的根是原二叉排序树的根* */ / else if(f-lchild else if(f-lchild=p)/=p)/* *p p是是f f的左孩子的左孩子* */ / f-lchild=p-rchild f-lchild=p-rchild ； / /* *将将p p的右子树链到的右子树链到f f的左链上的左链上* */

24、 / else / else /* *p p是是f f的右孩子的右孩子* */ / f-rchild=p-rchild f-rchild=p-rchild ;/ ;/* *将将p p的右子树链到的右子树链到f f的右链上的右链上* */ / free(p free(p);/);/* *释放被删除的节点释放被删除的节点p p* */ / else /else /* *p p有左子树有左子树* */ / q=p;s=p-lchild q=p;s=p-lchild; ; while(s-rchild while(s-rchild)/)/* *在在p p的左子树中查找最右下结点的左子树中查找最右下结点

25、* */ / q=s;s=s-rchild q=s;s=s-rchild; if(q=p) q-lchild=s-lchild if(q=p) q-lchild=s-lchild ;/ ;/* *将将s s的左子树链到的左子树链到q q上上* */ / else q-rchild=s-lchild else q-rchild=s-lchild; ; p-key=s-key;/ p-key=s-key;/* *将将s s的值赋给的值赋给p p* */ / free(s free(s);); return t;return t; / /* *DelBSTDelBST* */ / 3. 二叉排序树的

26、查找二叉排序树的查找根据二叉排序树的特点，首先将待查关键字根据二叉排序树的特点，首先将待查关键字k与根结与根结点关键字点关键字t进行比较，如果：进行比较，如果：（1）k= t：则返回根结点地址；：则返回根结点地址； （2）kt：则进一步查右子树。：则进一步查右子树。 显然，这是一个递归过程。可用如下递归算法实现：显然，这是一个递归过程。可用如下递归算法实现： 二叉排序树查找的递归算法为：二叉排序树查找的递归算法为：BSTree SearchBST(BSTree bst, KeyTypeBSTree SearchBST(BSTree bst, KeyType key) key)/ /* *在根指

27、针在根指针bstbst所指二叉排序树中，递归查找某关键字等于所指二叉排序树中，递归查找某关键字等于keykey的元素，的元素，若查找成功，返回指向该元素结点指针，否则返回空指针。若查找成功，返回指向该元素结点指针，否则返回空指针。* */ / if (!bst if (!bst) return NULL;) return NULL;else if (bst- key=key) return bstelse if (bst- key=key) return bst;/;/* *查找成功查找成功* */ /elseelse if (key bst if (key key)- key) return

28、 SearchBST(bst-lchild return SearchBST(bst-lchild, key);/, key);/* *在左子树继续查找在左子树继续查找* */ / else else return SearchBST(bst-rchildreturn SearchBST(bst-rchild, key);/, key);/* *在右子树继续查找在右子树继续查找* */ / 二叉排序树查找的非递归算法：二叉排序树查找的非递归算法：BSTree SearchBST(BSTree bst, KeyTypeBSTree SearchBST(BSTree bst, KeyType ke

29、y) key)/ /* *在根指针在根指针bstbst所指二叉排序树所指二叉排序树bstbst上，查找关键字等于上，查找关键字等于keykey的结点，若查的结点，若查找成功，返回指向该元素结点指针，否则返回空指针。找成功，返回指向该元素结点指针，否则返回空指针。* */ / BSTree q; q=bst BSTree q; q=bst; ; while(q while(q) ) if (q-key=k) return q;/ if (q-key=k) return q;/* *查找成功查找成功* */ /if (key data.key) q=q-lchildif (key data.key

30、) q=q-lchild;/;/* *在左子树中查找在左子树中查找* */ /else q=q-rchildelse q=q-rchild; /; /* *在右子树中查找在右子树中查找* */ / return NULL;/return NULL;/* *查找失败查找失败* */ / /*SearchBST*/ 4. 二叉排序树的查找性能二叉排序树的查找性能 对于含有同样关键字序列的一组结点，结点插对于含有同样关键字序列的一组结点，结点插入的先后次序不同，所构成的二叉排序树的形态和入的先后次序不同，所构成的二叉排序树的形态和深度不同。深度不同。而而二叉排序树的平均查找长度二叉排序树的平均查找长

31、度ASL与二叉与二叉排序树的形态有关排序树的形态有关，二叉排序树的各分支越均衡，二叉排序树的各分支越均衡，树的深度浅，其平均查找长度树的深度浅，其平均查找长度ASL越小。越小。 例如：例如：452412375393(a) 输入关键字序列为输入关键字序列为45,24,53,12,37,93时的二叉排序树时的二叉排序树12122437455393(b)输入关键字序列为输入关键字序列为12,24,37,45,53,93时的二叉排序树时的二叉排序树 假设假设每个元素的查找概率相等，则它们的平均每个元素的查找概率相等，则它们的平均查找长度分别是：查找长度分别是： ASL=(1+2+2+3+3+3)/6=

32、14/6ASL=(1+2+3+4+5+6)/6=21/6由此可见，由此可见，在二叉排序树上进行查找时的平均查找在二叉排序树上进行查找时的平均查找长度和二叉排序树的形态有关。长度和二叉排序树的形态有关。 若考虑把若考虑把n个结点，按各种可能的次序插入到二叉个结点，按各种可能的次序插入到二叉排序树中，则有排序树中，则有n！棵二叉排序树（其中有的形态！棵二叉排序树（其中有的形态相同），可以证明，对这些二叉排序树进行平均，相同），可以证明，对这些二叉排序树进行平均，得到的平均查找长度仍然是得到的平均查找长度仍然是O(logO(log2 2n)n)。 8.3.2 平衡二叉排序树平衡二叉排序树平衡二叉排序

33、树又称为平衡二叉排序树又称为AV树。树。一棵平衡二叉排序树一棵平衡二叉排序树或者是空树，或者是具有下列性质的二叉排序树：或者是空树，或者是具有下列性质的二叉排序树： （1）左子树与右子树高度之差的绝对值小于等于左子树与右子树高度之差的绝对值小于等于1； （2）左子树和右子树也是平衡二叉排序树。左子树和右子树也是平衡二叉排序树。 平衡因子平衡因子：结点的左子树深度与右子树深度之差。：结点的左子树深度与右子树深度之差。由性质可知，一棵平衡二叉树的所有结点的平衡因由性质可知，一棵平衡二叉树的所有结点的平衡因子只能是子只能是-1、0或或1。40256030507080-1-1-1-1000402550

34、305860-1-21000200(a)一棵平衡二叉排序树一棵平衡二叉排序树(b)一棵失去平衡的二叉排序树一棵失去平衡的二叉排序树当我们在一个平衡二叉排序树上当我们在一个平衡二叉排序树上插入插入一个结点时，一个结点时，有可能导致失衡有可能导致失衡，即出现绝对值大于，即出现绝对值大于1的平衡因子，的平衡因子，如如2、-2。 下面通过实例来说明失衡情况以及相应的调整方法下面通过实例来说明失衡情况以及相应的调整方法1.在在(a)图图A的左子树的左子树上插入的左子树的左子树上插入15后，导致失后，导致失衡，如衡，如(b)图。为恢复平衡并保证二叉排序树的特性，图。为恢复平衡并保证二叉排序树的特性，可将可

35、将A改为改为B的右子，的右子，B原来的右子改为原来的右子改为A的左子，的左子，图图,即以即以B为轴，对为轴，对A做一次顺时针旋转。做一次顺时针旋转。402560203010000AB(a)平衡二叉排序树平衡二叉排序树402560203020101AB150(b)插入插入15后失去平衡后失去平衡25204015300010BA6000调整后的二叉排序树调整后的二叉排序树2.在在(a)图图A的右子树的右子树B的右子树上插入的右子树上插入70后，导致失后，导致失衡，如衡，如(b)图。为恢复平衡并保证二叉排序树的特性，图。为恢复平衡并保证二叉排序树的特性，可将可将A改为改为B的左子，的左子，B原来的左

36、子改为原来的左子改为A的右子，的右子，图图(c),即以即以B为轴，对为轴，对A做一次逆时针旋转。做一次逆时针旋转。(a)平衡二叉排序树平衡二叉排序树2520403060-10000AB2520403060-2-10-10AB700(b)插入插入70后失去平衡后失去平衡40256030700-1000AB200调整后的二叉排序树调整后的二叉排序树3.在在(a)图图A的左子树的左子树B的右子树上插入的右子树上插入45后，导致失后，导致失衡，如衡，如(b)图。为恢复平衡并保证二叉排序树的特性，图。为恢复平衡并保证二叉排序树的特性，可首先将可首先将B改为改为C的左子，而的左子，而C原来的左子改为原来的

37、左子改为B的的右子；然后将右子；然后将A改为改为C的右子，的右子，C原来的右子改为原来的右子改为A的左子，即对的左子，即对B做了一次逆时针旋转，对做了一次逆时针旋转，对A做一次顺做一次顺时针旋转。时针旋转。18010904020306050708595A0000C000000B(a)一棵平衡二叉排序树一棵平衡二叉排序树8010904020306050708595A0001C01000-1B4502(b)插入插入45后失去平衡后失去平衡060108040203050457090C-100100000BA859500调整后的二叉排序树调整后的二叉排序树4.在在(a)图图A的右子树的右子树B的左子树

38、上插入的左子树上插入55后，导致失后，导致失衡，如衡，如(b)图。为恢复平衡并保证二叉排序树的特性，图。为恢复平衡并保证二叉排序树的特性，可首先将可首先将B改为改为C的右子，而的右子，而C原来的右子改为原来的右子改为B的的左子；然后将左子；然后将A改为改为C的左子，的左子，C原来的左子改为原来的左子改为A的右子，即对的右子，即对B做了一次顺时针旋转，对做了一次顺时针旋转，对A做一次逆做一次逆时针旋转。时针旋转。(a)一棵平衡二叉排序树一棵平衡二叉排序树-140A0508060709085950C00000B20103000000-240 A1508060709085950C00-11B2010

39、300040 A508060709085950C00B201030005500(b)插入插入55后失去平衡后失去平衡040 C20608090859500B402007050551030-100000A调整后的二叉排序树调整后的二叉排序树综上所述，失衡类型及相应的调整方法可归纳为以综上所述，失衡类型及相应的调整方法可归纳为以下四种：下四种：1）LL型（以型（以B轴，对轴，对A做了一次顺时针旋转）做了一次顺时针旋转）ABBLBRSAR21(a)插入新结点插入新结点S后失去平衡后失去平衡BABLBRSAR00(b)调整后恢复平衡调整后恢复平衡在一般二叉排序树的结点中增加一

40、个存放平衡因子的域在一般二叉排序树的结点中增加一个存放平衡因子的域bf。LL型失衡的特点是：型失衡的特点是：A-bf=2，B-bf=1。相应调整操作可用如下语句完成：相应调整操作可用如下语句完成： B=A-Lchild； A-Lchild=b-rchild； B-rchild=A； A-bf-bf=0； B-bf=0-bf=0； 1）LL型型最后，将调整后二叉树的根结点最后，将调整后二叉树的根结点B“接到接到”原原A处。处。令令A原来的父指针为原来的父指针为FA，如果，如果FA非空，则用非空，则用B代代替替A做做FA的左子或右子；否则原来的左子或右子；否则原来A就是根结点，就是根结点，此时应令

41、根指针此时应令根指针t指向指向B： if (FA=NULL) t=B; else if (A=FA-Lchild) FA-Lchild=B; else FA-r-rchild=B； 2）LR型（对型（对B做了一次逆时针旋转，对做了一次逆时针旋转，对A做了一做了一次顺时针旋转）次顺时针旋转）ABCRCLSAR2-1(a)插入新结点插入新结点S后失去平衡后失去平衡BLC 1CBCRCLSAR00(b)调整后恢复平衡调整后恢复平衡BLA- 1LR型失衡的特点是：型失衡的特点是：A-bf=2，B-bf=-1。 相应调整操作可用如下语句完成：相应调整操作可用如下语句完成： B=A-lchild； C=B

42、-Rchild； B-rchild=C-lchild； A-lchild=C-rchild； C-lchildC-lchild=B=B； C-rchildC-rchild=A=A； 然后针对上述三种不同情况，修改然后针对上述三种不同情况，修改A、B、C的平衡因子：的平衡因子：if (S-key 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 *

43、/ A-bf=0-bf=0； B-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 else FA-rchild=C=C； 3）RR型（以型（以B为轴，对为轴，对A做了一次逆时针旋转）做

44、了一次逆时针旋转）(a)插入新结点插入新结点S后失去平衡后失去平衡ABBLBRSAL-21-1(b)调整后恢复平衡调整后恢复平衡0BABLBRSAL0RR型失衡的特点是：型失衡的特点是：A-bf=-2，B-bf=-1。 相应调整操作可用如下语句完成：相应调整操作可用如下语句完成： B=A-rchild； A-rchild=B-lchild； B-lchild=A； A-bf-bf=0； B-bf=0-bf=0； 最后，将调整后二叉树的根结点最后，将调整后二叉树的根结点B“接到接到”原原A处。处。令令A原来的父指针为原来的父指针为FA，如果，如果FA非空，则用非空，则用B代替代替A做做FA的左子

45、或右子；否则，原来的左子或右子；否则，原来A就是根结点，就是根结点，此时应令根指针此时应令根指针t指向指向B： if (FA=NULL) t=B; else if (A=FA-Lchild) FA-Lchild=B; else FA-r-rchild=B； 4）RL型（型（对对B做了一次顺时针旋转，对做了一次顺时针旋转，对A做了一次做了一次逆时针旋转逆时针旋转 ）ABCALCLCRBRS-21-1(a)插入新结点插入新结点S后失去平衡后失去平衡BA AC CBRCLCRALS001(b)调整过后恢复平衡调整过后恢复平衡RL型失衡的特点是：型失衡的特点是：A-bf=-2，B-bf=1。 相应调整

46、操作可用如下语句完成：相应调整操作可用如下语句完成： B=A-rchild； C=B-lchild； B-lchild=C-rchild； A-rchild=C-lchild； C-lchildC-lchild=A=A； C-rchildC-rchild=B=B； 然后针对上述三种不同情况，修改然后针对上述三种不同情况，修改A、B、C的平衡因子：的平衡因子：if (S-key key) /* 在在CL下插入下插入S */ A-bf=0； B-bf=-1 ； C-bf=0；if (S-key C-key) /* 在在CR下插入下插入S */ A-bf=1； B-bf=0 ； C-bf=0；if

47、(S-key =C-key) /* C本身就是插入的新结点本身就是插入的新结点S */ A-bf=0-bf=0； B-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 else FA-r

48、child=C=C； 综上所述，在一个平衡二叉排序树上插入一个新结综上所述，在一个平衡二叉排序树上插入一个新结点点S时，主要包括以下三步：时，主要包括以下三步：（1）查找应插位置，同时记录离插入位置最近的）查找应插位置，同时记录离插入位置最近的可能失衡结点可能失衡结点A（A的平衡因子不等于的平衡因子不等于0）。）。（2）插入新结点）插入新结点S，并修改从，并修改从A到到S路径上各结点路径上各结点的平衡因子。的平衡因子。（3）根据）根据A、B的平衡因子，判断是否失衡以及失的平衡因子，判断是否失衡以及失衡类型，并做相应处理。衡类型，并做相应处理。 平衡二叉排序树的插入算法平衡二叉排序树的插入算法其

49、中其中AVLTree为平衡二叉排序树类型，为平衡二叉排序树类型，AVLTNode为平衡为平衡二叉排序树结点类型二叉排序树结点类型 void ins_AVLtree（AVLTree *avlt , KeyType k）/*在平衡二叉树中插入元素在平衡二叉树中插入元素k，使之成为一棵新的二叉排序树，使之成为一棵新的二叉排序树*/ s=(AVLTree)malloc(sizeof(AVLTNode s=(AVLTree)malloc(sizeof(AVLTNode);); s-key=k; s-lchild=s-rchild=NULL; S-bf=0; if (*avlt=NULL) *avlt=S

50、; else /* 首先查找首先查找S的插入位置的插入位置FP，同时记录距，同时记录距S的插入位置最近且的插入位置最近且 平衡因子不等于平衡因子不等于0（等于（等于-1或或1）的结点）的结点a，a为可能的失衡结点为可能的失衡结点*/ A=*avlt； fa=NULL; p=*avlt； fp=NULL while (p!=NULL) if (p-bf!=0) a=p; fa=fp; fp=p; if (K key) p=p-lchild; else p=p-rchild; /* 插入插入S*/ if (K key) FP-lchild=S;else FP-rchild=S; /* 确定结点确定

51、结点B，并修改，并修改A的平衡因子的平衡因子 */if (K key) B=A-lchild；A-bf=A-bf+1 else B=A-rchild；A-bf=A-bf-1 /* 修改修改B到到S路径上各结点的平衡因子（原值均为路径上各结点的平衡因子（原值均为0）*/p=B；while (p!=S) if (K key) p-bf=1；p=p-lchild else p-bf=-1；p=p-rchild /* 判断失衡类型并做相应处理判断失衡类型并做相应处理 */ if (A-bf=2 & B-bf=1) /* LL型型 */ B=A-Lchild； A-Lchild=b-rchild

52、； B-rchild=A； A-bf=0； b-bf=0；if FA=NULL *avlt=b else if A=FA-Lchild FA-Lchild=B else FA-rchild=B； else if (A-bf=2 & B-bf=-1) /* LR型型 */ B=a-lchild； C=B-Rchild； B-rchild=C-lchild； A-lchild=C-rchild； C-lchild=B； C-rchild=A；if (S-key key) A-bf=-1； B-bf=0 ； C-bf=0；else if (S-key C-key) A-bf=0； B-bf=

53、1 ； C-bf=0；else A-bf=0； B-bf=0 ； if (FA=NULL) *avlt=C; else if (A=FA-lchild) FA-lchild=C;else FA-rchild=C； else if (A-bf=-2 & B-bf=1) /* RL型型 */ B=a-rchild； C=B-lchild； B-lchild=C-rchild； A-rchild=C-lchild； C-lchild=A； C-rchild=B；if (S-key key) A-bf=0； B-bf=-1 ； C-bf=0；else if (S-key C-key) A-bf

54、=1； B-bf=0 ； C-bf=0；else A-bf=0； B-bf=0 ； if (FA=NULL) *avlt=C; else if (A=FA-lchild) FA-lchild=C; else FA-rchild=C； else if (A-bf=-2 & B-bf=-1) /* RR型型 */ B=A-rchild； A-rchild=B-lchild； B-lchild=A； A-bf=0； B-bf=0； if (FA=NULL) *avlt=B; else if (A=FA-Lchild) FA-Lchild=B; else FA-rchild=B； 8.3.3

55、B树树1. m路查找树（路查找树（ m叉排序树）叉排序树）定义：定义：一棵一棵m路查找树，或者是一棵空树，或者是路查找树，或者是一棵空树，或者是满足如下性质的树：满足如下性质的树： 1)1)结点最多有结点最多有m棵子树，棵子树，m1个关键字，其结构如个关键字，其结构如下：下： nP0K1P1K2P2KnPn其中其中n为关键字个数，为关键字个数，Pi为指向子树根结点的为指向子树根结点的指针，指针，0in，Ki为关键字，为关键字，1in 2）Ki37，所以，所以找到结点找到结点C，又因为，又因为405885,所以找到结点所以找到结点G，最，最后在结点后在结点G中找到中找到58。如果要查找。如果要查

56、找32，首先由根指，首先由根指针针mbt找到根结点找到根结点A，因为，因为3225, 所以找到结点所以找到结点E，因为，因为303235, 所所以最后找到失败结点以最后找到失败结点 f ，表示，表示32不存在，查找失败。不存在，查找失败。 在具体实现时，采用如下结点结构：在具体实现时，采用如下结点结构：parentnK1K2KnP0P1PnParent为指向双亲结点的指针。为指向双亲结点的指针。在在B树中查找关键字为树中查找关键字为k的元素算法如下：的元素算法如下：#define m typedef int Boolean; typedef struct Mbtnode struct Mbtn

57、ode *parent ; int keynum ; KeyType keym+1 ; struct Mbtnode *ptrm+1 ; Mbtnode, *Mbtree; Boolean srch_mbtree (Mbtree mbt, KeyType k, Mbtree *np, int *pos)/*在根为在根为mbt的的B树中查找关键字树中查找关键字k，如果查找成功，则将所在结点地址放，如果查找成功，则将所在结点地址放入入np，将结点内位置序号放入，将结点内位置序号放入pos，并返回，并返回true；否则，将；否则，将k应被插入的结应被插入的结点地址放入点地址放入np，将结点内应插位置

58、序号放入，将结点内应插位置序号放入pos，并返回，并返回false*/p = mbt; fp = NULL; found = false; i = 0;while (p != NULL & !found) i = search (p, k);if (i0 & p-keyi = k) found = true;else fp = p; p = p-ptri; if found *np = p; *pos = i ; return true ;else *np = fp; *pos = i; return false ;寻找小于等于关键字寻找小于等于关键字key的最大关键字序号算法

59、的最大关键字序号算法int search (Mbtree mbt, KeyType key )n = mbt-keynum ;i = 1 ;while (i keyi keyi+1处，插入后如果处，插入后如果q-keynumm-1，则进行分裂处理，则进行分裂处理*/if (*mbt=NULL) * *mbt =(Mbtree)malloc(sizeof(Mbtnodembt =(Mbtree)malloc(sizeof(Mbtnode););(*mbt)-keynum=1;(*mbt)-parent=NULL; (*mbt)-key1=k;(*mbt)-ptr0=NULL ; (*mbt)-p

60、tr1=NULL ; else x=k; /* 将将x插到插到q-keyi+1 处处 */ ap=NULL;/* 将将ap插到插到q-ptri+1 处处 */ Finished=NULL; while (q!=NULL & !finished) /* q=NULL 表示已经分裂到根表示已经分裂到根 */ Insert(q, i, x, ap); if (q-keynumkeys; ap=q1; q=q-parent; if (q!=NULL) i=search(q,x); /* search( ) 的定义参见的定义参见B树查找一节树查找一节 */ if (!finished) /* 表示根结点要分裂，并产生新根表示根结点要分裂，并产生新根 */ new_root=(Mbtree)malloc(siz