AVL树的旋转

AVL树是一种自平衡二叉搜索树（Self-Balancing Binary Search Tree），以其发明者Adelson-Velsky和Landis的名字命名。它是一种确保二叉搜索树在插入或删除节点后仍然保持平衡的树形数据结构。

AVL树的特点

1. 平衡因子（Balance Factor）：每个节点的平衡因子定义为其左子树的高度减去右子树的高度。

平衡因子的值只能是-1、0或1，即：

• 0：左子树高度等于右子树高度。
• 1：左子树比右子树高1。
• -1：右子树比左子树高1。

如果任一节点的平衡因子超出范围（例如2或-2），则树不再平衡，需要通过旋转操作恢复平衡。

2. 时间复杂度：查找、插入和删除操作的时间复杂度均为 O(log n)，因为AVL树的高度始终保持接近对数级别。
3. 自平衡性：插入或删除节点后，通过旋转操作（单旋转或双旋转）来恢复平衡。

AVL树插入的例子

我们从空树开始，按顺序插入以下节点值：10, 20, 30, 40, 50, 25，并展示插入过程中的旋转调整。

---

步骤 1：插入 10

• 树为空，直接插入 10 作为根节点。
• 树结构：

  10

• 平衡，无需调整。

---

步骤 2：插入 20

• 20 大于 10，成为 10 的右子节点。
• 树结构：

  10
    \
     20

• 平衡因子：
  • 节点 10 的平衡因子：-1（左子树高度 0 - 右子树高度 1）。
• 平衡，无需调整。

---

步骤 3：插入 30

• 30 大于 20，成为 20 的右子节点。

• 树结构：

  10
    \
     20
       \
        30

• 平衡因子：

  • 节点 10 的平衡因子：-2（左子树高度 0 - 右子树高度 2）。
  • 节点 20 的平衡因子：-1（左子树高度 0 - 右子树高度 1）。

• 不平衡：RR型（右-右失衡）。

• 解决方法：对节点 10 左旋调整。

• 调整后树结构：

    20
   /  \
  10   30

---

步骤 4：插入 40

• 40 大于 30，成为 30 的右子节点。

• 树结构：

    20
   /  \
  10   30
         \
          40

• 平衡因子：

  • 节点 20 的平衡因子：-1（左子树高度 1 - 右子树高度 2）。
  • 节点 30 的平衡因子：-1（左子树高度 0 - 右子树高度 1）。

• 平衡，无需调整。

---

步骤 5：插入 50

• 50 大于 40，成为 40 的右子节点。

• 树结构：

    20
   /  \
  10   30
         \
          40
            \
             50

• 平衡因子：

  • 节点 20 的平衡因子：-2（左子树高度 1 - 右子树高度 3）。
  • 节点 30 的平衡因子：-2（左子树高度 0 - 右子树高度 2）。
  • 节点 40 的平衡因子：-1（左子树高度 0 - 右子树高度 1）。

• 不平衡：RR型（右-右失衡）。

• 解决方法：对节点 30 左旋调整。

• 调整后树结构：

    20
   /  \
  10   40
       /  \
      30   50

---

步骤 6：插入 25

• 25 大于 20，小于 40，小于 30，成为 30 的左子节点。

• 树结构：

    20
   /  \
  10   40
       /  \
      30   50
     /
    25

• 平衡因子：

  • 节点 20 的平衡因子：-2（左子树高度 1 - 右子树高度 3）。
  • 节点 40 的平衡因子：1（左子树高度 2 - 右子树高度 1）。
  • 节点 30 的平衡因子：1（左子树高度 1 - 右子树高度 0）。

• 不平衡：RL型（右-左失衡）。

• 解决方法：对节点 40 进行右旋-左旋调整。

  1. 右旋节点 30：

       20
      /  \
     10   40
          /  \
         25   50
           \
            30

  2. 左旋节点 40：

       20
      /  \
     10   30
          /  \
         25   40
                \
                 50

---

最终 AVL 树

调整完成后，最终的 AVL 树如下：

  20
 /  \
10   30
     /  \
    25   40
           \
            50

---

插入过程中的平衡操作总结：

1. RR型：对节点 10 左旋。
2. RR型：对节点 30 左旋。
3. RL型：对节点 40 先右旋再左旋。

AVL树的旋转操作定义

旋转是AVL树在插入或删除节点后，用来恢复平衡的一种调整操作。旋转分为单旋转（左旋或右旋）和双旋转（先右后左或先左后右），每种旋转都有明确的定义和步骤。

---

1. 单旋转

