8.6 二叉排序树

假设查找的数据集是普通的顺序存储，那么插入操作就是将记录放在表的末端，给表记录数加一即可，删除操作可以是删除后，后面的记录向前移，也可以是要删除的元素与最后一个元素互换，表记录数减一，反正整个数据集也没有什么顺序，这样的效率也不错。应该说，插入和删除对于顺序存储结构来说，效率是可以接受的，但这样的表由于无序造成查找的效率很低。

如果查找的数据集是有序线性表，并且是顺序存储的，查找可以用折半、插值、 斐波那契等查找算法来实现，可惜，因为有序，在插入和删除操作上，就需要耗费大置的时间。

有没有一种即可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法呢？还真有。

我们在 8.2 节把这种需要在查找时插入或删除的查找表称为动态查找表。我们现在就来看看什么样的结构可以实现动态查找表的高效率。

如果在复杂的问题面前，我们束手无策的话，不妨先从最最简单的情况入手。现在我们的目标是插入和查找同样高效。假设我们的数据集开始只有一个数 {62}，然后现在需要将 88 插入数据集，于是数据集成了 {62,88}，还保持着从小到大有序。再查找有没有 58 ，没有则插入，可此时要想在线性表的顺序存储中有序，就得移动 62 和 88 的位置，如图 8-6-2 左图，可不可以不移动呢？嗯，当然是可以，那就是二叉树结构。当我们用二叉树的方式时，首先我们将第一个数 62 定为根结点， 88 因为比 62 大，因此让它做 62 的右子树，58 因比 62 小，所以成为它的左子树。此时 58 的插入并没有影响到 62 与 88 的关系，如图 8-6-2 右图所示。

也就是说，若我们现在需要对集合{ 62, 88, 58, 47, 35, 73, 51, 99, 37, 93 }做查找，在我们打算创建此集合时就考虑用二叉树结构，而且是排好序的二叉树来创建。如图 8-6-3 所示，62 、88 、58 创建好后，下一个数 47 因比 58 小，是它的左子树（见③），35 是 47 的左子树（见④），73 比 62 大，但却比 88 小，是 88 的左子树（见⑤）， 51 比 62 小、比 58 小、比 47 大，是 47 的右子树（见⑥）， 99 比 62 、 88 都大，是 88 的右子树（见⑦）， 37 比 62 、 58 、 47 都小，但却比 35 大，是 35 的右子树（见⑧）， 93 则因比 62 、 88 大是 99 的左子树（见⑨）。

这样我们就得到了一棵二叉树，并且当我们对它进行中序遍历时，就可以得到一个有序的序列{ 35, 37, 47, 51, 58, 62, 73, 88, 93, 99 }，所以我们通常称它为二叉排序树。

二叉排序树（ Binary Sort Tree ），又称为二叉査找树。它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树。

从二叉排序树的定义也可以知道，它前提是二叉树，然后它采用了递归的定义方法，再者，它的结点间满足一定的次序关系，左子树结点一定比其双亲结点小，右子树结点一定比其双亲结点大。

构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。

8.6.1 二叉排序树查找操作

首先我们提供一个二叉树的结构：

/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode	/* 结点结构 */
{int data;	/* 结点数据 */struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
} BiTNode, *BiTree;

然后我们来看看二叉排序树的查找是如何实现的。

#define TRUE 1
#define FALSE 0
typedef int Status; //创建子函数返回类型 
/* 递归查找二叉排序树 T 中是否存在 key , 指针 f 指向 T 的双亲，其初始调用值为NULL */
/* 若查找成功，则指针 p 指向该数据元素结点，并返回 TRUE */
/* 否则指针 p 指向查找路径上访问的最后一个结点并返回 FALSE */
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{if (!T)	/* 查找不成功 */{*p = f;return FALSE;}else if (key == T->data)	/* 查找成功 */{*p = T;return TRUE;}else if (key < T->data){return SearchBST(T->lchild , key, T, p); /*在左子树继续查找 */}else{return SearchBST(T->rchild, key, T, p); /*在右子树继续查找 */}
}

