8.7.2　平衡二叉树实现算法

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

  1. /* 二叉树的二叉链表结点结构定义 */
  2. /* 结点结构 */
  3. typedef struct BiTNode                  
  4. {
  5.     /* 结点数据 */
  6.     int data;                           
  7.     /* 结点的平衡因子 */
  8.     int bf;                             
  9.     /* 左右孩子指针 */
  10.     struct BiTNode *lchild, *rchild;    
  11. } BiTNode, *BiTree;

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

  1. /* 对以p为根的二叉排序树作右旋处理， */
  2. /* 处理之后p指向新的树根结点，即旋转处理之前
  3.    的左子树的根结点 */
  4. void R_Rotate(BiTree *P)
  5. {
  6.     BiTree L;
  7.     /* L指向P的左子树根结点 */
  8.     L = (*P)->lchild;            
  9.     /* L的右子树挂接为P的左子树 */
  10.     (*P)->lchild = L->rchild;    
  11.     L->rchild = (*P);
  12.     /* P指向新的根结点 */
  13.     *P = L;                      
  14. }

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

8.7.2　平衡二叉树实现算法 - 图1

图8-7-9

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

左旋操作代码如下。

  1. /* 对以P为根的二叉排序树作左旋处理， */
  2. /* 处理之后P指向新的树根结点，即旋转处理之前
  3.    的右子树的根结点0 */
  4. void L_Rotate(BiTree *P)
  5. {
  6.     BiTree R;
  7.     /* R指向P的右子树根结点 */
  8.     R = (*P)->rchild;            
  9.     /* R的左子树挂接为P的右子树 */
  10.     (*P)->rchild = R->lchild;    
  11.     R->lchild = (*P);
  12.     /* P指向新的根结点 */
  13.     *P = R;                      
  14. }

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

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

  1. #define LH +1  /* 左高 */
  2. #define EH 0   /* 等高 */
  3. #define RH -1  /* 右高 */
  4. /* 对以指针T所指结点为根的二叉树作左平衡旋转
  5.    处理 */
  6. /* 本算法结束时，指针T指向新的根结点 */
  7. void LeftBalance(BiTree *T)
  8. {
  9.     BiTree L,Lr;
  10.     /* L指向T的左子树根结点 */
  11.     L = (*T)->lchild;               
  12.     switch (L->bf)
  13.     {                               
  14.     /* 检查T的左子树的平衡度，并作相应平衡处理 */
  15.     /* 新结点插入在T的左孩子的左子树上，要作单右旋处理 */
  16.     case LH:                        
  17.         (*T)->bf = L->bf = EH;
  18.         R_Rotate(T);
  19.         break;
  20.     /* 新结点插入在T的左孩子的右子树上，要作双旋处理 */
  21.     case RH:                        
  22.         /* Lr指向T的左孩子的右子树根 */
  23.         Lr = L->rchild;             
  24.         /* 修改T及其左孩子的平衡因子 */
  25.         switch (Lr->bf)             
  26.         {
  27.         case LH: (*T)->bf = RH;
  28.             L->bf = EH;
  29.             break;
  30.         case EH: (*T)->bf = L->bf = EH;
  31.             break;
  32.         case RH: (*T)->bf = EH;
  33.             L->bf = LH;
  34.             break;
  35.         }
  36.         Lr->bf = EH;
  37.         /* 对T的左子树作左旋平衡处理 */
  38.         L_Rotate(&(*T)->lchild);    
  39.         /* 对T作右旋平衡处理 */
  40.         R_Rotate(T);                
  41.     }
  42. }

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

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

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

3.第5～27行是分支判断。

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

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

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

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

8.7.2　平衡二叉树实现算法 - 图2

