数据结构(22)-平衡二叉树
定义
平衡二叉树(Self-Balancing Binary Search Tree 或者 Height-Balanced Binary Search Tree)，是一种二叉排序树，其中每一个结点的左子树和右子树的高度至多相差1。
平衡二叉树，也称AVL树，由俄罗斯科学家G.M.Adelson-Velskii和E.M.Landis共同发明的一种解决平衡二叉树的算法。
我们将二叉树上结点的左子树深度减去右子树深度所得到的值称为平衡因子(Balance Factor)，那么平衡二叉树上所有结点的平衡因子只可能是-1，0，1。判断一棵树是不是平衡二叉树，首先需要判断该树是不是二叉排序树，即左子树比双亲结点小，右子树比双亲结点大；然后还需要判断结点的平衡因子是否合规。
距离插入结点最近的，且平衡因子绝对值大于1的结点为根的子树，称之为最小不平衡树。
平衡二叉树实现原理
平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是破坏了，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，使之成为新的平衡子树。
假设我们有一个数组需要构建二叉排序树，根据二叉排序树的特性，我们会构建成下图左边样子，但是这样高度达到8的树，查找是比较麻烦的，而右图的样子相对来说更符合我们的预期。
avl树01.png
下面我们就来看看如何构建成右图的样子。3和2，可以正常的构建，到1的时候，此时根结点3的的平衡因子(BF)就变成了2，此时整棵树就变成了最小不平衡子树。由于BF值为证，因此我们需要将整棵树右旋，让结点2变成根结点，3变成2的右孩子。然后加入4，树还是平衡的，然后再加入结点5，此时结点3的BF值变为了-2，则需要左旋，将结点4变为结点2的右子树，结点3变为结点4的左子树，二叉树又达到了新的平衡。接着加入结点6，此时根结点2的BF值变成了-2，需要将树左旋，此时结点4变成了根结点，结点2变成了结点4的左子树，而结点3也需要进行处理，根据二叉排序树的特点结点3就变成了结点2的右孩子。接着加入结点7，此时结点5的BF值变成了-2，左旋，结点6变成了结点4的右子树，结点5变成了结点6的左子树。加入结点10，平衡。接着加入结点9，此时，结点4、6、7的BF值都变成了-2，我们只需要左旋最小不平衡子树7、9、10即可，左旋之后可以发现，树变成了非排序树，这显然是不行的，原因在于结点7的BF值是-2，结点10的BF值是1，符号并不统一，所以我们需要先对结点9和结点10进行右旋，然后再对结点7、9、10左旋，此时结点9变成了结点6的右子树，结点7变成了结点9的左子树，结点10变成了结点9的右子树，平衡。接着加入结点8，这和结点9的情况相同，结点6的BF值变成了-2，结点9的BF值变成了-1，此时需要先对结点9右旋，然后再对结点6左旋，此时结点7就变成了根结点4的右子树，结点6变成了结点7的左子树，结点9变成了结点7的右子树，结点8变成了结点9的左子树，达到最终的平衡。如上图右边所示。
可以看出构建平衡二叉树的过程，就是在不断的调整过程，BF大于1就右旋，BF小于-1就左旋。最小不平衡子树的BF与它的子树的BF符号相反时，就需要对结点先进行一次旋转使得符号相同，然后再进行旋转才能达到平衡。
平衡二叉树的实现
首先，我们需要对二叉排序树的结点结构增加一个平衡因子：
typedef int TStatus;
typedef int ElementType;
typedef struct BinaryNode {
ElementType data;
// 存储平衡因子
int bf;
struct BinaryNode *leftChild, *rightChild;
} BinaryNode, *BinaryTree;
其次，左旋右旋的时候，我们需要修改结点子树的指向：
// 对以bTree为根结点进行右旋处理
void rightRotate(BinaryTree *bTree) {
BinaryTree leftChild = (*bTree)->leftChild;
// 旋转之后leftChild的右子树就变成了bTree
// 而leftChild原来的右子树因为要满足二叉排序树的特性则需要变成bTree的左子树
(*bTree)->leftChild = leftChild->rightChild;
leftChild->rightChild = (*bTree);
// 此时新的根结点就变成了leftChild
*bTree = leftChild;
}
// 对以bTree为根结点进行左旋处理
void leftRotate(BinaryTree *bTree) {
BinaryTree rightChild = (*bTree)->rightChild;
// 旋转之后rightChild的左子树就变成了bTree
// rightChild之前的左子树比rightChild小，但是比bTree大，则需要变成bTree的右子树
(*bTree)->rightChild = rightChild->leftChild;
rightChild->leftChild = (*bTree);
// 此时新的根结点就变成rightChild
*bTree = rightChild;
}
最后，我们还需要对每个结点的平衡因子做处理，而且如果出现平衡因子符号不一致的情况，需要做双旋操作：
#define LH +1 // 左边比右边高
#define EH 0 // 左右等高
#define RH -1 // 右边比左边高
// 对以bTree为根结点的二叉树做右平衡处理
void rightBalance(BinaryTree *bTree) {
BinaryTree rightChild = (*bTree)->rightChild;
BinaryTree rightL;
switch (rightChild->bf) {
case RH:
// 新结点插入到bTree的右子树的右子树 需要左旋
(*bTree)->bf = rightChild->bf = EH;
leftRotate(bTree);
break;
case LH:
// 新结点插入到bTree的左子树的右子树 需要双旋 因为bf的值为+1 则先右旋再左旋
rightL = rightChild->leftChild;
switch (rightL->bf) {
case RH:
(*bTree)->bf = LH;
rightChild->bf = EH;
break;
case EH:
(*bTree)->bf = rightChild->bf = EH;
break;
case LH:
(*bTree)->bf = EH;
rightChild->bf = RH;
break;
default:
break;
}
rightL->bf = EH;
rightRotate(&(*bTree)->rightChild);
leftRotate(bTree);
break;
default:
break;
}
}
// 对以bTree为根结点的二叉树做左平衡处理
void leftBalance(BinaryTree *bTree) {
BinaryTree leftChild = (*bTree)->leftChild;
BinaryTree leftR;
switch (leftChild->bf) {
case LH:
// 新结点插入到bTree的左子树的左子树 需要右旋
(*bTree)->bf = leftChild->bf = EH;
rightRotate(bTree);
break;
case RH:
// 新结点插入到bTree的右子树的左子树 需要双旋 因为bf的值为-1 则先左旋再右旋
// 先修改平衡因子 然后再旋转
leftR = leftChild->rightChild;
switch (leftR->bf) {
case LH:
(*bTree)->bf = RH;
leftChild->bf = EH;
break;
case EH:
(*bTree)->bf = leftChild->bf = EH;
case RH:
(*bTree)->bf = EH;
leftChild->bf = LH;
default:
break;
}
leftR->bf = EH;
leftRotate(&(*bTree)->leftChild);
rightRotate(bTree);
break;
default:
break;
}
}
现在我们就可以直接插入结点来构建平衡二叉树了：
/// @param e 插入的结点值
/// @param isTall 插入之后树是否长高，即高度是否增加
TStatus insertAVLTree(BinaryTree *bTree, int e, bool *isTall) {
if (!(*bTree)) {
// 新插入的结点
*bTree = (BinaryTree)malloc(sizeof(BinaryNode));
(*bTree)->data = e;
(*bTree)->leftChild = (*bTree)->rightChild = NULL;
(*bTree)->bf = EH;
*isTall = true;
} else {
if ((*bTree)->data == e) {
// 已经存在data相同的结点
isTall = false;
return T_ERROR;
}
if (e < (*bTree)->data) {
// 小于 插入到左子树中
if (insertAVLTree(&(*bTree)->leftChild, e, isTall) == T_ERROR) {
// 插入失败 返回
return T_ERROR;
}
if (*isTall) {
// 插入左子树 且左子树长高
switch ((*bTree)->bf) {
case LH:
// 原来左子树比右子树高，则需要做左平衡处理
leftBalance(bTree);
*isTall = false;
break;
case EH:
// 原来左右子树等高 插入后左子树增高
(*bTree)->bf = LH;
*isTall = true;
break;
case RH:
// 原来右子树比左子树高，插入后 等高
(*bTree)->bf = EH;
*isTall = false;
break;
default:
break;
}
}
} else {
// 大于等于 插入右子树
if (insertAVLTree(&(*bTree)->rightChild, e, isTall) == T_ERROR) {
// 插入失败 返回
return T_ERROR;
}
if (*isTall) {
switch ((*bTree)->bf) {
case LH:
(*bTree)->bf = EH;
*isTall = false;
break;
case EH:
(*bTree)->bf = RH;
*isTall = true;
break;
case RH:
rightBalance(bTree);
*isTall = false;
break;
default:
break;
}
}
}
}
return T_OK;
}
平衡二叉树增加了由于带有二叉排序树的特性，而且因为自身的平衡性，降低了树的高度，这样大大的提高了对树的查找、插入、删除等动作的便利性，这三种操作的时间复杂度都为。
参考文献
- 大话数据结构