1. SearchBST 函数是一个可递归运行的函数，函数调用时的语句为 SearchBST(T,93,NULL,p) ，参数 T 是一个二叉链表，其中数据如图 8-6-3 所示，key 代表要查找的关键字，目前我们打算查找 93 ，二叉树 f 指向 T 的双亲，当 T 指向根结点时，f 的初值就为 NULL ，它在递归时有用，最后的参数 P 是为了査找成功后可以得到查找到的结点位置。

   

2. 第 9〜13 行，是用来判断当前二叉树是否到叶子结点，显然图 8-6-3 告诉我们当前 T 指向根结点 62 的位置，T 不为空，第 11〜12 行不执行。

3. 第 14〜18 行是查找到相匹配的关键字时执行语句，显然 93≠62 ，第 16〜17 行不执行。

4. 第 19〜22 行是当要查找关键字小于当前结点值时执行语句，由于 93>62 ，第 21 行不执行。

5. 第 23〜26 行是当要查找关键字大于当前结点值时执行语句，由于 93>62 ，所以递归调用 SearchBST(T->rchild, key, T, p) 。此时 T 指向了 62 的右孩子 88 ，如图 8-6-4 所示。

   

6. 此时第二层 SearchBST ，因 93 比 88 大，所以执行第 25 行，再次递归调用 SearchBST(T->rchild, key, T, p) 。此时 T 指向了 88 的右孩子 99 ，如图 8-6-5 所示。

   

7. 第三层的 SearchBST ，因 93 比 99 小，所以执行第 21 行，递归调用 SearchBST( T->lchild, key, T, p ) 。此时 T 指向了 99 的左孩子 93 ，如图 8-6-6 所示。

   

8. 第四层 SearchBST ，因 key 等于 T->data ，所以执行第 16〜17 行，此时指针 p 指向 93 所在的结点，并返回 True 到第三层、第二层、第一层，最终函数返回 True 。

8.6.2 二叉排序树插入操作

有了二叉排序树的查找函数，那么所谓的二叉排序树的插入，其实也就是将关键字放到树中的合适位置而已，来看代码。

#define TRUE 1
#define FALSE 0
typedef int Status; //创建子函数返回类型 
/* 当二叉排序树T中不存在关键字等于 key 的数据元素时，*/
/* 插入 key 并返回 TRUE ,否則返回 FALSE */
Status InsertBST(BiTree *T,int key)
{BiTree p, s;if (!SearchBST(*T, key, NULL, &p))	/* 查找不成功 */{s = (BiTree)malloc(sizeof (BiTNode));s->data = key;s->lchild = s->rchild = NULL;if (!p){*T = s;	/* 插入 s 为新的根结点 */}else if (key < p->data){p->lchild = s; /* 插入 s 为左孩子 */}else{p->rchild = s; /* 插入 s 为右孩子 */}return TRUE;}elsereturn FALSE;	/* 树中已有关键字相同的结点，不再插入 */
}

这段代码非常简单。如果你调用函数是 “InsertBST(T, 93);” ，那么结果就是 FALSE ，如果是 “InsertBST (T,95);” ，那么一定就是在 93 的结点增加一个右孩子 95 ，并且返回 True 。如图 8-6-7 所示。

有了二叉排序树的插入代码，我们要实现二叉排序树的构建就非常容易了。下面的代码就可以创建一棵图 8-6-3 这样的树。

