DSA - AVL 树

概念

AVL 树是一棵平衡的二叉搜索树(BST)，也就是升级版就的 BST。它的定义范围比 BST 小，AVL 树同时也是 BST，而 BST 不一定是 AVL 树。

AVL 树是由发明者的名字命名的，这个名字奇怪得一点都不奇怪。

AVL 树与一般 BST 的区别就是，它是平衡的，即左右子树的高度差不大于 1，且对于二叉树中的每个节点，这句话都是对的。

为了方便，AVL 树把左右子树的高度差存在了节点上，叫做平衡因子，平衡因子 = 左子树高度 - 右子树高度。如果平衡因子是除了 -1，0，1 之外的数字，说明以该节点为根节点的子树已经失去了平衡。

为什么平衡很重要呢

对于 BST，理想的查找/插入/删除操作的时间是 $O(logN)$ (N 是节点数)，但如果二叉树退化到链表，操作时间就变成了 $O(N)$，AVL 树就是为了避免这种情况而存在的。AVL 树的查找/插入/删除时间一直是 $O(logN)$，为了保持这个时间，我们需要在进行插入/删除操作之后，再进行某项操作来维持 AVL 树的平衡，即将它的高度维持为 $logN$。

操作

插入

插入就和 BST 的插入操作是一样的，不过插入之后，需要原路返回找到第一个失去平衡的节点，对它进行旋转操作。只需要对以这个节点为根节点的子树进行旋转操作，整棵 AVL 树就会重新回归平衡。

要找到失去平衡的子树，需要判断节点的平衡因子。插入新节点后，一些节点平衡因子会改变，因此需要在插入新节点后，原路返回更新节点的平衡因子。

如果使用循环的方法插入新节点，那么在 AVL 树节点的设计上，还需要增加一个 parent 指针指向父节点，才能实现原路返回；如果使用递归的方法来插入新节点，递归本身就有一个原路返回的过程，所以 parent 指针也不需要了。

旋转

旋转就是用来维持 AVL 树平衡的操作。

假设 x 是进行插入操作后失去平衡的子树的根节点，那么在插入新节点时总共有 4 种可能发生的情况：

x 是插入新节点后原路返回时遇到的第一个失去平衡的节点，我们只需要关注这个节点。

1. LL: 新节点作为 x 的左子节点的左子节点插入

2. RR: 新节点作为 x 的右子节点的右子节点插入

3. LR: 新节点作为 x 的左子节点的右子节点插入

4. RL: 新节点作为 x 的右子节点的左子节点插入

对于这 4 种情况分别有不同的旋转策略：

1. LL: 对 x 做右旋操作

2. RR: 对 x 做左旋操作

3. LR: 对 x 的左子节点做左旋操作，再对 x 做右旋操作

4. RL: 对 x 的右子节点做右旋操作，再对 x 做左旋操作

这些策略就像魔方公式一样，记住就行。当然有兴趣也可以去看证明过程，我是暂时没这个兴趣啦。

如何判断插入是哪种情况：

TODO

删除

TODO

代码

TODO

复杂度

操作	时间	空间
插入	$O(logn)$	$O(1)$
删除	$O(logn)$	$O(1)$
旋转	$O(1)$	$O(1)$

可视化

一个 AVL 树可视化网站，可以看到插入/删除等操作的动态过程。

AVL 树 vs 红黑树

AVL 树一般会拿来跟红黑树比较，两者都是平衡的二叉搜索树，不过它们采取不同的策略来保持树的平衡。AVL 树比红黑树平衡度更高，不过插入/删除操作后的需要的旋转操作也可能更多。

如果是查找操作居多，插入/删除操作较小，可以优先考虑 AVL 树。

如果插入/删除操作居多，应该优先考虑红黑树。

• read this