AVL树（平衡二叉搜索树）

AVL树是一种自平衡的二叉搜索树，由Adelson-Velsky和Landis在1962年提出。它的核心特性是：对于树中的任意节点，其左子树和右子树的高度差（平衡因子）绝对值不超过1。这个约束条件确保了树的高度始终保持在O(log n)级别，从而保证了查找、插入和删除操作的时间复杂度都是O(log n)。

1. 核心概念：平衡因子

平衡因子是AVL树平衡判断的关键指标。对于任意一个节点，其平衡因子定义为：
平衡因子 = 左子树高度 - 右子树高度
根据AVL树的定义，有效的平衡因子只能是 -1、0 或 1。如果某个节点的平衡因子绝对值大于1，则该节点为"失衡节点"，整棵树就失去了平衡，需要通过"旋转"操作来恢复平衡。

2. 节点结构

AVL树的节点通常包含以下几个字段：

• key 或 value：节点存储的数据。
• left：指向左子节点的指针。
• right：指向右子节点的指针。
• height：该节点的高度。节点的高度定义为从该节点到其最远叶子节点的路径上包含的边的数量（或者节点数，定义需统一，这里采用边数）。叶子节点的高度通常定义为0，空节点的高度定义为-1。

3. 平衡操作：旋转

当插入或删除一个节点后，可能会从插入/删除点开始向上回溯，找到第一个平衡因子变为2或-2的祖先节点，这个节点就是失衡节点。针对不同的失衡情况，有四种旋转操作：

• 情况1：左左情况（LL）

  • 描述：在失衡节点的左子树的左子树上插入新节点，导致失衡节点的平衡因子变为2，并且其左子节点的平衡因子为1或0（通常为1）。
  • 操作：右旋（Right Rotation）
    1. 将失衡节点（设为A）的左子节点（设为B）提升为新的根节点（新的子树根）。
    2. 将节点B原来的右子树（设为T2）作为节点A的新左子树。
    3. 将节点A作为节点B的新右子树。
  • 效果：旋转后，树恢复平衡，并且保持了二叉搜索树的性质。

• 情况2：右右情况（RR）

  • 描述：在失衡节点的右子树的右子树上插入新节点，导致失衡节点的平衡因子变为-2，并且其右子节点的平衡因子为-1或0（通常为-1）。
  • 操作：左旋（Left Rotation）
    1. 将失衡节点（设为A）的右子节点（设为C）提升为新的根节点。
    2. 将节点C原来的左子树（设为T2）作为节点A的新右子树。
    3. 将节点A作为节点C的新左子树。
  • 效果：旋转后，树恢复平衡。

• 情况3：左右情况（LR）

  • 描述：在失衡节点的左子树的右子树上插入新节点，导致失衡节点的平衡因子变为2，并且其左子节点的平衡因子为-1。
  • 操作：先左旋后右旋
    1. 先对失衡节点的左子节点（B）进行一次左旋，将情况转化为熟悉的LL情况。这次左旋是针对B和它的右子节点（C）进行的。
    2. 再对失衡节点（A）进行一次右旋。这样就恢复了平衡。

• 情况4：右左情况（RL）

  • 描述：在失衡节点的右子树的左子树上插入新节点，导致失衡节点的平衡因子变为-2，并且其右子节点的平衡因子为1。
  • 操作：先右旋后左旋
    1. 先对失衡节点的右子节点（C）进行一次右旋，将情况转化为熟悉的RR情况。
    2. 再对失衡节点（A）进行一次左旋。

4. 插入操作的全过程

假设我们要将一系列数字插入到一个初始为空的AVL树中，以插入序列 [10, 20, 30, 40, 50, 25] 为例：

1. 插入10：树是空的，直接创建根节点10。节点10的高度为0，平衡因子为0。
2. 插入20：作为10的右子节点。更新节点10的高度为1。节点10的平衡因子 = (左子树高度-1) - (右子树高度0) = (-1) - 0 = -1。平衡，无需旋转。
3. 插入30：作为20的右子节点。
   • 从30开始向上回溯检查平衡因子：
     • 节点20：平衡因子 = 0 - 1 = -1，平衡。
     • 节点10：平衡因子 = (-1) - 1(20的高度) = -2。失衡！
   • 失衡节点是10。情况判断：新节点30在10的右子节点(20)的右子树中，属于RR情况。
   • 执行左旋：
     • 将节点20提升为子树的根。
     • 将20原来的左子树（此时为空）作为10的右子树。
     • 将10作为20的左子树。
   • 旋转后，树的结构变为20为根，10是左子节点，30是右子节点。所有节点平衡因子绝对值<=1，树恢复平衡。
4. 插入40：作为30的右子节点。回溯路径：40->30->20。各节点平衡因子正常，无需旋转。
5. 插入50：作为40的右子节点。
   • 向上回溯：
     • 节点40：平衡因子 = (-1) - 1 = -2？等等，我们需要先计算高度。叶子节点50高度为0。节点40高度为1。节点30：右子树高度为2（40的高度+1），左子树高度为-1（空），平衡因子 = (-1) - 2 = -3？注意：我们回溯到的第一个失衡节点是30（平衡因子为-2）。
   • 失衡节点是30。情况：50在30的右子节点(40)的右子树中，属于RR情况。
   • 执行左旋（以30为根的子树上）：
     • 将40提升为子树根。
     • 将40原来的左子树（空）作为30的右子树。
     • 将30作为40的左子树。
   • 旋转后，局部树结构为40(左:30, 右:50)。检查整棵树，根节点20的平衡因子 = 1(左子树10的高度为0，所以左子树高度为0+1=1) - 2(新子树根40的高度为1，所以右子树高度为1+1=2) = -1。平衡。
6. 插入25：作为20的左子节点10的右子节点？不对，20的左子节点是10，10的右子树为空，所以25应作为10的右子节点。
   • 向上回溯检查：
     • 节点10：平衡因子 = (-1) - 1(25的高度0) = 0？等等，插入25后，10的高度变为1。平衡因子=0。
     • 节点20：平衡因子 = 2(10的高度1+1=2) - 2(40的高度1+1=2) = 0。平衡。
     • 节点40：平衡因子 = 1(30的高度0+1=1) - 1(50的高度0+1=1) = 0。
   • 所有节点平衡，无需旋转。

5. 删除操作简述

删除操作比插入更复杂，因为失衡可能会向上传播到根节点。

1. 执行标准的BST删除操作（分三种情况：删除叶子节点、删除只有一个子节点的节点、删除有两个子节点的节点）。
2. 从被删除节点的父节点开始，向上回溯到根节点，检查路径上每个祖先节点的平衡因子。
3. 如果发现某个祖先节点失衡，则根据上述四种失衡情况（LL, RR, LR, RL）进行相应的旋转操作。
4. 关键点：旋转操作可能会改变子树的高度，因此即使旋转修复了一个失衡节点，仍然需要继续向上回溯检查，直到根节点，因为失衡可能向上传递。

总结
AVL树通过引入平衡因子和旋转操作，强制保持了二叉搜索树的平衡，从而优化了最坏情况下的性能。它的优点是查找效率非常稳定，缺点是插入和删除操作由于需要维护平衡，开销相对更大，旋转操作较多。在实际应用中，如果需要频繁插入和删除，红黑树可能是更常用的选择；如果查询操作远多于更新操作，AVL树是很好的选择。