引言

在二叉查找树中存在退化成单链表的极端情况，例如序列，构建二叉查找树如图所示：

图1 二叉树退化成单链表

此时二叉树搜索时间复杂度为。二叉查找树的查找效率取决于树的高度，因此树的高度越小，查找效率越高。如果将图1改为图2方式存储，查找6只需比较3次。

图2 平衡二叉树

从图2中可以看出，当结点数目一定，保持树的左右两端保持平衡，树的查找效率最高。这里所说的平衡是指左右子树的高度相差不超过1。

概念

平衡二叉树（Balanced Binary Tree）又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好地解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在。但是频繁旋转会使插入和删除牺牲掉左右的时间，不过相对二叉查找树来说，时间上稳定了很多。平衡二叉树中左右子树的高度差称之为平衡因子。

举几个例子，如图3不是平衡二叉树，因为结点60左右子树高度差为2。

图3 非平衡二叉树

图4不是平衡二叉树，因为66的左右子树高度差为2。

图4 非平衡二叉树

平衡因子

平衡因子：某结点左右子树高度差为该结点的平衡因子（BF, Balance Factor）。平衡二叉树中结点的平衡因子只能是0、1或者-1。左右子树等高为0，左高右低为1，左低右高为-1。

自平衡是指在对平衡二叉树执行插入和删除结点操作后，可能会导致树中某个结点的平衡因子绝对值超过1，即平衡二叉树失去“平衡”，此时需要通过旋转操作恢复该结点的平衡。

图5 平衡因子为0

图6 平衡因子为1

图7 平衡因子为-1

插入结点后失衡和调整

如图8是一个平衡二叉树，每个结点的平衡因子绝对值都不超过1。

图8 平衡二叉树

对平衡二叉树插入新结点99后，结点左子树高度为1，右子树高度变为3，此时平衡因子为-2。

图9 失衡二叉树

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过1的结点为根的子树称为最小不平衡子树。图9中以结点66为父结点的树就称为最小失衡子树。

平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的，通常有以下几种类型：

【LL型】

如图10是LL型二叉树，每个结点的平衡因子都是不小于0。结点66的左子树高度为3，右子树高度为1，此时平衡因子为2。为保证树的平衡，此时需要对结点66做顺时针右旋，流程如下：

图10 LL型二叉树右旋

右旋过程总结如下：

• 失衡结点的左孩子替代此失衡结点。
• 失衡结点的左孩子的右子树变为失衡结点的左子树。
• 将此失衡结点作为左孩子结点的右子树。

【RR型】

如图11是RR型二叉树，每个结点的平衡因子都不大于0。结点66的左子树高度为1，右子树高度为3，此时平衡因子为-2。为保证树的平衡，此时需要对结点66做逆时针左旋，流程如下：

图11 RR型左旋

左旋过程总结如下：

• 失衡结点的右孩子替代此失衡结点位置。
• 失衡结点的右孩子的左子树变为失衡结点的右子树。
• 失衡结点本身变为右孩子的左子树。

【LR型】

如图12是LR型二叉树，结点60的左子树高度为2，右子树高度为0，此时平衡因子为2；而结点55的平衡因子为-1。 为保证树的平衡，此时需要对结点60的左子树左旋，然后对该结点右旋，流程如下：

图12 LR型先左旋后右旋

过程总结如下：

• 对失衡结点A的左孩子B进行左旋操作，即上述RR情形操作。
• 对失衡结点A做右旋操作，即上述LL情形操作。

【RL型】

如图13是RL型二叉树，结点75的左子树高度为0，右子树高度为2，此时平衡因子为-2；而结点80的平衡因子为1。 为保证树的平衡，此时需要对结点75的右子树右旋，然后对该结点左旋，流程如下：

图13 RL型先右旋后左旋

过程总结如下：

• 对失衡结点A的右孩子B进行右旋操作，即上述LL情形操作。
• 对失衡结点A做左旋操作，即上述RR情形操作。

删除结点后失衡和调整

平衡二叉树的结点删除包括两个过程，查找和删除。结点的删除有以下三种情况：