int i;
int a[10] = {62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(i=0;i<10;i++)
{InsertBST(&T,a[i]);
}

8.6.3 二叉排序树删除操作

俗话说 “请神容易送神难” ，我们已经介绍了二叉排序树的查找与插入算法，但是对于二叉排序树的删除，就不是那么容易，我们不能因为删除了结点，而让这棵树变得不满足二叉排序树的特性，所以删除需要考虑多种情况。

如果需要查找并删除如 37 、51 、73 、93 这些在二叉排序树中是叶子的结点，那是很容易的，毕竟删除它们对整棵树来说，其他结点的结构并未受到影响，如图 8-6-8 所示。

对于要删除的结点只有左子树或只有右子树的情况，相对也比较好解决。那就是结点删除后，将它的左子树或右子树整个移动到删除结点的位置即可，可以理解为独子继承父业。比如图 8-6-9，就是先删除 35 和 99 结点，再删除 58 结点的变化图，最终，整个结构还是一个二叉排序树。

但是对于要删除的结点既有左子树又有右子树的情况怎么办呢？比如图 8-6-10 中的 47 结点若要删除了，它的两儿子以及子孙们怎么办呢？

起初的想法，我们当 47 结点只有一个左子树，那么做法和一个左子树的操作一 样，让 35 及它之下的结点成为 58 的左子树，然后再对 47 的右子树所有结点进行插入操作，如图 8-6-11 所示。这是比较简单的想法，可是 47 的右子树有子孙共 5 个结点，这么做效率不高且不说，还会导致整个二叉排序树结构发生很大的变化，有可能会增加树的高度。增加高度可不是个好事，这我们待会再说，总之这个想法不太好。

我们仔细观察一下，47 的两个子树中能否找出一个结点可以代替 47 呢？果然有，37 或者 48 都可以代替 47 ，此时在删除 47 后，整个二叉排序树并没有发生什么本质的改变。

为什么是 37 和 48 ? 对的，它们正好是二叉排序树中比它小或比它大的最接近 47 的两个数。也就是说，如果我们对这棵二叉排序树进行中序遍历，得到的序列 { 29, 35, 36, 37, 47, 48, 49, 50, 51, 56, 58, 62, 73, 88, 93, 99 }，它们正好是 47 的前驱和后继。

因此，比较好的办法就是，找到需要删除的结点 p 的直接前驱（或直接后继） s , 用 s 来替换结点 p ，然后再删除此结点 s ，如图 8-6-12 所示。

根据我们对删除结点三种情况的分析：

• 叶子结点；
• 仅有左或右子树的结点；
• 左右子树都有的结；

我们来看代码，下面这个算法是递归方式对二叉排序树 T 査找 key ，查找到时删除。

typedef int Status; //创建子函数返回类型 
/* 若二叉排序树T中存在关键字等于 key 的数据元素时，则删除该数据元素结点，*/
/* 并返回 TRUE ;否則返回 FALSE */
Status DeleteBST(BiTree *T, int key)
{if(!*T) /* 不存在关键字等于 key 的数据元素 */{return FALSE;}else{if(key == (*T)->data) /* 找到关键字等于 key 的数据元素 */{return Delete(T);}else if(key < (*T)->data){return DeleteBST(&(*T)->lchild, key);}else {return DeleteBST(&(*T)->rchild, key);}}
}

这段代码和前面的二叉排序树查找几乎完全相同，唯一的区别就在于第 14 行，此时执行的是 Delete 方法，对当前结点进行删除操作。我们来看 Delete 的代码。

typedef int Status; //创建子函数返回类型 
/*从二叉排序树中删除结点P,并重接它的左或右子树。*/
Status Delete(BiTree *p)
{BiTree q, s;if ((*p)->rchild = NULL)	/* 右子树空则只需重接它的左子树 */{q = *p;*p = (*p)->lchild;free(q);}else if ((*p)->lchild == NULL)	/* 只需重接它的右子树 */{q = *p;*p = (*p)->rchild;free(q);}else /* 左右子树均不空 */{q = *p;s = (*p)->lchild;while(s->rchild) /* 转左，然后向右到尽头（找待测结点的前驱）*/{q = s;s - s->rchild;}(*p)->data = s->data;	/* s 指向被删结点的直接前驱 */if (q != *p){q->rchild = s->lchild;	/* 重接 q 的右子树 */}else{q->lchilds = s->lchild;	/* 重接 q 的左子树 */}free(s);}return TRUE;
}

从这段代码也可以看出，我们其实是在找删除结点的前驱结点替换的方法，对于用后继结点来替换，方法上是一样的。

8.6.4 二叉排序树总结

总之，二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为 1 次，即根结点就是要找的结点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。

例如 { 62, 88, 58, 47, 35, 73, 51, 99, 37, 93 } 这样的数组，我们可以构建如下图左图的二叉排序树。但如果数组元素的次序是从小到大有序，如 { 35, 37, 47, 51, 58, 62, 73, 88, 93, 99 } ，则二叉排序树就成了极端的右斜树，注意它依然是一棵二叉排序树，如图 8-6-19 的右图。此时，同样是查找结点 99 ，左图只需要两次比较，而右图就需要 10 次比较才可以得到结果，二者差异很大。

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，均为 [log2n]+1 ，那么查找的时间复杂也就为 O(logn) 近似于折半查找，事实上，图 8-6-18 的左图也不够平衡，明显的左重右轻。

不平衡的最坏情况就是像上图右图的斜树，查找时间复杂度为 O(n) ，这等同于顺序查找。

因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树。这样我们就引申出另一个问题，如何让二叉排序树平衡的问题。

8.7 平衡二叉树（ AVL树 ）

平衡二叉树（ Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree )，是一种二叉排序树，其中每一个节点的左子树和右子树的髙度差至多等于 1 。

