全屏显示专题章节

从前面几个小节的讨论中可以看出,在线性表的3种查找方式中,折半查找法的查找效率最高,但它只适合于顺序结构,不能用链表作存储结构。因此,当表中元素的插入、删除操作比较频繁时,为了保持表的有序性,需要移动表中的很多记录,因此会增加许多额外的时间开销,从而抵消折半查找在效率方面的优势,也就是说,折半查找仅适合于静态的查找表。如果要对动态的查找表进行高效率的查找,则要使用几种特殊的二叉树或树作为表的组织形式,在这里统称为树表,基于这种结构的查找方式称为树型查找。本节中将介绍在树表上进行的各种查找和修改操作方法。

1.二叉排序树的定义

二叉排序树（binary sort tree）又称二叉查找树,它既可能是一棵空树,也可能是具有下列性质的二叉树之一。

（1）若左子树不空,则左子树上所有结点的值均小于根结点的值。

（2）若右子树不空,则右子树上所有结点的值均大于根结点的值。

（3）左、右子树也都是二叉排序树。

图8－4所示即为一棵二叉排序树。从上述的定义可知,对二叉排序树进行中序遍历,便可得到一个按关键字有序的序列12,21,28,33,43,49,55,61,77,98。

二叉排序树的存储结构定义如下。

2.二叉排序树的插入

（1）若二叉树为空,则插入结点为新的根结点。

（2）若二叉树非空且插入结点小于根结点,则在左子树上查找；若插入结点大于根结点,则在右子树上查找,直至某个结点的左、右子树空为止。

（3）若二叉树非空且插入结点小于该结点时,则作为该结点的左孩子,否则作为该结点的右孩子。

2）二叉排序树的构造过程

【例8－1】　若记录的关键字序列为33,50,42,18,39,9,77,44,2,11,24,则构造一棵二叉排序树的过程如图8－5所示。

从图8－5中可以看出,一个无序序列可以通过构造二叉排序树而成为一个有序序列,每次插入新结点都是二叉排序树上新的叶子结点,不必移动其他结点,仅需改动某个结点指针,由空变为非空即可。

3）生成二叉排序树的算法

具体算法如下。

二叉树的生成,是从空的二叉排序树开始的。每插入一个记录数据,就调用一次插入算法,将它插入到当前已经生成的二叉排序树中。

3.二叉排序树的删除操作

若要在二叉排序树中删除一个结点,并且删除之后的二叉排序树仍要保持二叉排序树的特性,这就需要考虑以下三种情况进行。

1）删除的结点是叶子结点

将与该结点相连接的父结点的指针设为NULL。如图8－6所示,要删除结点11,则只需将其父结点9的右指针设为NULL即可。

2）删除的结点只有一棵子树

将被删除结点的子树向上提升,用子树的根结点取代被删除结点。如图8－7所示,要删除结点9,则可以用结点11取代结点9。

3）删除的结点有两棵子树

当删除的结点有两棵子树时,可采用以下两种方法。

（1）中序直接前趋法　将被删除结点的中序遍历的直接前驱结点取代被删除结点。如图8－8所示,要删除结点20,则要将中序直接前驱结点19取代结点20。

（2）中序直接后继法　将被删除结点的中序遍历的直接后继结点取代被删除结点。如图8－9所示,要删除结点20,则要将中序直接后继结点25取代结点20。

二叉排序树上删除结点的算法具体如下。

若被删结点没有左子树,则用其右孩子结点代替它（注意,右孩子结点可以为空）。若被删结点有左子树,则在其左子树中找到中序遍历的最后一个结点r,把被删结点的右子树作为结点r的右子树,并用被删结点的左孩子结点代替被删结点。

注意:如果被删结点是根结点,同样适用上述方法,只不过要对根结点做调整,因为原根结点要被删除,所以把取代根结点的结点作为新的根结点。

4.二叉排序树查找过程

由二叉排序树的定义可得二叉排序树的查找过程如下。

（1）若查找树为空,则查找失败。

