AVL树左旋与右旋结合

概述

AVL树是一种自平衡二叉搜索树，它通过保证任何节点左右子树的高度差不超过1来保持其高度尽可能低。在插入或删除操作后，如果树失去了平衡，则需要进行旋转操作来重新恢复平衡状态。本文将介绍AVL树中的左旋和右旋操作，并结合这两种基本旋转方法解决一些特定情况下的不平衡问题。

AVL树的基本概念

平衡因子

在一个节点中，其左右子树的高度差称为该节点的平衡因子（Balance Factor, BF）。计算公式为： [ \text{BF} = h(\text{右子树}) - h(\text{左子树}) ] 其中 (h) 表示高度。

平衡状态

• 若某节点的平衡因子为0，则该节点是平衡的。
• 若某节点的平衡因子为1或-1，则其左右子树的高度差不超过1，该节点是平衡的。
• 若某节点的平衡因子为2或-2，则需要通过旋转操作使其恢复平衡状态。

左旋与右旋

右旋

右旋（Right Rotation）是对不平衡节点进行的一种调整方式。假设某个节点 (A) 的左子树高度大于其右子树，此时 (A) 与其左子树的根节点 (B) 进行旋转操作：

• 将 (B) 作为新的父节点。
• 原先的 (B) 的右孩子成为 (A) 的新左子树的根节点。

此过程可以表示为：

   A              B
  / \            / \
 B   C    右旋 → D   A
 /                /
D                 C

左旋

左旋（Left Rotation）是对不平衡节点进行的另一种调整方式。假设某个节点 (A) 的右子树高度大于其左子树，此时 (A) 与其右子树的根节点 (B) 进行旋转操作：

• 将 (B) 作为新的父节点。
• 原先的 (B) 的左孩子成为 (A) 新右子树的根节点。

此过程可以表示为：

   A              B
  / \            / \
 C   B    左旋 → D   A
 /     \          /
D       C        C

结合使用

在某些情况下，简单的单次旋转可能不足以完全恢复AVL树的平衡。例如，当一个节点的左右子树高度差绝对值达到2时，我们首先进行一次旋转以缩小不平衡的程度，再根据新的不平衡状态继续旋转操作。

典型情况

1. LL（Left-Left）情况：插入或删除导致根节点 (A) 的左孩子的左子树变得过高。这时需要先执行右旋。
2. RR（Right-Right）情况：与 LL 情况相反，插入或删除导致根节点 (A) 的右孩子的右子树变得过高。这时同样首先执行左旋。

结合示例

假设在处理一个 LL 或 RR 不平衡状态时：

1. 首先进行一次相应的单向旋转（如右旋或左旋）。
2. 然后检查根节点的平衡因子，若仍不平衡，则继续进行另一方向的旋转。

例如，对于一个LL情况：

    A              B
   / \            / \
  B   C    右旋 → D   A
 /                /
D                 C

然后调整为：
      B
     / \
    D   A
   /
C

通过上述示例可以看到，结合使用单次旋转和多次旋转是恢复AVL树平衡的关键。

结论

理解并掌握左旋与右旋操作对于维护 AVL 树的平衡至关重要。这两种基本操作能够帮助我们处理各种不平衡情况，并确保二叉搜索树的性能维持在最优状态。