9.3.2　平衡二叉树

平衡二叉树（Balanced Binary Tree）又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树；它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子（Balance Factor，BF）定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是－1、0和1。如图9－7（a）所示为两棵平衡二叉树，而图9－7（b）所示为两棵不平衡的二叉树，结点中的值为该结点的平衡因子。

图9－7 平衡与不平衡的二叉树及结点的平衡因子

先看一个具体例子（参见图9－8）。假设表中关键字序列为（13，24，37，90，53）。空树和1个结点的树显然都是平衡的二叉树。在插入24之后仍是平衡的，只是根结点的平衡因子BF由0变为－1；在继续插入37之后，由于结点的BF值由－1变成－2，由此出现了不平衡的现象。由此，可以对树作一个向左逆时针“旋转”的操作，令结点为根，而结点为它的左子树，此时，结点和的平衡因子都为0，而且仍保持二叉排序树的特性。在继续插入和之后，由于结点的BF值由－1变成－2，排序树中出现了新的不平衡的现象，需进行调整。但此时由于结点插在结点的左子树上，因此不能如上作简单调整。对于以结点为根的子树来说，既要保持二叉排序树的特性，又要平衡，则必须以作为根结点，而使成为它的左子树的根。成为它的右子树的根。这好比对树作了两次旋转操作——先向右顺时针，后向左逆时针（如图9－8（f）～（h）所示），使二叉排序树由不平衡转化为平衡。

图9－8 平衡树的生成过程

假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a，则失去平衡后进行调整的规律可归纳为下列四种情况。

（1）单向右旋平衡处理：由于在＊a的左子树根结点的左子树上插入结点，＊a的平衡因子由1增至2，致使以＊a为根的子树失去平衡，则需进行一次向右的顺时针旋转操作。

（2）单向左旋平衡处理：由于在＊a的右子树根结点的右子树上插入结点，＊a的平衡因子由－1增至－2，致使以＊a为根结点的子树失去平衡，则需进行一次向左的逆时针旋转操作。

（3）双向旋转（先左后右）平衡处理：由于在＊a的左子树根结点的右子树上插入结点，＊a的平衡因子由1增至2，致使以＊a为根结点的子树失去平衡，则需进行两次旋转（先左旋转后右旋转）操作。

（4）双向旋转（先右后左）平衡处理：由于在＊a的右子树根结点的左子树上插入结点，＊a的平衡因子由－1变为－2，致使以＊a为根结点的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

上述4种情况中，（1）和（2）对称，（3）和（4）对称。旋转操作的正确性容易由“保持二叉排序树的特性：中序遍历所得关键字序列自小至大有序”证明之。以上平衡算法如下：算法9.9为左平衡处理算法，算法9.7和算法9.8分别描述了在平衡处理中进行右旋转操作和左旋操作时修改指针的情况。右平衡处理的算法和左平衡算法类似，这里不再赘述。

算法9.7 二叉排序树作右旋转

算法9.8 二叉排序树作左旋转

算法9.9 二叉排序树作左平衡旋转

在平衡树上进行查找的过程和排序树相同，因此，在查找过程中和给定值进行比较的关键字个数不超过树的深度。在平衡树上进行查找的时间复杂度为O（log2n）。（注：上述对平衡二叉树的查找性能的讨论是在等概率的前提下进行的。）