• 待删除结点度为0。
• 待删除结点度为1。
• 待删除结点度为2。

【删除结点度为0】

如下图14所示，待删除节点值为 “80”，该结点无子树，删除后并不影响平衡二叉树的结构特性，可以直接删除。平衡二叉树中待删除结点度为0时，该结点为叶子结点，可以直接删除。

图14 删除结点度为0

【删除结点度为1】

如下图15所示，待删除结点值为“77”，该结点有一个左子树，删除结点后，为了维持平衡二叉树结构特性，需要将左子树“上移”到删除的结点位置上。平衡二叉树中待删除的结点度为1时，可以将待删除结点的左子树或右子树“上移”到删除结点位置上，以此来满足平衡二叉树的结构特性。

图15 删除结点度为1

【删除结点度为2】

如下图16所示，待删除结点值为 “77”，该结点既有左子树，也有右子树，删除结点后，为了维持平衡二叉树的结构特性，需要从其左子树中选出一个最大值的结点，“上移”到删除的结点位置上。平衡二叉树中待删除结点的度为2时，可以将待删除结点的左子树中的最大值结点“移动”到删除结点位置上，以此来满足平衡二叉树的结构特性。操作过程：

• 查找出左子树中的最大值结点M。
• 替换待删除结点N的值为的结点M的值。
• 删除结点M。

因为M作为左子树的最大值结点，所以结点的度一定是0或1，所以删除结点的情况就转移为以上两种情况。

图16 删除结点度为2

上面三种情况最后都要判断父结点是否平衡，如果不平衡，则通过旋转使其平衡。

代码实现

【数据结构】

typedef struct _AVLNode{  int data;  int height;  struct _AVLNode* lchild;  struct _AVLNode* rchild;}AVLNode, *AVLTree;

【树的高度】

int Height(AVLTree Tree){  return nullptr == Tree ? 0 : Tree->height;}

【平衡因子】

int GetBalance(AVLTree Tree){  return (nullptr == Tree) ? 0 : (Height(Tree->lchild) - Height(Tree->rchild));}

【查找最小值】

AVLTree FindMin(AVLTree Tree){  if (nullptr == Tree)  {    return nullptr;  }  else if (nullptr == Tree->lchild)  {    return Tree;  }  else  {    return FindMin(Tree->lchild);  }}

【查找最大值】

AVLTree FindMax(AVLTree Tree){  if (nullptr == Tree)  {    return nullptr;  }  else if (nullptr == Tree->rchild)  {    return Tree;  }  else  {    return FindMax(Tree->rchild);  }}

【LL型】

/*右旋*/AVLTree LL_Rotate(AVLTree Tree){  if (nullptr == Tree) return nullptr;  AVLTree Root = Tree->lchild;  Tree->lchild = Root->rchild;  Root->rchild = Tree;   Tree->height = std::max(Height(Tree->lchild), Height(Tree->rchild)) + 1;  Root->height = std::max(Height(Root->lchild), Height(Root->rchild)) + 1;  return Root;}

【RR型】

/*左旋*/AVLTree RR_Rotate(AVLTree Tree){  if (nullptr == Tree) return nullptr;  AVLTree Root = Tree->rchild;  Tree->rchild = Root->lchild;  Root->lchild = Tree;  Tree->height = std::max(Height(Tree->lchild), Height(Tree->rchild)) + 1;  Root->height = std::max(Height(Root->lchild), Height(Tree->rchild)) + 1;  return Root;}

【LR型】

AVLTree LR_Rotate(AVLTree Tree){  if (nullptr == Tree) return nullptr;  Tree->lchild = RR_Rotate(Tree->lchild);  return LL_Rotate(Tree);}

【RL型】

AVLTree RL_Rotate(AVLTree Tree){  if (nullptr == Tree) return nullptr;  Tree->rchild = LL_Rotate(Tree->rchild);  return RR_Rotate(Tree);}

【插入结点】

