# 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 树可视化网站](https://www.cs.usfca.edu/~galles/visualization/AVLtree.html)，可以看到插入/删除等操作的动态过程。

## AVL 树 vs 红黑树

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

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

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

* [read this](https://www.codesdope.com/course/data-structures-avl-trees/)