AVL 树的定义

AVL 树是一种自平衡的二叉搜索树，它满足如下性质：

• 任意节点的平衡因子的绝对值不大于 1
  • 平衡因子 = 左子树高度 - 右子树高度

AVL 树的插入

当向 AVL 树中插入关键字时，AVL 树会新增一个叶子节点，因此可能导致某些节点失衡，AVL 树通过旋转失衡点，使二叉树重新保持平衡。

向 AVL 树中插入节点的逻辑是：从插入点开始，向上寻找失衡点，如果没有节点失衡，则插入结束；否则，围绕第一个失衡点进行旋转，因为在旋转前后，子树的高度不变，所以无需再向上回溯。

关于 AVL 树的旋转请参考：AVL 树的旋转。

简而言之：

• 对于 LL 型：以失衡点的左孩子为轴，将失衡点右旋
• 对于 RR 型：以失衡点的右孩子为轴，将失衡点左旋
• 对于 LR 型：先以失衡点的左孩子的右孩子为轴，将其左孩子左旋，得到 LL 型；再按照 LL 型进行旋转
• 对于 RL 型：先以失衡点的右孩子的左孩子为轴，将其右孩子右旋，得到 RR 型；再按照 RR 型进行旋转

下面是判断属于何种旋转类型的方法：

• 找到第一个失衡点
• 如果失衡点及其左孩子的平衡因子都大于 0，则属于 LL 型
• 如果失衡点的平衡因子大于 0，并且其左孩子节点的平衡因子小于 0，则属于 LR 型
• 如果失衡点及其右孩子的平衡因子都小于 0，则属于 RR 型
• 否则，属于 RL 型

下面是寻找第一个失衡点的方法：

从插入点的父节点开始，朝着根节点方向前进，依次调整所经过的节点的平衡因子：

• 如果调整的过程中，发现新插入的节点不会导致以当前节点为根的子树的高度增加，则停止回溯
• 如果调整的过程中，发现新插入的节点导致当前节点失衡，则当前节点就是要寻找的第一个失衡点

AVL 树的删除

二叉搜索树删除节点的本质是：使用待删除节点的左子树的最右节点（或右子树的最左节点）的关键字替换待删除节点的关键字，然后再将左子树的最右节点（或右子树的最左节点）删掉。

在 AVL 树中，删除节点时，如果导致某些节点失衡，那么需要进行旋转。因为旋转之后，子树的高度可能比删除节点之前的高度小 1，所以在旋转后，可能需要继续向根节点方向回溯。

下面是，删除节点时，导致失衡的四种情形：

• LL 型
• LR 型
• RR 型
• RL 型

Python 实现

tim-chow 的 Github