[数据结构·树] 平衡二叉搜索树（AVL）

🌳 AVL 树 (自平衡二叉查找树) 的 C 语言实现与解析

AVL 树是一种自平衡的二叉查找树（BST）。它通过在插入和删除节点后进行“旋转”操作，来确保树的高度始终保持在 $O(\log n)$ 级别，从而保证了所有基本操作（查找、插入、删除）的最坏时间复杂度都是 $O(\log n)$。

---

📄 完整的 C 语言实现代码

#include <stdio.h>
#include <stdlib.h>

// 1. 节点结构定义
// 相比普通的BST，增加了 'height' 字段
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    int height; // 存储以此节点为根的子树的高度
};

// 辅助函数：获取两个整数中的较大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 辅助函数：获取节点的高度 (处理 NULL 节点)
// 空树的高度定义为 -1（或 0，这里用 0 更方便计算平衡因子）
// 为了方便计算平衡因子，我们将空节点的高度设为 0
// 这样叶子节点的高度就是 1
int height(struct Node* N) {
    if (N == NULL)
        return 0; // 空节点高度为 0
    return N->height;
}

// 辅助函数：创建新节点
struct Node* createNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; // 新节点作为叶子节点，高度为 1
    return node;
}

// 2. 关键辅助函数：获取平衡因子 (Balance Factor)
// 平衡因子 = 左子树高度 - 右子树高度
int getBalanceFactor(struct Node* N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

// 3. 核心操作：旋转 (Rotation)

// 3.1 右旋转 (Right Rotation)
// 针对 "左-左" (LL) 不平衡情况
//
//       y                               x
//      / \                             / \
//     x   T3                          T1  y
//    / \       --(右旋转 y)-->       / \
//   T1  T2                         T2  T3
//
struct Node* rightRotate(struct Node* y) {
    struct Node* x = y->left;
    struct Node* T2 = x->right;

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

    // 更新高度 (必须先更新 y，再更新 x)
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // 返回新的根节点
    return x;
}

// 3.2 左旋转 (Left Rotation)
// 针对 "右-右" (RR) 不平衡情况
//
//     x                               y
//    / \                             / \
//   T1  y                           x   T3
//      / \     --(左旋转 x)-->     / \
//     T2  T3                     T1  T2
//
struct Node* leftRotate(struct Node* x) {
    struct Node* y = x->right;
    struct Node* T2 = y->left;

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

    // 更新高度 (必须先更新 x，再更新 y)
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // 返回新的根节点
    return y;
}


// 4. 插入节点 (Insert)
struct Node* insert(struct Node* node, int data) {
    // --- 步骤 1: 执行标准的 BST 插入 ---
    if (node == NULL)
        return (createNode(data));

    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    else // 不允许插入重复值
        return node;

    // --- 步骤 2: 更新祖先节点的高度 ---
    node->height = 1 + max(height(node->left), height(node->right));

    // --- 步骤 3: 获取平衡因子，检查是否失衡 ---
    int balance = getBalanceFactor(node);

    // --- 步骤 4: 如果失衡，执行旋转 (4 种情况) ---

    // 情况 1: 左-左 (LL)
    // data < node->left->data
    if (balance > 1 && data < node->left->data) {
        return rightRotate(node);
    }

    // 情况 2: 右-右 (RR)
    // data > node->right->data
    if (balance < -1 && data > node->right->data) {
        return leftRotate(node);
    }

    // 情况 3: 左-右 (LR)
    // data > node->left->data
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left); // 先对左子节点进行左旋
        return rightRotate(node);            // 再对当前节点进行右旋
    }

    // 情况 4: 右-左 (RL)
    // data < node->right->data
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right); // 先对右子节点进行右旋
        return leftRotate(node);             // 再对当前节点进行左旋
    }

    // 如果未失衡，直接返回原节点指针
    return node;
}

// 辅助函数：查找子树中的最小节点 (用于删除)
struct Node* findMin(struct Node* node) {
    struct Node* current = node;
    while (current->left != NULL)
        current = current->left;
    return current;
}

// 5. 删除节点 (Delete)
struct Node* deleteNode(struct Node* root, int data) {
    // --- 步骤 1: 执行标准的 BST 删除 ---
    if (root == NULL)
        return root;

