定义

1. 平衡因子 = 左子树高度 - 右子树高度
2. 平衡二叉树 = 每个节点左右子树高度差不超过 $1$

操作

• 旋转

  • 左旋
    1. let R = self.r
    2. self.r = R.l
    3. R.l = self
  • 右旋
    1. let L = self.l
    2. self.l = L.r
    3. L.r = self
  • 平衡二叉树 旋转の图示 📅 2025-12-24

• 增

  1. 插入节点，same as 二叉排序树
  2. 向上回溯，检测平衡因子
     1. 平衡因子 $0\to\pm1$ $\Rightarrow$ 可能失衡，继续向上检测
     2. 平衡因子 $\pm1\to0$ $\Rightarrow$ 可以停止回溯
     3. 平衡因子 $\pm1 \to \pm2$ $\Rightarrow$ 立即旋转一次，然后停止回溯
        1. LL 旋转
        2. RR 旋转
        3. LR 旋转
        4. RL 旋转

• 删
  1. 删除节点 same as 二叉排序树
  2. 从删除节点向上回溯找到第一个不平衡子节点 $z$ 进行平衡 same as 增
  3. 继续向上回溯直到根节点