AVL

AVL 基础知识可以查看：

• 常用算法25讲-15 | AVL树：如何让二叉排序树永远保持最优？
• 玩转数据结构 - 平衡树和 AVL

AVL 是一种平衡二叉树，它对平衡二叉树的定义：对于任意节点，左子树和右子树的高度差不能超过1。

AVL 是 BST，可以看做是 BST 的增强版，因此相对 BST 会多出以下概念：

• 平衡因子
• 平衡操作：单旋、双旋

在AVL树中插入或移除节点和BST完全相同。然而，AVL树的不同之处在于我们需要检验它的平衡因子，如果有需要，会将其逻辑应用于树的自平衡。

平衡因子的计算

当前节点的平衡因子 = 该节点右子树高 - 该节点左子树高

• 节点3的平衡因子为 2 - 0 = 2，表示右侧子树导致失衡
• 节点2的平衡因子 0 - 0 = 0，表示左右侧平衡
• 节点6的平衡因子 0 - 1 = 1，表示右侧较重
• 节点5的平衡因子 -1 - 0 = -1，表示左侧较重
• 节点4的平衡因子 -1 - (-1) = 0，表示左右平衡
• 节点7的平衡因子 -1 - (-1) = 0，表示左右平衡

旋转

LL

这种情况出现在节点的左侧子节点高于右侧子节点的高度。且左侧子节点为平衡状态或者左侧较重的状态。进行下面的旋转操作能够使得树恢复平衡：

LL 的过程：

1. 左侧子节点的右侧子节点指向当前节点。
2. 当前节点的左侧子节点指向左侧子节点的原右侧子节点。

RR

这种情况出现在节点的右侧子节点高于左侧子节点的高度。且右侧子节点处于平衡状态或者右侧较重的状态。进行下面的旋转操作能够使得树恢复平衡：

RR 的过程：

1. 右侧子节点的左侧子节点指向当前节点。
2. 当前节点的右侧子节点指向右侧子节点的原左侧子节点。

LR

这种情况出现于左侧子节点的高度大于右侧子节点的高度，并且左侧子节点右侧较重。在这种情况下，我们可以对左侧子节点进行左旋转来修复，这样会形成左-左的情况，然后再对不平衡的节点进行一个右旋转来修复，如下图所示。