有两位俄罗斯数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年共同发明一种解决平衡二叉树的算法，所以有不少资料中也称这样的平衡二叉树为 AVL 树。

从平衡二叉树的英文名字，你也可以体会到，它是一种髙度平衡的二叉排序树。 那什么叫做高度平衡呢？意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子 BF ( Balance Factor ），那么平衡二叉树上所有结点的平衡因子只可能是 -1、 0 和 1 。只要二叉树上有一个结点的平衡因子的绝对值大于 1 ，则该二叉树就是不平衡的。

看图 8-7-2 ，为什么图 1 是平衡二叉树，而图 2 却不是呢？这里就是考查我们对平衡二叉树的定义的理解，它的前提首先是一棵二叉排序树，右上图的 59 比 58 大， 却是 58 的左子树，这是不符合二叉排序树的定义的。图 3 不是平衡二叉树的原因就在于，结点 58 的左子树高度为 3 ，而右子树为 1，二者差大于了绝对值 1 ，因此它也不是平衡的。而经过适当的调整后的图 4 ，它就符合了定义，因此它是平衡二叉树。

距离插入结点最近的，且平衡因子的绝对值大于 1 的结点为根的子树，我们称为最小不平衡子树。图 8-7-3 中，当新插入结点 37 时，距离它最近的平衡因子绝对值超过 1 的结点是 58 （ 即它的左子树高度 2 减去右子树高度 0 ），所以从 58 开始以下的子树为最小不平衡子树。

8.7.1 平衡二叉树实现原理

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

为了能在讲解算法时轻松一些，我们先讲一个平衡二叉树构建过程的例子。假设我们现在有一个数组 a[10]={ 3, 2, 1, 4, 5, 6, 7, 10, 9, 8 } 需要构建二叉排序树。在没有学习平衡二叉树之前，根据二叉排序树的特性，我们通常会将它构建成如图 8-7-4 的图 1 所示的样子。虽然它完全符合二叉排序树的定义，但是对这样高度达到 8 的二叉树来说，查找是非常不利的。我们更期望能构建成如图 8-7-4 的图 2 的样子，高度为 4 的二叉排序树才可以提供高效的查找效率。那么现在我们就来研究如何将一个数组构建出图 2 的树结构。

对于数组 a[10]={3, 2, 1, 4, 5, 6, 7, 10, 9, 8 } 的前两位 3 和 2，我们很正常地构建，到了第 3 个数 “1” 时，发现此时根结点 “3” 的平衡因子变成了 2 ，此时整棵树都成了最小不平衡子树，因此需要调整，如图 8-7-5 的图 1（ 结点左上角数字为平衡因子 BF 值 ）。因为 BF 值为正，因此我们将整个树进行右旋（ 顺时针旋转 ），此时结点 2 成了根结点，3 成了 2 的右孩子，这样三个结点的 BF 值均为 0 ，非常的平衡，如图 8-7-5 的图 2 所示。

然后我们再增加结点 4 ，平衡因子没发生改变，如图 3 。增加结点 5 时，结点 3 的 BF 值为 -2 ，说明要旋转了。由于 BF 是负值，所以我们对这棵最小平衡子树进行左旋（ 逆时针旋转 ），如图 4 ，此时我们整个树又达到了平衡。

继续，增加结点 6 时，发现根结点 2 的 BF 值变成了 -2 ，如图 8-7-6 的图 6 。所以我们对根结点进行了左旋，注意此时本来结点 3 是 4 的左孩子，由于旋转后需要满足二叉排序树特性，因此它成了结点 2 的右孩子，如图 7。增加结点 7 ，同样的左旋转，使得整棵树达到平衡，如图 8 和图 9 所示。

当增加结点 10 时，结构无变化，如图 8-7-7 的图 10 。再增加结点 9 ，此时结点 7 的 BF 变成了 -2 ，理论上我们只需要旋转最小不平衡子树 7、9、10 即可，但是如果左旋转后，结点 9 就成了 10 的右孩子，这是不符合二叉排序树的特性的，此时不能简单的左旋，如图 11 所示。

仔细观察图 11，发现根本原因在于结点 7 的 BF 是 -2 ，而结点 10 的 BF 是 1，也就是说，它们俩一正一负，符号并不统一，而前面的几次旋转，无论左还是右旋， 最小不平衡子树的根结点与它的子结点符号都是相同的。这就是不能直接旋转的关键。那怎么办呢？

不统一，不统一就把它们先转到符号统一再说，于是我们先对结点 9 和结点 10 进行右旋，使得结点 10 成了 9 的右子树，结点 9 的 BF 为 -1，此时就与结点 7 的 BF值符号统一了，如图 8-7-7 的图 12 所示。

这样我们再以结点 7 为最小不平衡子树进行左旋，得到图 8-7-8 的图 13 。接着插入 8，情况与刚才类似，结点 6 的 BF 是 -2，而它的右孩子 9 的 BF 是 1，如图 14 , 因此首先以 9 为根结点，进行右旋，得到图 15 ，此时结点 6 和结点 7 的符号都是负，再以 6 为根结点左旋，最终得到最后的平衡二叉树，如图 8-7-8 的图 16 所示。

西方有一句民谣是这样说的：“丢失一个钉子，坏了一只蹄铁；坏了一只蹄铁，折了一匹战马；折了一匹战马，伤了一位骑士；伤了一位骑士，输了一场战斗；输了一场战斗，亡了一个帝国。”相信大家应该有点明白，所谓的平衡二叉树，其实就是在二叉排序树创建过程中保证它的平衡性，一旦发现有不平衡的情况，马上处理，这样就不会造成不可收拾的情况出现。通过刚才这个例子，你会发现，当最小不平衡子树根结点的平衡因子 BF 是大于 1 时，就右旋，小于 -1 时就左旋，如上例中结点 1、5、6、7 的插入等。插入结点后，最小不平衡子树的 BF 与它的子树的 BF 符号相反时，就需要对结点先进行一次旋转以使得符号相同后，再反向旋转一次才能够完成平衡操作，如上例中结点 9、8 的插入时。

8.7.2 平衡二叉树实现算法

好了，有这么多的准备工作，我们可以来讲解代码了。首先是需要改进二叉排序树的结点结构，增加一个 bf ，用来存储平衡因子。

/* 二叉树的二叉链表结点结构定义 */
typedef struct	BiTNode	 /* 结点结构 */
{int data;	/* 结点数据 */int bf;		/* 结点的平衡因子 */struct BiTNode *lchild, *rchild;	/* 左右孩子指针 */
} BiTNode, *BiTree;

然后，对于右旋操作，我们的代码如下。

/* 对以 p 为根的二叉排序树作右旋处理，*/
/* 处理之后 p 指向新的树根结点，即旋转处理之前的左子树的根结点 */
void R_Rotate(BiTree *P)
{BiTree L;L = (*P)->lchild;			/*	L 指向 P 的左子树根结点 */(*P)->lchild = L->rchild;	/* L 的右子树挂接为 P 的左子树 */L->rchild = (*P);*P = L;						/* P 指向新的根结点 */
}

此函数代码的意思是说，当传入一个二叉排序树 P ，将它的左孩子结点定义为 L，将 L 的右子树变成 P 的左子树，再将 P 改成 L 的右子树，最后将 L 替换 P 成为根结点。这样就完成了一次右旋操作，如图 8-7-9 所示。图中三角形代表子树，N 代表新增结点。

上面例子中的新增加结点 N （ 如下图的图 1 和图 2 ），就是右旋操作。

左旋操作代码如下：

/* 对以 P 为根的二叉排序树作 左旋 处理，*/
/* 处理之后 P 指向新的树根结点，即旋转处理之前的右子树的根结点 0 */
void L_Rotate(BiTree *P)
{BiTree R;R = (*P)->rchild;		/* R 指向P的右子树根结点*/(*P)->rchild = R->lchild;	/* R 的左子树挂接为 P 的右子树*/R->lchild = (*P);*P = R;				/* P 指向新的根结点*/
}

这段代码与右旋代码是对称的，在此不做解释了。上面例子中的新增结点 5、6、7（ 如图 8-7-5 的图 4、5，图 8-7-6 的图 6、7、8、9 ），都是左旋操作。

现在我们来看左平衡旋转处理的函数代码。

#define LH +1	/* 左高 */
#define EH 0	/* 等高 */
#define RH -1	/* 右高 */
/* 对以指针 T 所指结点为根的二叉树作左平衡旋转处理 */
/* 本算法结束时，指针 T 指向新的根结点 */
void LeftBalance(BiTree *T)
{BiTree L, Lr;L = (*T)->lchild;	/* L 指向 T 的左子树根结点 */switch (L->bf){/* 检查 T 的左子树的平衡度，并作相应平衡处理 */case LH:	/* 新结点插入在 T 的左孩子的左子树上，要作单右旋处理 */(*T)->bf = L->bf = EH;R_Rotate(T);break;case RH:	/* 新结点插入在 T 的左孩子的右子树上，要作双旋处理 */Lr = L->rchild;	/* Lr 指向 T 的左孩子的右子树根 */switch (Lr->bf) /* 修改 T 及其左孩子的平衡因子 */{case LH: (*T)->bf = RH;L->bf = EH;break;case EH:	(*T)->bf = L->bf = EH;break;case RH:	(*T)->bf = EH;L->bf = LH;break;}Lr->bf = EH;L_Rotate(&(*T)->lchild);    /* 对 T 的左子树作左旋平衡处理 */R_Rotate(T);                /* 对 T 作右旋平衡处理 */}
}

首先，我们定义了三个常数变量，分别代表 1、0、-1 。

1. 函数被调用，传入一个需调整平衡性的子树 T 。由于 LeftBalance 函数被调用时，其实是已经确认当前子树是不平衡状态，且左子树的高度大于右子树的高度。换句话说，此时 T 的根结点应该是平衡因子 BF 的值大于 1 的数。

2. 第 9 行，我们将 T 的左孩子赋值给 L 。

3. 第 10〜36 行是分支判断。

4. 当 L 的平衡因子为 LH ，即为 1 时，表明它与根结点的 BF 值符号相同，因此，第 14 行，将它们的 BF 值都改为 0 ，并且第 15 行，进行右旋操作。操作的方式如图 8-7-9 所示。

5. 当 L 的平衡因子为 RH ，即为 -1 时，表明它与根结点的 BF 值符号相反，此时需要做双旋处理。第 19〜32 行，针对 L 的右孩子 Lr 的 BF 作判断，修改根结点 T 和 L 的 BF 值。第 33 行将当前 Lr 的 BF 改为 0 。

6. 第 34 行，对根结点的左子树进行左旋，如图 8-7-10 第二图所示。

7. 第 35 行，对根结点进行右旋，如图 8-7-10 的第三图所示，完成平衡操作。

同样的，右平衡旋转处理的函数代码非常类似，直接看代码，不做讲解了。

我们前面例子中的新增结点 9 和 8 就是典型的右平衡旋转，并且双旋完成平衡的例子（如图 8-7-7 的图11、12，图 8-7-8 图14、15、16所示)。