AVLTree Insert(AVLTree Tree, int key){  if (nullptr == Tree)  {    Tree = (AVLNode*)malloc(sizeof(AVLNode));    Tree->data = key;    Tree->lchild = nullptr;    Tree->rchild = nullptr;    Tree->height = 1;    return Tree;  }  if (Tree->data > key)  {    Tree->lchild = Insert(Tree->lchild, key);  }  else if (Tree->data < key)  {    Tree->rchild = Insert(Tree->rchild, key);  }  else  {    return Tree;  }  Tree->height = std::max(Height(Tree->lchild), Height(Tree->rchild)) + 1;  int balance = GetBalance(Tree);  if (balance > 1 && key < Tree->lchild->data) /*LL型*/  {    return LL_Rotate(Tree);  }  else if (balance < -1 && key > Tree->rchild->data) /*RR型*/  {    return RR_Rotate(Tree);  }  else if (balance > 1 && key > Tree->lchild->data) /*LR型*/  {    return LR_Rotate(Tree);  }  else if (balance < -1 && key < Tree->rchild->data) /*RL型*/  {    return RL_Rotate(Tree);  }  return Tree;}

【删除结点】

AVLTree Delete(AVLTree Tree, int key){  if (nullptr == Tree)  {    return nullptr;  }  if (Tree->data > key)  {    Tree->lchild = Delete(Tree->lchild, key);  }  else if (Tree->data < key)  {    Tree->rchild = Delete(Tree->rchild, key);  }  else  {    if (nullptr != Tree->lchild && nullptr != Tree->rchild)    {      AVLTree Max = FindMax(Tree->lchild);      Tree->data = Max->data;      Tree->lchild = Delete(Tree->lchild, Max->data);    }    else if (nullptr == Tree->lchild && nullptr != Tree->rchild)    {      AVLNode* Node = Tree;      Tree = Tree->rchild;      free(Node);    }    else if (nullptr != Tree->lchild && nullptr == Tree->rchild)    {      AVLNode* Node = Tree;      Tree = Tree->lchild;      free(Node);    }    else    {      free(Tree);      Tree = nullptr;      return Tree;    }  }  Tree->height = std::max(Height(Tree->lchild), Height(Tree->rchild)) + 1;  int balance = GetBalance(Tree);  if (balance > 1 && GetBalance(Tree->lchild) >= 0) /*LL型*/  {    return LL_Rotate(Tree);  }  else if (balance < -1 && GetBalance(Tree->rchild) <= 0) /*RR*/  {    return RR_Rotate(Tree);  }  else if (balance > 1 && GetBalance(Tree->lchild) < 0) /*LR型*/  {    return LR_Rotate(Tree);  }  else if (balance < -1 && GetBalance(Tree->rchild) > 0) /*RL型*/  {    return RL_Rotate(Tree);  }  return Tree;}

【前序遍历】

void PreOrderTraverse(AVLTree Tree){  if (Tree)  {    std::cout << Tree->data << " ";    PreOrderTraverse(Tree->lchild);    PreOrderTraverse(Tree->rchild);  }}

【测试程序】

int main(){  AVLTree Tree = NULL;  Tree = Insert(Tree, 9);  Tree = Insert(Tree, 5);  Tree = Insert(Tree, 10);  Tree = Insert(Tree, 3);  Tree = Insert(Tree, 6);  Tree = Insert(Tree, 11);  Tree = Insert(Tree, 1);  Tree = Insert(Tree, 2);  Tree = Insert(Tree, 4);  Tree = Insert(Tree, 12);  Tree = Insert(Tree, 13);  std::cout << "前序遍历" << std::endl;  PreOrderTraverse(Tree);  std::cout << std::endl;  Tree = Delete(Tree, 10);  std::cout << "前序遍历" << std::endl;  PreOrderTraverse(Tree);  std::cout << std::endl;  return 0;}

插入所有结点，生成的平衡二叉树为：

图17 构建的平衡二叉树

运行结果：

图18 平衡二叉树创建和删除

【完整代码】

Github:

https://github.com/MrYuxiangZhu/DataStructure/tree/master/06.%20Tree