（2）若查找树非空,将给定值k与查找树的根结点关键字进行比较。

（3）若相等,则查找成功,结束查找过程,否则,转入如下步骤。

①当给k小于根结点关键字,查找将在以左孩子为根的子树上继续进行,转步骤（1）。

②当给k大于根结点关键字,查找将在以右孩子为根的子树上继续进行,转步骤（1）。

以二叉链表作为二叉排序树的存储结构,具体算法描述如下

二叉排序树的查找算法主要有以下两种。

（1）二叉排序树查找非递归算法。

（2）二叉排序树查找递归算法。

5.二叉排序树的查找分析

在二叉排序树上查找其关键字等于给定值结点的过程,恰是走了一条从根结点到该结点的路径的过程。由于含有n个结点的二叉树是不唯一的,那么如何来进行查找分析呢？

例如,图8－10所示两棵二叉排序树中结点的值都相同,但（a）的深度为3,而（b）的深度为6。其等概率平均查找长度分别为:

二叉排序树的平均查找长度和二叉树的形态有关。

（1）在最好情况下,二叉排序树在生成过程中,树的形态比较均匀,其最终得到的是一颗形态与二分查找的判定树相似的二叉排序树,如图8－10（a）所示。显然,这种情况下平均查找长度与log₂n成正比,时间复杂度为O（log₂n）。

（2）在最坏情况下,二叉排序树是通过一个有序表的n个结点依次插入生成的,此时所得的二叉排序树蜕化为一颗深度为n的单支树,如图8－10（b）所示。它的平均查找长度和单链表的顺序查找相同,也是（n＋1）/2,时间复杂度为O（n）。

对均匀的二叉排序树进行插入或删除结点操作后,应对其进行调整,使其依然保持均匀。同时为避免出现最坏情况下的歪斜树,应对其进行平衡处理,使其成为平衡二叉树。

1.平衡二叉树的概念

平衡二叉树（balanced binary tree）是由阿德尔森－维尔斯（Adelson－Velskii）和兰迪斯（Landis）于1962年首先提出的,所以又称为AVL树。

若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1,则称这样的二叉树为平衡二叉树。将该结点的左子树深度减去右子树深度的值,称为该结点的平衡因子（balance factor）。也就是说,一棵二叉排序树中,所有结点的平衡因子只为0、1、－1时,则该二叉排序树就是一棵平衡二叉树,否则就不是一棵平衡二叉树。也可以这样理解:平衡二叉树或者是一棵空树,或者是具有下列性质的二叉排序树。

（1）它的左子树和右子树高度之差的绝对值不超过1。

（2）它的左子树和右子树都是平衡二叉树。

图8－11中给出了两棵二叉排序树,每个结点旁边所标注数字是以该结点为根的树的左子树与右子树高度之差,这个数字称为结点的平衡因子。由平衡二叉树定义可知,所有结点的平衡因子只能取－1、0与1三个值之一。若二叉排序树中存在这样的结点,其平衡因子的绝对值大于1,这棵树就不是平衡二叉树。图8－11中,（a）不是平衡二叉树,（b）是平衡二叉树。

我们希望二叉排序树都是AVL树,因为其深度和log₂n是同数量级的,则平均查找长度也和log₂n是同数量级的。

2.非平衡二叉树的平衡处理

若一棵二叉排序树是平衡二叉树,则插入或删除某个结点后,可能会变成非平衡二叉树,这时,就可以对该二叉树进行平衡处理,使其变成一棵平衡二叉树。处理的原则应该是:处理与插入点最近的而平衡因子又比1大或比－1小的结点,既要满足平衡二叉树的要求,又要保持二叉排序树的性质。下面分四种情况讨论平衡处理的方法。

1）RR型的处理（单向右型）

如图8－12所示,在A的左孩子结点B上插入一个左孩子结点C,使A的平衡因子由1变成了2,成为不平衡的二叉排序树。这时可对其进行平衡处理:将A顺时针旋转,成为B的右子树,而原来B的右子树则变成A的左子树,待插入结点C作为B的左子树。