有了这些准备，我们的主函数才算是正式登场了。

#define LH +1	/* 左高 */
#define EH 0	/* 等高 */
#define RH -1	/* 右高 */
#define TRUE 1
#define FALSE 0
typedef int Status; //创建子函数返回类型 
/* 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */ 
/* 数据元素为 e 的新结点并返回 1 ,否则返回 0 。若因插入而使二叉排序树 */ 
/* 失去平衡，则作平衡旋转处理，布尔变量 taller 反映 T 长高与否。*/
Status InsertAVL(BiTree *T, int e, Status *taller)
{if (!*T){/* 插入新结点，树“长高”，置 taller 为 TRUE */*T = (BiTree)malloc(sizeof(BiTNode));(*T)->data = e;(*T)->lchild = (*T)->rchild = NULL;(*T)->bf = EH;*taller = TRUE;}else{if (e == (*T)->data){/* 树中已存在和 e 有相同关键字的结点则不再插入 */*taller = FALSE;return FALSE;}if (e < (*T)->data){/* 应继续在 T 的左子树中进行搜索 */if (!InsertAVL(&(*T>->lchild, e, taller))  /* 未插入 */{return FALSE;}if (taller) /* 已插入到 T 的左子树中且左子树“长高” */{switch ((*T)->bf) /* 检查 T 的平衡度 */{case LH: /* 原本左子树比右子树高，需要作左平衡处理 */LeftBalance(T);*taller = FALSE;break;case EH: /* 原本左右子树等高，现因左子树增高而树增高 */(*T)->bf = LH;*taller = TRUE;break;case RH: /* 原本右子树比左子树高，现左右子树等高 */(*T)->bf = EH;*taller = FALSE;break;}}}else{/* 应继续在 T 的右子树中进行搜索 */if (!InsertAVL(&(*T)->rchild, e, taller)) /* 未插入 */{return FALSE;}if (*taller) /* 已插入到 T 的右子树且右子树“长高” */{switch ((*T)->bf) /* 检查 T 的平衡度 */{case	LH: /* 原本左子树比右子树高，现左、右子树等高 */(*T)->bf = EH;*taller = FALSE;break;case	EH: /* 原本左右子树等高，现因右子树增高而树增高 */(*T)->bf = RH;*taller = TRUE;break;case	RH: /* 原本右子树比左子树高，需要作右平衡处理 */RightBalance(T);*taller = FALSE;break;}}}}return TRUE;
}

1. 程序开始执行时，第 12〜20 行是指当前 T 为空时，则申请内存新增一个结点。

2. 第 23〜28 行表示当存在相同结点，则不需要插入。

3. 第 29〜54 行，当新结点 e 小于 T 的根结点值时，则在 T 的左子树査找。

4. 第 32〜35 行，递归调用本函数，直到找到则返回 false ，否则说明插入结点成功，执行下面语句。

5. 第 36〜53 行，当 taller 为 TRUE 时，说明插入了结点，此时需要判断 T 的平衡因子，如果是 1 ，说明左子树高于右子树，需要调用 LeftBalance 函数进行左平衡旋转处理。如果为 0 或 -1 ，则说明新插入结点没有让整棵二叉排序树失去平衡性，只需要修改相关的 BF 值即可。

6. 第 55〜80 行，说明新结点 e 大于 T 的根结点的值，在 T 的右子树查找。代码上述类似，不再详述。

对于这段代码来说，我们只需要在需要构建平衡二叉树的时候执行如下列代码即可在内存中生成一棵与图 8-7-4 的图 2 相同的平衡的二叉树。

int i;
int a[10] = { 3, 2, 1, 4, 5, 6, 7, 10, 9, 8 };
BiTree T = NULL;
Status taller;
for (i = 0; i<10; i++)
{InsertAVL(&T, a[i], &taller);
}

不容易，终于讲完了，本算法代码很长，是有些复杂，编程中容易在很多细节上出错，要想真正掌握它，需要多练习。不过其思想还是不难理解的，总之就是把不平衡消灭在最早时刻。

如果我们需要查找的集合本身没有顺序，在频繁查找的同时也需要经常的插入和删除操作，显然我们需要构建一棵二叉排序树，但是不平衡的二叉排序树，查找效率是非常低的，因此我们需要在构建时，就让这棵二叉排序树是平衡二叉树，此时我们的查找时间复杂度就为 O(logn) ，而插入和删除也为 O(logn) 。这显然是比较理想的一种动态查找表算法。