平衡二叉树（AVL 树）

平衡二叉树通常指 AVL 树（Adelson-Velsky and Landis Tree）。
它在二叉搜索树（BST）的基础上限制树高，使查找、插入和删除保持 $O(\log n)$ 的时间复杂度。

为什么需要平衡

BST 满足：任意节点的左子树中的值小于该节点，右子树中的值大于该节点，左右子树也都是 BST。
但 BST 不保证高度。若依次插入 1、2、3、4、5，可能得到：

1
 \
  2
   \
    3
     \
      4
       \
        5

此时树退化为链表，查找最坏需要 $O(n)$；保持较低树高则可以避免这种情况。

AVL 树与平衡因子

AVL 树首先是 BST，并且任意节点的左右子树高度差不超过 1。平衡因子（Balance Factor，BF）通常定义为：

因此，AVL 树中每个节点的 BF 都属于 $\{-1,0,1\}$。BF 为 1 表示左子树高一层，为 -1 表示右子树高一层；$|BF|>1$ 则表示失衡。

例如，下面的树中，节点 5 的左右子树高度分别为 2 和 1，故 $BF(5)=1$，整棵树仍然平衡：

    5
   / \
  3   8
 /
2

插入后的四种旋转

插入新节点后，从新节点向上检查祖先。若某个节点失衡，就根据从该节点走向新节点的前两步判断类型。这四种情况一定要理解：

LL 与 RR：单旋

依次插入 30、20、10，新节点位于 30 的“左 → 左”方向，对 30 右旋：

    30             20
   /              /  \
  20      →      10   30
 /
10

RR 与之对称：依次插入 10、20、30，对失衡节点 10 左旋：

10                20
  \              /  \
   20     →     10   30
     \
      30

LR 与 RL：双旋

依次插入 30、10、20，新节点位于“左 → 右”方向。先对 30 的左孩子 10 左旋，再对 30 右旋：

    30           30           20
   /            /            /  \
  10     →     20     →     10   30
    \          /
     20       10

RL 与之对称：依次插入 10、30、20，先对 10 的右孩子 30 右旋，再对 10 左旋：

10           10                20
  \            \              /  \
   30    →      20      →     10   30
  /              \
 20               30

记忆： LL → 右旋，RR → 左旋；LR → 先左旋再右旋，RL → 先右旋再左旋。

删除与时间复杂度

删除时先按 BST 的规则处理，再从删除位置向上检查平衡。例如，下面的树原本平衡；删除 40 后，节点 30 的左右子树高度变为 2 和 0，因 $BF(30)=2$ 而失衡：

    30             30
   /  \           /
  20  40   →     20
 /               /
10              10

此时仍通过旋转恢复平衡。插入后通常调整最近的失衡祖先即可；删除可能使更高层继续失衡，需要逐层向上检查和调整。

AVL 树的高度为 $O(\log n)$，所以查找、插入和删除的时间复杂度均为 $O(\log n)$。代价是插入、删除时需要维护平衡，适合查找频繁的场景。

与 BST、完全二叉树的区别

AVL 树一定是 BST，BST 不一定是 AVL 树。 完全二叉树描述的是形状；是否满足 BST 的大小关系，还要另外判断。

感觉今天还是有点不舒服，头有点晕。
这么看来需要注意身体了。