    // 查找节点
    if (data < root->data)
        root->left = deleteNode(root->left, data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    else {
        // 找到了要删除的节点

        // 情况 1: 节点有 0 个或 1 个子节点
        if ((root->left == NULL) || (root->right == NULL)) {
            struct Node* temp = root->left ? root->left : root->right;

            // 0 个子节点
            if (temp == NULL) {
                temp = root;
                root = NULL; // 树变空 (如果这是唯一的节点)
            } else {
                // 1 个子节点
                *root = *temp; // 复制子节点的内容到当前节点
            }
            free(temp); // 释放旧的子节点 (或当前节点)
        } else {
            // 情况 2: 节点有 2 个子节点
            // 找到右子树中的最小节点 (中序后继)
            struct Node* temp = findMin(root->right);

            // 用后继者的值替换当前节点的值
            root->data = temp->data;

            // 从右子树中删除那个后继者
            root->right = deleteNode(root->right, temp->data);
        }
    }

    // 如果删除后树为空 (比如删除了唯一的节点)，则直接返回
    if (root == NULL)
        return root;

    // --- 步骤 2: 更新当前节点的高度 ---
    root->height = 1 + max(height(root->left), height(root->right));

    // --- 步骤 3: 获取平衡因子，检查是否失衡 ---
    int balance = getBalanceFactor(root);

    // --- 步骤 4: 如果失衡，执行旋转 (4 种情况) ---

    // 情况 1: 左-左 (LL)
    // 注意：这里的判断条件与 insert 不同，只看平衡因子
    if (balance > 1 && getBalanceFactor(root->left) >= 0) {
        return rightRotate(root);
    }

    // 情况 2: 左-右 (LR)
    if (balance > 1 && getBalanceFactor(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // 情况 3: 右-右 (RR)
    if (balance < -1 && getBalanceFactor(root->right) <= 0) {
        return leftRotate(root);
    }

    // 情况 4: 右-左 (RL)
    if (balance < -1 && getBalanceFactor(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    // 返回 (可能已更新的) 根节点
    return root;
}

// 辅助函数：中序遍历 (用于测试)
void inOrder(struct Node* root) {
    if (root != NULL) {
        inOrder(root->left);
        printf("%d (h=%d, bf=%d) ", root->data, root->height, getBalanceFactor(root));
        inOrder(root->right);
    }
}

// 主函数：演示
int main() {
    struct Node* root = NULL;

    printf("--- 插入操作 (触发 LL, RR, LR, RL 旋转) ---\n");
    
    // 插入 10, 20 (触发 RR)
    root = insert(root, 10);
    root = insert(root, 20);
    printf("插入 10, 20 (RR): "); inOrder(root); printf("\n");
    
    // 插入 30 (再次 RR)
    root = insert(root, 30);
    printf("插入 30 (RR): "); inOrder(root); printf("\n"); // 根应为 20

    // 插入 40 (RR)
    root = insert(root, 40);
    printf("插入 40 (RR): "); inOrder(root); printf("\n");

    // 插入 50 (RR)
    root = insert(root, 50);
    printf("插入 50 (RR): "); inOrder(root); printf("\n"); // 根应为 40 (或 20)

    // 插入 25 (触发 RL)
    root = insert(root, 25);
    printf("插入 25 (RL): "); inOrder(root); printf("\n"); // 根应为 30
    
    // 插入 5, 4 (触发 LL)
    root = insert(root, 5);
    root = insert(root, 4);
    printf("插入 5, 4 (LL): "); inOrder(root); printf("\n");
    
    // 插入 8 (触发 LR)
    root = insert(root, 8);
    printf("插入 8 (LR): "); inOrder(root); printf("\n");


    printf("\n最终中序遍历 (排序结果): \n");
    inOrder(root);
    printf("\n");

    printf("\n--- 删除操作 ---\n");
    
    // 删除 4 (叶子节点, 可能触发旋转)
    printf("删除 4: \n");
    root = deleteNode(root, 4);
    inOrder(root);
    printf("\n");
    
    // 删除 8 (叶子节点)
    printf("删除 8: \n");
    root = deleteNode(root, 8);
    inOrder(root);
    printf("\n");

    // 删除 20 (有两个孩子)
    printf("删除 20: \n");
    root = deleteNode(root, 20);
    inOrder(root);
    printf("\n");
    
    // 删除 30 (根节点)
    printf("删除 30 (根): \n");
    root = deleteNode(root, 30);
    inOrder(root);
    printf("\n");

    return 0;
}

---

🔑 关键代码解析

AVL 树的核心在于 insert 和 deleteNode 函数中的平衡维护部分。

1. height() 和 getBalanceFactor()

这是 AVL 树的基础。

• height(struct Node* N):

  • 这个辅助函数用于安全地获取一个节点的高度。

  • 关键点： 它必须能处理 NULL 节点。我们将 NULL 节点的高度定义为 0 (有些实现定义为 -1，但 0 更便于计算)。叶子节点的高度因此为 1。

• getBalanceFactor(struct Node* N):

  • 计算平衡因子 (BF)，这是 AVL 树的核心指标。

  • $BF = height(N \rightarrow left) - height(N \rightarrow right)$

  • 平衡条件： 对于一棵 AVL 树，所有节点的 $BF$ 必须在 [-1, 0, 1] 这个范围内。

  • 如果 $BF > 1$，意味着左子树比右子树“重”太多（左倾）。

  • 如果 $BF < -1$，意味着右子树比左子树“重”太多（右倾）。

2. 旋转操作：leftRotate() 和 rightRotate()

旋转是恢复平衡的唯一手段。它们在 $O(1)$ 时间内完成，并且保持了二叉查找树的有序性。

• rightRotate(y):

  • 当节点 y 因为其左子节点 x（Left）而变得不平衡时使用。

  • 它将 x 提升为新的根，y 降为 x 的右子节点。

  • x 原本的右子树 (T2) 变成了 y 的新左子树。

  • 重要： 必须先更新 y 的高度，再更新 x 的高度，因为 x 的新高度依赖于 y 的新高度。

• leftRotate(x):

  • 当节点 x 因为其右子节点 y（Right）而变得不平衡时使用。

  • 它将 y 提升为新的根，x 降为 y 的左子节点。

  • y 原本的左子树 (T2) 变成了 x 的新右子树。

3. insert(node, data) 插入操作

这是最关键的部分。它分为 4 个步骤：

1. 标准 BST 插入：

   • 使用递归，像普通二叉查找树一样找到 NULL 位置，并插入新节点。

2. 更新高度：

   • 在递归返回（回溯）的路径上，更新从新节点到根节点路径上所有祖先节点的高度。

   • node->height = 1 + max(height(node->left), height(node->right));

3. 获取平衡因子：

   • int balance = getBalanceFactor(node);

4. 检查并执行旋转（四种情况）：

   • 在回溯路径上，我们检查第一个不平衡的节点（即 balance > 1 或 balance < -1 的节点）并进行修正。

   • a. 左-左 (LL) 情况 (balance > 1)

     • 触发： 在 node 的左 (L)子树的左 (L)边插入了新节点。

     • 判断： balance > 1 且 data < node->left->data。

     • 修正： 对 node 执行一次右旋转 (rightRotate(node))。

   • b. 右-右 (RR) 情况 (balance < -1)

     • 触发： 在 node 的右 (R)子树的右 (R)边插入了新节点。

     • 判断： balance < -1 且 data > node->right->data。

     • 修正： 对 node 执行一次左旋转 (leftRotate(node))。

   • c. 左-右 (LR) 情况 (balance > 1)

     • 触发： 在 node 的左 (L)子树的右 (R)边插入了新节点。

     • 判断： balance > 1 且 data > node->left->data。

     • 修正（两步）：

       1. node->left = leftRotate(node->left); (先对其左子节点左旋，将其变为 LL 情况)

       2. return rightRotate(node); (再对 node 右旋)

   • d. 右-左 (RL) 情况 (balance < -1)

     • 触发： 在 node 的右 (R)子树的左 (L)边插入了新节点。

     • 判断： balance < -1 且 data < node->right->data。

     • 修正（两步）：

       1. node->right = rightRotate(node->right); (先对其右子节点右旋，将其变为 RR 情况)

       2. return leftRotate(node); (再对 node 左旋)

4. deleteNode(root, data) 删除操作

删除操作比插入更复杂，因为它可能导致沿途多个节点失衡（而插入最多只会导致一个节点失衡）。

1. 标准 BST 删除：

   • 和我们之前实现的 BST 删除逻辑一样。

   • 找到节点，分 0、1、2 个子节点三种情况处理。

   • 如果是 2 个子节点，用中序后继（右子树的最小值）替换它，然后递归地删除那个后继节点。

2. 处理树为空：

   • 如果删除的是最后一个节点 (root == NULL)，必须立即返回，否则后续的高度更新会访问空指针。

3. 更新高度：

   • 同插入操作。

4. 检查并执行旋转：

   • 这一步的逻辑与插入类似，但判断条件略有不同。我们不再依赖 data（因为 data 已经被删了或替换了），而是直接检查子节点的平衡因子。

   • LL 情况： balance > 1 且 getBalanceFactor(root->left) >= 0。

   • LR 情况： balance > 1 且 getBalanceFactor(root->left) < 0。

   • RR 情况： balance < -1 且 getBalanceFactor(root->right) <= 0。

   • RL 情况： balance < -1 且 getBalanceFactor(root->right) > 0。

   • 注意： 因为删除操作可能导致多个祖先节点失衡，所以不需要在找到第一个失衡点后就停止，递归的回溯过程会自动修正所有路径上的失衡。