AVL 树是一种自动平衡二叉搜索树,其任意左右子节点,高度差总是 0 或 1。AVL 的核心知识点在于平衡调整。

插入、查找

和普通 BST 是一样的。

删除、平衡调整

首先进行普通删除。然后进行平衡调整

何时调整?

高度不平衡时,$\alpha$ 结点的子树高度差为 2. 有四种情况产生它:

对 $\alpha$ 的左儿子左子树进行一次插入。 对 $\alpha$ 的左儿子右子树进行一次插入。 对 $\alpha$ 的右儿子左子树进行一次插入。 对 $\alpha$ 的右儿子右子树进行一次插入。

前两种和后两种是对称的。可以分为两种基本情形:

  1. 外侧插入。即左 - 左,或者 右 - 右。此种情况,单旋转后平衡。
  2. 内侧插入。即左 - 右,或者 右 - 左。此种情况,双旋转后平衡。

动画截取自 维基百科

单旋转

单旋转(左旋):

left_rotate

单旋转(右旋):

right_rotate

让我们用一个例子加深理解:

image-20211130211856453

如图,插入 6 之后,8 的左子树高度为 2,右子树高度为 0. leftHeight > rightHeight,因此进行右旋。将 7 提到右上方 8 的未知取而代之,8 下降到右下方作为 7 的子树。

双旋转

双旋转:

right_left_rotate

例子:

image-20211130212507439

如图,插入 15 之后,实际上经过了如下两步:

image-20211130213137661

  1. 将 16 绕 15 旋转到右下方。
  2. 将 7 绕 15 旋转到左下方。

原理就是这样了,不会有面试官要考背出代码实现吧,不会吧不会吧(