注:图中结点旁边的数字表示该结点的平衡因子。

2）LR型的处理（左右型）

如图8－13所示,在A的左孩子结点B上插入一个右孩子结点C,使得A的平衡因子由1变成了2,成为不平衡的二叉排序树。这时可对其进行平衡处理:将C变到B与A之间,使之成为LL型,然后按LL型处理。

3）LL型的处理（单向左型）

如图8－14所示,在A的右孩子结点B上插入一个右孩子结点C,使A的平衡因子由－1变成－2,成为不平衡的二叉排序树。这时可对其进行平衡处理:将A逆时针旋转,成为B的左子树,而原来B的左子树则变成A的右子树,待插入结点C成为B的右子树。

4）RL型的处理（右左型）

如图8－15所示,在A的右孩子结点B上插入一个左孩子结点C,使A的平衡因子由－1变成－2,成为不平衡的二叉排序树。这时可对其进行平衡处理:将C变到A与B之间,使之变为RR型,然后按RR型处理。

【例8－2】　给定一个关键字序列4,5,7,2,1,3,6。试生成一棵平衡二叉树。

【分析】　平衡二叉树实际上也是一棵二叉排序树,故可以按建立二叉排序树的思想建立一棵二叉树,在建立的过程中,若遇到不平衡,则进行相应的平衡处理,最后就可以变成一棵平衡二叉树。具体生成过程见图8－16。

5.平衡二叉树的查找及性能分析

平衡二叉树本身就是一棵二叉排序树,故它的查找与二叉排序树完全相同。但是其查找性能却优于二叉排序树,即不像二叉排序树那样,会出现最坏的时间复杂度O（n）,它的时间复杂度与二叉排序树的最好时间复杂度相同,均为O（log₂n）。

【例8－3】　对例8－2给定的关键字序列4,5,7,2,1,3,6,试用二叉排序树和平衡二叉树两种方法查找,给出查找关键字6的次数及成功的平均查找长度。

【分析】　由于关键字序列的顺序已经确定,故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见图8－16,得到的二叉排序树见图8－17。

从图8－17所示的二叉排序树可知,查找到6需4次,平均查找长度为

ASL＝（1＋2＋2＋3＋3＋3＋4）/7＝18/7≈2.57

从图8－16的平衡二叉树可知,查找到6需2次,平均查找长度为

ASL＝（1＋2＋2＋3＋3＋3＋3）/7＝17/7≈2.43

由以上结果可知,平衡二叉树的查找性能优于二叉排序树。

【例8－4】　给定关键字序列11,78,10,1,3,2,4,21,试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找来实现查找,试画出它们的对应存储形式（顺序查找的顺序表,二分查找的判定树,二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树）,并求出每一种查找的成功平均查找长度。

顺序查找的顺序表（一维数组）如图8－18所示。

由图8－18可以得到顺序查找的成功平均查找长度为

二分查找的判定树（中序序列为从小到大排列的有序序列）如图8－19所示。由图8－19可以得到二分查找的成功平均查找长度为

二叉排序树（关键字顺序已确定,该二叉排序树应该是唯一的）如图8－20（a）所示,平衡二叉树（关键字顺序已确定,该平衡二叉树也应该是唯一的）如图8－20（b）所示。

由图8－20（a）可以得到二叉排序树查找的成功平均查找长度为

由图8－20（b）可以得到平衡二叉树的成功平均查找长度为

一棵m阶的B－树,或者为空树,或者为满足以下特性的m叉树。

（1）所有的非终端结点的结构如下。

其中:①k₁,k₂,…,k_n为n个按从小到大顺序排列的关键字；②p₀,p₁,p₂,…,p_n为（n＋1）个指针,用于指向该结点的（n＋1）棵子树,p₀所指向子树中的所有关键字的值均小于k₁,p_n所指向子树中的所有关键字的值均大于k_n,p_i（1≤i≤n－1）所指向子树中的所有关键字的值均大于k_i且小于k_i＋1；③n（n≤m－1）为键值的个数,即子树个数为（n＋1）。

