AVL树（平衡二叉搜索树）

AVL树是一种自平衡二叉搜索树，其核心特性是每个节点的左右子树高度差（平衡因子）不超过1。这种平衡性保证了树的查找、插入和删除操作的时间复杂度均为O(log n)。

1. 平衡因子的定义

平衡因子是节点的左子树高度减去右子树高度的值，计算公式为：

平衡因子 = 左子树高度 - 右子树高度

平衡因子只能为-1、0或1。若超出该范围，则需要通过旋转操作调整树结构。

2. 失衡情况与旋转操作

当插入或删除节点导致平衡因子变为2或-2时，树失衡。失衡分为四种情况：

情况1：左左失衡（LL）

• 特征：当前节点平衡因子为2，其左子节点平衡因子为1。
• 原因：在左子树的左子树插入节点。
• 修复方法：右旋转（以当前节点为轴顺时针旋转）：
  1. 将当前节点的左子节点提升为新根节点。
  2. 原左子节点的右子树变为当前节点的左子树。
  3. 当前节点变为新根节点的右子树。

情况2：右右失衡（RR）

• 特征：当前节点平衡因子为-2，其右子节点平衡因子为-1。
• 原因：在右子树的右子树插入节点。
• 修复方法：左旋转（以当前节点为轴逆时针旋转）：
  1. 将当前节点的右子节点提升为新根节点。
  2. 原右子节点的左子树变为当前节点的右子树。
  3. 当前节点变为新根节点的左子树。

情况3：左右失衡（LR）

• 特征：当前节点平衡因子为2，其左子节点平衡因子为-1。
• 原因：在左子树的右子树插入节点。
• 修复方法：先左旋转后右旋转：
  1. 对当前节点的左子节点执行左旋转（转化为LL情况）。
  2. 对当前节点执行右旋转。

情况4：右左失衡（RL）

• 特征：当前节点平衡因子为-2，其右子节点平衡因子为1。
• 原因：在右子树的左子树插入节点。
• 修复方法：先右旋转后左旋转：
  1. 对当前节点的右子节点执行右旋转（转化为RR情况）。
  2. 对当前节点执行左旋转。

3. AVL树的插入操作步骤

1. 标准BST插入：按照二叉搜索树规则插入新节点。
2. 更新高度：从新节点向上回溯更新每个祖先节点的高度。
3. 检查平衡因子：针对每个祖先节点计算平衡因子：
   • 若平衡因子为±1，继续向上回溯。
   • 若平衡因子为±2，根据上述四种情况执行旋转操作。
4. 调整后终止：旋转后子树高度恢复，无需继续回溯。

4. AVL树的删除操作步骤

1. 标准BST删除：分三种情况（无子节点、有一个子节点、有两个子节点）删除目标节点。
2. 更新高度与平衡：从被删除节点的父节点向上回溯：
   • 更新节点高度。
   • 若平衡因子为±2，执行旋转操作（可能需多次旋转至根节点）。

5. 实例演示（插入操作）

假设依次插入节点[10, 20, 30]：

1. 插入10：树平衡（平衡因子=0）。
2. 插入20：树平衡（10的平衡因子=-1）。
3. 插入30：在10处检测到失衡（平衡因子=-2，属RR情况），对10执行左旋转：
   • 20成为新根节点。
   • 10成为20的左子节点。
   • 树恢复平衡。

6. 时间复杂度分析

• 查找：O(log n)，因树高度始终平衡。
• 插入/删除：O(log n)，包含BST操作和旋转操作（旋转为O(1)）。

通过维护平衡因子和旋转操作，AVL树确保了高效动态数据管理，适用于需要频繁查找的场景（如数据库索引）。