右旋（Right Rotation）

右旋用于左子树过高（LL型失衡）的情况。

定义：

1. 选择失衡节点 ( A )。
2. 将 ( A ) 的左子节点 ( B ) 作为新的根。
3. 将 ( B ) 的右子树 ( T2 ) 移到 ( A ) 的左子树位置。
4. 将 ( A ) 移为 ( B ) 的右子节点。

操作示意图：

不平衡前（LL型失衡）：
        A
       /
      B
     /
    C

右旋后：
        B
       / \
      C   A

---

左旋（Left Rotation）

左旋用于右子树过高（RR型失衡）的情况。

定义：

1. 选择失衡节点 ( A )。
2. 将 ( A ) 的右子节点 ( B ) 作为新的根。
3. 将 ( B ) 的左子树 ( T2 ) 移到 ( A ) 的右子树位置。
4. 将 ( A ) 移为 ( B ) 的左子节点。

操作示意图：

不平衡前（RR型失衡）：
        A
         \
          B
           \
            C

左旋后：
        B
       / \
      A   C

---

2. 双旋转

双旋转用于**左右型失衡（LR型）或右左型失衡（RL型）**的情况。

LR型旋转（先左后右）

当节点 ( A ) 的左子树 ( B ) 的右子树过高时，需要LR旋转。

步骤：

1. 对 ( A ) 的左子节点 ( B ) 执行左旋。
2. 对节点 ( A ) 执行右旋。

操作示意图：

不平衡前：
        A
       /
      B
       \
        C

LR旋转后：
        C
       / \
      B   A

---

RL型旋转（先右后左）

当节点 ( A ) 的右子树 ( B ) 的左子树过高时，需要RL旋转。

步骤：

1. 对 ( A ) 的右子节点 ( B ) 执行右旋。
2. 对节点 ( A ) 执行左旋。

操作示意图：

不平衡前：
        A
         \
          B
         /
        C

RL旋转后：
        C
       / \
      A   B

代码实现

#include <iostream>
using namespace std;

// 定义AVL树的节点结构
struct Node {
    int key;        // 节点值
    int height;     // 节点高度
    Node* left;     // 左子节点
    Node* right;    // 右子节点

    Node(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};

// 获取节点高度
int getHeight(Node* node) {
    return node ? node->height : 0;
}

// 计算节点的平衡因子
int getBalanceFactor(Node* node) {
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

// 更新节点高度
void updateHeight(Node* node) {
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
}

// **右旋操作**
Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // 旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    updateHeight(y);
    updateHeight(x);

    return x;  // 新的根节点
}

// **左旋操作**
Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // 旋转
    y->left = x;
    x->right = T2;

    // 更新高度
    updateHeight(x);
    updateHeight(y);

    return y;  // 新的根节点
}

// **插入节点并调整平衡**
Node* insert(Node* root, int key) {
    if (!root) return new Node(key);

    // 插入到左子树
    if (key < root->key) {
        root->left = insert(root->left, key);
    }
    // 插入到右子树
    else if (key > root->key) {
        root->right = insert(root->right, key);
    } else {
        return root;  // 不允许重复值
    }

    // 更新当前节点高度
    updateHeight(root);

    // 计算平衡因子
    int balance = getBalanceFactor(root);

    // **LL型（左-左）**
    if (balance > 1 && key < root->left->key) {
        return rightRotate(root);
    }

    // **RR型（右-右）**
    if (balance < -1 && key > root->right->key) {
        return leftRotate(root);
    }

    // **LR型（左-右）**
    if (balance > 1 && key > root->left->key) {
        root->left = leftRotate(root->left);  // 先对左子树左旋
        return rightRotate(root);            // 再对根节点右旋
    }

    // **RL型（右-左）**
    if (balance < -1 && key < root->right->key) {
        root->right = rightRotate(root->right);  // 先对右子树右旋
        return leftRotate(root);                // 再对根节点左旋
    }

    return root;  // 返回平衡后的根节点
}

// **中序遍历**
void inOrder(Node* root) {
    if (root) {
        inOrder(root->left);
        cout << root->key << " ";
        inOrder(root->right);
    }
}

// 主函数
int main() {
    Node* root = nullptr;

    // 插入节点
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);  // RR型失衡，触发左旋
    root = insert(root, 40);
    root = insert(root, 50);  // RR型失衡，触发左旋
    root = insert(root, 25);  // RL型失衡，触发右旋+左旋

    // 中序遍历，输出结果
    cout << "中序遍历结果: ";
    inOrder(root);
    cout << endl;

    return 0;
}