AVL树的双旋转（Double Rotation）

描述：
AVL树是一种自平衡二叉搜索树，它通过旋转操作来维持树的平衡。当插入或删除节点导致树的高度差（平衡因子）超过1时，就需要进行平衡操作。双旋转是处理某些特定不平衡情况的操作，它由两次单旋转组合而成。具体来说，双旋转分为两种类型：左右旋转（LR Rotation）和右左旋转（RL Rotation）。当不平衡节点的左子树比右子树高，且左子树的右子树更高时，需要进行LR旋转；当不平衡节点的右子树比左子树高，且右子树的左子树更高时，需要进行RL旋转。

解题过程：

1. 识别不平衡节点：

   • 在AVL树中插入或删除节点后，从被修改的节点开始向上回溯，检查每个祖先节点的平衡因子（左子树高度减去右子树高度）。
   • 如果某个节点的平衡因子绝对值大于1（例如2或-2），则该节点为不平衡节点，需要调整。

2. 确定旋转类型：

   • 检查不平衡节点的左右子树的高度差，以确定是单旋转还是双旋转。
   • 对于不平衡节点A：
     • 如果A的左子树更高（平衡因子为2），且A的左孩子B的右子树更高（B的平衡因子为-1），则需要进行LR旋转。
     • 如果A的右子树更高（平衡因子为-2），且A的右孩子B的左子树更高（B的平衡因子为1），则需要进行RL旋转。

3. LR旋转（左右旋转）：

   • 步骤1：对不平衡节点A的左孩子B进行右旋转（RR Rotation）。这一步将B的右孩子C提升为新的根（相对于B和C的子树），使B成为C的左孩子。
   • 步骤2：对不平衡节点A进行左旋转（LL Rotation）。这一步将C提升为整个子树的根，A成为C的右孩子。
   • 示例：假设A是失衡节点，B是A的左孩子，C是B的右孩子。LR旋转后，C成为新的根，B成为C的左孩子，A成为C的右孩子。

4. RL旋转（右左旋转）：

   • 步骤1：对不平衡节点A的右孩子B进行左旋转（LL Rotation）。这一步将B的左孩子C提升为新的根（相对于B和C的子树），使B成为C的右孩子。
   • 步骤2：对不平衡节点A进行右旋转（RR Rotation）。这一步将C提升为整个子树的根，A成为C的左孩子。
   • 示例：假设A是失衡节点，B是A的右孩子，C是B的左孩子。RL旋转后，C成为新的根，A成为C的左孩子，B成为C的右孩子。

5. 更新高度：

   • 旋转完成后，需要重新计算相关节点的高度和平衡因子，确保树的平衡性。
   • 由于旋转操作只影响局部子树，因此只需更新被旋转节点及其孩子的高度。

6. 时间复杂度：

   • 双旋转操作的时间复杂度为O(1)，因为只涉及常数次指针调整。
   • 但由于需要从插入/删除点向上回溯到根节点，整体平衡操作的时间复杂度为O(log n)，其中n是树中节点数。

通过双旋转，AVL树可以在插入或删除后快速恢复平衡，保证查找、插入和删除操作的时间复杂度均为O(log n)。