在二叉搜索树章节中，我们提到了在多次插入和删除操作后，二叉搜索树可能退化为链表。这种情况下，所有操作的时间复杂度将从

$O(\log n)$ 恶化为

$O(n)$。

如下图所示，经过两次删除节点操作，这个二叉搜索树便会退化为链表。

再例如，在以下完美二叉树中插入两个节点后，树将严重向左倾斜，查找操作的时间复杂度也随之恶化。

G. M. Adelson-Velsky 和 E. M. Landis 在其 1962 年发表的论文 "An algorithm for the organization of information" 中提出了「AVL 树」。论文中详细描述了一系列操作，确保在持续添加和删除节点后，AVL 树不会退化，从而使得各种操作的时间复杂度保持在

$O(\log n)$ 级别。换句话说，在需要频繁进行增删查改操作的场景中，AVL 树能始终保持高效的数据操作性能，具有很好的应用价值。

二叉搜索树的「平衡」概念是指：平衡因子，也就是每一个结点的左子树和右子树高度差的绝对值最多为 1。当平衡因子大于 1 时，代表这颗 BST 失衡。

如下图所示，通过中序遍历，找到二叉树首个失衡节点是“节点 5”。旋转操作是多数平衡树能够维持平衡的关键，它能在不改变一棵合法 BST 中序遍历结果的情况下改变局部节点的深度。对于这棵失衡的 BST ，对"失衡节点 5" 进行右旋操作，就能使 BST 恢复平衡：

旋转操作包括左旋和右旋，上面的过程为右旋，前置条件是失衡节点的左子树高度大于右子树高度。如果以失衡节点作为子树的 Root 看，操作涉及到失衡节点 5，LChild 节点 3 和 RGrandChild 节点 4。
将节点 5 右旋的过程如下：

1. 以节点 5 作为当前子树的 Root
2. 将节点 5 作为节点 3 的 RChild
3. 将节点 4 作为节点 5 的 LChild
4. 将节点 3 作为当前子树的 Root

左旋可以视作右旋操作的镜像，前置条件是失衡节点的右子树高度大于左子树高度。以下图为例，涉及到失衡节点 1，RChild 节点 4 和 LGrandChild 节点 3：

对节点 1 的右旋过程如下：

1. 以节点 1 作为当前子树的 Root
2. 将节点 1 作为节点 4 的 LChild
3. 将节点 3 作为节点 1 的 RChild
4. 将节点 4 作为当前子树的 Root