所谓平衡二叉树是指（什么是平衡二叉树）

作者 |小灰

来源 | 程序员小灰

————— 第二天 —————

————————————

在红黑树当中，我们通过红色结点和黑色结点作为辅助，来判断一颗二叉树是否相对平衡。

而在AVL树当中，我们通过“平衡因子”来判断一颗二叉树是否符合高度平衡。

到底什么是AVL树的平衡因子呢？

对于AVL树的每一个结点，平衡因子是它的左子树高度和右子树高度的差值。只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候，这颗二叉树才是一颗合格的AVL树。

举个例子，下图就是一颗典型的AVL树，每个节点旁边都标注了平衡因子：

其中结点4的左子树高度是1，右子树不存在，所以该结点的平衡因子是1-0=1。

结点7的左子树不存在，右子树高度是1，所以平衡因子是0-1=-1。

所有的叶子结点，不存在左右子树，所以平衡因子都是0。

上图原本是一个平衡的AVL树，当插入了新结点1时，父结点2的平衡因子变成了1，祖父结点4的平衡因子变成了2。

此时，结点4的左右子树高度差超过了1，打破了AVL树的平衡。

那么，怎样才能重新恢复AVL的平衡呢？

之前讲解红黑树的时候，我们提到红黑树包括左旋转、右旋转、变色这三种操作。

而AVL树不存在变色的问题，只有左旋转、右旋转这两种操作。左旋转：逆时针旋转AVL树的两个结点X和Y，使得父结点被自己的右孩子取代，而自己成为自己的左孩子。说起来有些绕，见下图（标号1,2,3的三角形，是结点X和Y的子树）：

图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。

右旋转：顺时针旋转AVL树的两个结点X和Y，使得父结点被自己的左孩子取代，而自己成为自己的右孩子。见下图：

图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。

左左局面（LL）

顾名思义，祖父结点A有一个左孩子结点B，而结点B又有一个左孩子结点C。标号1,2,3,4的三角形是各个结点的子树。

在这种局面下，我们以结点A为轴，进行右旋操作：

右右局面（RR）

祖父结点A有一个右孩子结点B，而结点B又有一个右孩子结点C。

在这种局面下，我们以结点A为轴，进行左旋操作：

左右局面（LR）

祖父结点A有一个左孩子结点B，而结点B又有一个右孩子结点C。

在这种局面下，我们先以结点B为轴，进行左旋操作：

这样就转化成了左左局面。我们继续以结点A为轴，进行右旋操作：

右左局面（RL）

祖父结点A有一个右孩子结点B，而结点B又有一个左孩子结点C。

在这种局面下，我们先以结点B为轴，进行右旋操作：

这样就转化成了右右局面。我们继续以结点A为轴，进行左旋操作：

例子中，以结点4为根的子树出现了不平衡的情况。

不难看出，这个子树正好符合 “左左局面”。

于是，我们以结点4为轴，进行右旋操作：

这样一来，这颗AVL树重新恢复了高度平衡。

如上图所示，在AVL树中删除了结点1，导致父节点2的平衡因子变为-2，打破了平衡。

此时，以结点2为根的子树正好形成了“右左局面”，于是我们首先以结点4为轴进行右旋：

然后以结点2为轴进行左旋：

如此一来，AVL树重新恢复了高度平衡。

☞华为开会有“原则”？企业的成功都从会议开始

☞微信、支付宝否认提供「锁定 35 万人」数据；苹果押宝中国 5G 市场；TiDB 4.0.1 发布 | 极客头条

☞程序员晒端午福利，网友：看了你的福利我想摔手机

☞如何成为一名黑客？

☞发送0.55 ETH花费近260万美元！这笔神秘交易引发大猜想

☞京东姚霆：推理能力，正是多模态技术未来亟需突破的瓶颈！

,