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 是插入新节点后原路返回时遇到的第一个失去平衡的节点，我们只需要关注这个节点。
LL: 新节点作为 x 的左子节点的左子节点插入
RR: 新节点作为 x 的右子节点的右子节点插入
LR: 新节点作为 x 的左子节点的右子节点插入
RL: 新节点作为 x 的右子节点的左子节点插入
对于这 4 种情况分别有不同的旋转策略：
LL: 对 x 做右旋操作
RR: 对 x 做左旋操作
LR: 对 x 的左子节点做左旋操作，再对 x 做右旋操作
RL: 对 x 的右子节点做右旋操作，再对 x 做左旋操作
这些策略就像魔方公式一样，记住就行。当然有兴趣也可以去看证明过程，我是暂时没这个兴趣啦。
如何判断插入是哪种情况：
TODO
删除
TODO
代码
TODO
复杂度
可视化
一个 AVL 树可视化网站，可以看到插入/删除等操作的动态过程。
AVL 树 vs 红黑树
AVL 树一般会拿来跟红黑树比较，两者都是平衡的二叉搜索树，不过它们采取不同的策略来保持树的平衡。AVL 树比红黑树平衡度更高，不过插入/删除操作后的需要的旋转操作也可能更多。
如果是查找操作居多，插入/删除操作较小，可以优先考虑 AVL 树。
如果插入/删除操作居多，应该优先考虑红黑树。
Last updated