图8-7-10

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

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

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

  1. /* 若在平衡的二叉排序树T中不存在和e有相同关键
  2.    字的结点，则插入一个 */
  3. /* 数据元素为e的新结点并返回1，否则返回0。若
  4.    因插入而使二叉排序树 */
  5. /* 失去平衡，则作平衡旋转处理，布尔变量taller
  6.    反映T长高与否。 */
  7. Status InsertAVL(BiTree *T, int e, Status *taller)
  8. {
  9.     if (!*T)
  10.     {                                                    
  11.         /* 插入新结点，树“长高”，置taller为TRUE */
  12.         *T = (BiTree)malloc(sizeof(BiTNode));
  13.         (*T)->data = e;
  14.         (*T)->lchild = (*T)->rchild = NULL;
  15.         (*T)->bf = EH;
  16.         *taller = TRUE;
  17.     }
  18.     else
  19.     {
  20.         if (e == (*T)->data)
  21.         {                                                
  22.             /* 树中已存在和e有相同关键字的结点则不再插入 */
  23.             *taller = FALSE;
  24.             return FALSE;
  25.         }
  26.         if (e < (*T)->data)
  27.         {                                                
  28.             /* 应继续在T的左子树中进行搜索 */
  29.             /* 未插入 */
  30.             if (!InsertAVL(&(*T)->lchild, e, taller))    
  31.                 return FALSE;
  32.             /* 已插入到T的左子树中且左子树“长高” */
  33.             if (*taller)                                 
  34.             {
  35.                 /* 检查T的平衡度 */
  36.                 switch ((*T)->bf)                        
  37.                 {
  38.                 /* 原本左子树比右子树高，需要作左平衡处理 */
  39.                 case LH:                                 
  40.                     LeftBalance(T);
  41.                     *taller = FALSE;
  42.                     break;
  43.                 /* 原本左右子树等高，现因左子树增高而树增高 */
  44.                 case EH:                                 
  45.                     (*T)->bf = LH;
  46.                     *taller = TRUE;
  47.                     break;
  48.                 /* 原本右子树比左子树高，现左右子树等高 */
  49.                 case RH:                                 
  50.                     (*T)->bf = EH;
  51.                     *taller = FALSE;
  52.                     break;
  53.                 }
  54.             }
  55.         }
  56.         else
  57.         {                                                
  58.             /* 应继续在T的右子树中进行搜索 */
  59.             /* 未插入 */
  60.             if (!InsertAVL(&(*T)->rchild, e, taller))    
  61.                 return FALSE;
  62.             /* 已插入到T的右子树且右子树“长高” */
  63.             if (*taller)                                 
  64.             {
  65.                 /* 检查T的平衡度 */
  66.                 switch ((*T)->bf)                        
  67.                 {
  68.                 /* 原本左子树比右子树高，现左、右子树等高 */
  69.                 case LH:                                 
  70.                     (*T)->bf = EH;
  71.                     *taller = FALSE;
  72.                     break;
  73.                 /* 原本左右子树等高，现因右子树增高而树增高 */
  74.                 case EH:                                 
  75.                     (*T)->bf = RH;
  76.                     *taller = TRUE;
  77.                     break;
  78.                  /* 原本右子树比左子树高，需要作右平衡处理 */
  79.                 case RH:                                
  80.                     RightBalance(T);
  81.                     *taller = FALSE;
  82.                     break;
  83.                 }
  84.             }
  85.         }
  86.     }
  87.     return TRUE;
  88. }

1.程序开始执行时，第3～10行是指当前T为空时，则申请内存新增一个结点。 2.第13～17行表示当存在相同结点，则不需要插入。 3.第18～40行，当新结点e小于T的根结点值时，则在T的左子树查找。 4.第20～21行，递归调用本函数，直到找到则返回false，否则说明插入结点成功，执行下面语句。 5.第22～39行，当taller为TRUE时，说明插入了结点，此时需要判断T的平衡因子，如果是1，说明左子树高于右子树，需要调用LeftBalance函数进行左平衡旋转处理。如果为0或-1，则说明新插入结点没有让整棵二叉排序树失去平衡性，只需要修改相关的BF值即可。 6.第41～63行，说明新结点e大于T的根结点的值，在T的右子树查找。代码上述类似，不再详述。

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

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

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

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