漫画：什么是平衡二叉树？

作者|灰色

源|程序员灰色

第二天-

579———————————————

1214161在红色和黑色树中，我们使用红色节点和黑色节点作为辅助来判断二叉树是否相对平衡。

在AVL树中，我们使用“平衡因子”来判断二叉树是否符合高平衡。

AVL树的平衡因子是什么？

对于AVL树的每个节点，平衡因子是其左子树高度和右子树高度之差。只有当二叉树的所有节点的平衡因子为-1、0和1时，二叉树才是合格的AVL树。

例如，下图是一个典型的AVL树，每个节点旁边都有一个平衡因子:

其中节点4的左子树高度为1，右子树不存在，因此该节点的平衡因子为0=1。

节点7的左子树不存在，右子树的高度为1，因此平衡因子为0-1=-1。

所有叶节点都没有左右子树，因此平衡因子为0。

22上图最初是一棵平衡的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成为了他的右边的孩子。这是右旋转。

27左左局势

顾名思义，祖父节点A有一个左子节点B，节点B有一个左子节点C。编号为1、2、3和4的三角形是每个节点的子树。

在这种情况下，我们以节点A为轴，执行右手操作:

3RR

祖父节点A有一个右子节点B，节点B有一个右子节点c

在这种情况下，我们以节点A为轴，执行左手操作:

3左右情况

祖父节点A有一个左子节点B，节点B有一个右子节点c

在这种情况下，我们首先以节点B为轴，执行左手操作:

-36。-这变成了左左的情况。我们继续以节点A为轴，执行右手操作:

3左右位置

祖父节点A有一个右子节点B，节点B有一个左子节点c

在这种情况下，我们首先以节点B为轴，执行右手操作:

-40。-这转化为右手的情况。我们继续将节点A作为左手操作的轴:

42在这个例子中，以节点4为根的子树是不平衡的。

不难看出，这个子树恰好符合“左左情况”。

因此，我们以节点4为轴，执行右手操作:

结果，反车辆地雷树恢复了高度平衡。

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

此时，以节点2为根的子树正好形成一个“左右位置”，所以我们首先以节点4为轴向右转:

然后左转，以节点2为轴:

结果，反车辆地雷树恢复了高度平衡。

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

微信和支付宝否认提供“35万人被锁定”的数据；苹果押注中国5G市场；TiDB 4.0.1宣布|极客头条

程序员享受端午节的福利。网友:看了你的福利后，我想弄坏我的手机

如何成为黑客？

发送0.55以太网花费近260万美元！这桩神秘的交易引发了一场大猜想。

姚婷，京东:推理能力是未来多模态技术需要突破的瓶颈！

本文由 在线网速测试 整理编辑，转载请注明出处，原文链接：https://www.wangsu123.cn/news/7998.html。