（2）树中每个结点至多有m棵子树。

（3）除非根结点为叶子结点,否则至少有两棵子树。

（4）除根结点之外的所有非终端结点至少有「m/2?棵子树。

（5）所有叶子结点在同一个层次上,并且不含有任何信息。

B－树的特点说明有以下几点。

（1）对于非根结点的所有分支结点,n的取值范围为

（2）对于根结点,n的取值范围为1≤n≤m－1。

（3）对于叶子结点,其子树均为空树（即没有子结点）,又规定不含有任何信息,所以可以把它看作不在树中的外部结点。

（4）B－树的阶m可以事先任意指定,但一旦指定后,就应固定不变。

图8－21所示是一棵由10个键值生成的四阶B－树的示意图,该树共有四层,所有叶子结点均在第四层上。

由B－树的定义可知,在B－树上进行查找的过程与二叉排序树的查找类似。根据给定的键值k,首先在根结点的键值的集合中采用顺序（当m较小时）查找方法或二分（当m较大时）查找方法进行查找。若有k＝k_i,则查找成功,根据相应的指针即可取得记录；否则,若k在k_i和k_i＋1之间,则取指针p_i所指的结点,重复这个查找过程,直到在某结点中查找成功,或者在某结点处出现p_i为空时,则查找失败。例如,在图8－21所示B－树中查找关键字80和38。

可以证明,在含有n个关键字的B－树上进行查找时,从根结点到待查找关键字,所在路径上涉及的结点数的范围为

在B－树中插入一个键值k,不是在树中添加一个叶子结点,而是首先在最低层的某个非终端结点中添加一个键值。并且要使插入的结点中的键值字个数小于等于m－1,否则将涉及结点的“分裂”问题。

具体的插入方法如下,如图8－22所示。

（1）首先要经历从树的根结点到叶子结点的查找过程。如果键值k已在树中,则不用再进行其他操作；否则,先找出插入位置,然后再进行插入。

（2）对于叶子结点处于第（h＋1）层的树,插入的位置总是在第h层。若结点的关键字个数不超过（m－1）,则直接将键值插入就可以了；否则,需要把结点分裂为两个。

（3）分裂的做法是:取一个新结点,把原结点上的键值和k按升序排序后,从中间位置（即「m/2?之处）把键值（不包括中间位置的键值）分为两部分,左部分所含键值放在旧结点中,右部分所含键值放在新结点中,中间位置键值连同新结点的存储位置插入到父结点中。如果父结点的键值个数也超过（m－1）,则需要继续分裂,再向上插入,反复操作直至根结点为止。

B－树的删除过程与插入过程类似,只是稍为复杂一些。应使删除后的结点中的键值个数≥「m/2?,否则,就需要从其左（或右）兄弟结点“借调”关键字,若其左或右兄弟结点均无关键字可借（即结点中只有少量的关键字）,则必须进行结点的“合并”。

（1）被删关键字所在结点中关键字数目不小于「m/2?,则只需从该结点中删去该关键字k_i和相应指针p_i,树的其他部分不变。

（2）被删关键字所在结点中关键字数目等于「m/2?－1,而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于「m/2?－1,则需将其兄弟结点中最小（最大）的关键字上移至双亲结点中,将双亲结点中小于（大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点。

（3）被删关键字所在结点和其相邻的兄弟结点中的关键字数目均小于「m/2?－1。假设该结点有右兄弟,并且右兄弟结点地址由双亲结点中的指针p_i所指,则在删去关键字之后,它所在结点中剩余的关键字和指针加上双亲结点中的关键字k_i一起,合并到p_i所指结点中（若没有右兄弟,则合并到左兄弟结点中）。

（4）假设所删关键字为非终端结点中的k_i,则可以用指针p_i所指子树中的最小关键字y代替k_i,然后在相应结点中删除y。