在“二叉搜索树”章节提到，在多次插入和删除操作后，二叉搜索树可能退化为链表。在这种情况下，所有操作的时间复杂度将从O(logn)劣化为O(n)。

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

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

1962 年 G. M. Adelson‑Velsky 和 E. M. Landis 在 论 文 “An algorithm for the organization of information”中提出了 AVL 树。AVL树能够确保在持续添加和删除节点后不会退化，从而使得各种操作的时间复杂度保持在O(logn)级别。

AVL树既是二叉搜索树，也是平衡二叉树，同时满足这两类二叉树的所有性质，因此是一种平衡二叉搜索树（balanced binary search tree）。

由于AVL树的相关操作需要获取节点高度，因此我们需要为节点类添加变量：

“节点高度”是指从该节点到它的最远叶节点的距离，即所经过的“边”的数量。需要特别注意的是，叶节点的高度为0，而空节点的高度为-1。我们将创建两个工具函数，分别用于获取和更新节点的高度：

节点的平衡因子（balance factor）定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为0。我们同样将获取节点平衡因子的功能封装成函数，方便后续使用：

设平衡因子为f，则一棵AVL树的任意节点的平衡因子都满足 -1 < = f <= 1。

AVL树的特点在于“旋转”操作，它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新回复平衡。换句话说，**旋转操作既能保持“二叉搜索树”的性质，也能使树重新变成“平衡二叉树”。

我们将平衡因子绝对值 > 1 的节点称为“失衡节点”。根据节点失衡的情况不同，旋转操作分为四种：右旋、左旋、先右旋后左旋、先左旋后右旋。

如图所示，节点下方为平衡因子。从底往顶看，二叉树中首个失衡节点时“节点3”。我们关注以该失衡节点为根节点的子树，将该节点记为，其左子节点记为，执行“右旋操作”。完成右旋后，子树恢复平衡，并且仍然保持二叉搜索树的性质。

另外当节点有右子节点时（记为），需要在右旋中添加一步：将作为的左子结点。

“右旋”是一种形象化的说法，实际上需要通过修改节点指针来实现。

观察发现，左旋和右旋操作在逻辑上是镜像对称的，它们分别解决的两种失衡情况也是对称的。基于对称性，我们只需要将右旋代码啊的所有替换为，将所有的替换为，即可得到左旋的实现代码：

对于上述失衡二叉树的镜像情况，需要先对执行“右旋”，再对执行“左旋”操作。

下面展示了四种失衡情况与上述案例逐个对应，分别需要采用右旋、先左旋后右旋、先右旋后左旋、左旋的操作。

如下表所示，我们通过判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号，来确定失衡节点属于那种情况

为便于使用，我们将旋转操作封装成一个函数。有了这个函数，我们就能对各种失衡情况进行旋转，使失衡节点重新恢复平衡。

AVL树的节点插入操作与二叉搜索树在主体上类似。唯一的区别在于，在AVL树中插入节点后，从该节点到根节点的路径上可能会出现一系列失衡节点。因此，我们需要从这个节点开始，自底向上执行旋转操作，使其所有失衡节点恢复平衡。

类似地，在二叉搜索树的删除节点方法的基础上，需要从底至顶执行旋转操作，使所有失衡节点恢复平衡。