AVL 自平衡二叉树

1. 核心定义：什么是平衡？

在普通的二叉搜索树（BST）中，如果按顺序插入 1, 2, 3, 4，它会退化成一个链表，查询效率从 $O(\log N)$ 掉到 $O(N)$。

AVL 树通过**平衡因子（Balance Factor, BF）**来强制约束：

$\text{BF}=\text{Height}(\text{Left Subtree})-\text{Height}(\text{Right Subtree})$

约束条件： 每一个节点的 $|\text{BF}|$ 必须 $\le 1$（即只能是 $-1,0,1$）。一旦出现 $2$ 或 $-2$，立刻触发“旋转”逻辑进行修复。

---

2. 四种旋转

当一个新节点插入导致失衡时，我们需要通过旋转来降低高子树的高度。

失衡类型	表现（从失衡节点往下看）	修复手段	旋转本质
LL 型	左孩子的左边太重	单向右旋	把左孩子拉上来当爹，旧爹变右孩子
RR 型	右孩子的右边太重	单向左旋	把右孩子拉上来当爹，旧爹变左孩子
LR 型	左孩子的右边太重	先左后右	先对左孩子左旋变 LL，再对根右旋
RL 型	右孩子的左边太重	先右后左	先对右孩子右旋变 RR，再对根左旋

3. 删除

首先按照普通二叉搜索树的规则找到并删除节点：

• 若是叶子节点：直接删除。

• 若只有一个孩子：用孩子节点替代当前节点。

• 若有两个孩子：

  1. 找到该节点的中序后继（右子树中最小的节点）或中序前驱（左子树中最大的节点）。

  2. 用后继（或前驱）的值覆盖当前节点。

  3. 转而删除那个后继（或前驱）节点（此时问题转化为前两种简单情况）。