AVL 树被定义为一种自平衡的二叉搜索树 (BST)，其中对于任意节点，其左右子树的高度差不能超过一。
平衡因子 = 左子树高度 – 右子树高度
对于一棵平衡树（对于每个节点）：-1 ≤ 平衡因子 ≤ 1
AVL 树示例：
不同节点的平衡因子如下：12 为 +1，8 为 +1，18 为 +1，5 为 +1，11 为 0，17 为 0 以及 4 为 0。由于所有差值都位于 -1 到 +1 之间，因此这棵树是一棵 AVL 树。
非 AVL 树的 BST 示例：
下面的树不是一棵 AVL 树，因为节点 8 和 12 的平衡因子大于 1。
关于 AVL 树的要点：
- 旋转：旋转旨在以 O(1) 的时间恢复平衡，同时确保整体时间复杂度保持在 O(log n)。AVL 树使用四种情况在插入和删除后重新平衡自身：左左、右右、左右 和 右左
- 插入和删除：插入操作后需要进行自底向上的遍历以检查平衡并应用旋转，而删除操作可能会更复杂，因为可能需要进行多次旋转。在删除过程中，AVL 树可能需要多个重新平衡步骤，而红黑树在这方面则限制得更好。
- 用例：当我们需要频繁且高效的查找时，AVL 树特别有用，例如在数据库索引、内存密集型应用程序，或者在可预测的时间复杂度至关重要的场景中。
- 与其他树相比的缺点：虽然 AVL 树的查找速度比红黑树快，但由于平衡要求更严格，它在插入和删除时可能会产生略多的开销。因此，红黑树在标准库中更为常见，例如 Java 中的 INLINECODE4a762cbb 或 INLINECODEc3b25544，以及 C++ STL 中的
map。 - 中序遍历：对 AVL 树进行中序遍历仍然会按排序顺序返回元素，就像任何二叉搜索树一样。
AVL 树上的操作：
- 查找：这与普通的二叉搜索树 (BST) 相同，因为 AVL 树始终是一棵 BST。所以我们可以使用与 BST 相同的实现。这里的优势在于时间复杂度是 O(log n)
- 插入：它结合普通的 BST 插入执行旋转，以确保插入后受影响节点的平衡因子小于或等于 1
- 删除：它也结合普通的 BST 删除执行旋转，以确保删除后受影响节点的平衡因子小于或等于 1。
旋转子树（用于插入和删除）
AVL 树可以通过以下四种方式之一进行旋转，以在维护 BST 属性的同时保持自身平衡。
#### 1. 左左案例:
- 当一个节点被插入到左孩子的左子树时发生，导致平衡因子变得大于 +1。
- 修复：执行单次右旋转。
2. 右右案例:
- 当一个节点被插入到右孩子的右子树时发生，使平衡因子小于 -1。
- 修复：执行单次左旋转。
#### 3. 左右案例:
- 发生情况：当一个节点被插入到左孩子的右子树时，这破坏了某个祖先节点的平衡因子，使其变得左重。
- 修复：先对左孩子执行左旋转，然后对节点本身执行右旋转。
4. 右左案例:
- 发生情况：当一个节点被插入到右孩子的左子树时，这破坏了某个祖先节点的平衡因子，使其变得右重。
- 修复：先对右孩子执行右旋转，然后对节点本身执行左旋转。
AVL 树的应用：
- AVL 树通常作为讲授数据结构时自平衡 BST 的首选示例，因为相比红黑树，它更容易理解和实现。
- 适用于那些插入和删除较少，但需要频繁进行数据查找以及其他 BST 操作（如有序遍历、下取整、上取整、最大值和最小值）的应用场景。
- 红黑树在语言库中的实现更为常见，例如 C++ 中的 map，C++ 中的 set，Java 中的 TreeMap 等。