C语言数据结构之平衡二叉树（AVL树）实现方法示例

介绍

AVL树是一种自平衡二叉搜索树，它保证了所有节点的左右子树高度差不超过1，从而提高了查找、插入和删除操作的效率。本篇文章将介绍如何使用C语言实现AVL树，并提供两个例子以说明实现方法。

实现方法

结构体定义

首先，定义AVL树节点的结构体，包括该节点存储的值、该节点的高度、该节点的左右子树指针。

typedef struct AVLNode {
    int value;
    int height;
    struct AVLNode* left;
    struct AVLNode* right;
} AVLNode;

AVL树的基本操作函数

1. 计算节点高度

计算节点高度的函数可以递归实现，即左右子树高度的最大值加一。如果节点为NULL，其高度为0。

int height(AVLNode* node) {
    if (node == NULL) {
        return 0;
    }
    return 1 + max(height(node -> left), height(node -> right));
}

2. 计算平衡因子

平衡因子是指左子树高度减去右子树高度的差。如果平衡因子的绝对值大于1，则需要进行旋转以保持树的平衡。

int balance_factor(AVLNode* node) {
    if (node == NULL) {
        return 0;
    }
    return height(node -> left) - height(node -> right);
}

3. 左旋转操作

左旋转是指将某个节点的右子树旋转到它的左子树位置，使得该节点成为其右子树的左子树。左旋转需要保持树的平衡性。

AVLNode* left_rotate(AVLNode* node) {
    AVLNode* right_child = node -> right;
    AVLNode* left_subtree = right_child -> left;
    right_child -> left = node;
    node -> right = left_subtree;
    node -> height = max(height(node -> left), height(node -> right)) + 1;
    right_child -> height = max(height(right_child -> left), height(right_child -> right)) + 1;
    return right_child;
}

4. 右旋转操作

右旋转是指将某个节点的左子树旋转到它的右子树位置，使得该节点成为其左子树的右子树。右旋转需要保持树的平衡性。

AVLNode* right_rotate(AVLNode* node) {
    AVLNode* left_child = node -> left;
    AVLNode* right_subtree = left_child -> right;
    left_child -> right = node;
    node -> left = right_subtree;
    node -> height = max(height(node -> left), height(node -> right)) + 1;
    left_child -> height = max(height(left_child -> left), height(left_child -> right)) + 1;
    return left_child;
}

5. 插入操作

插入操作需要找到对应的插入位置，并在插入后保持树的平衡性。首先插入节点，并递归调整其祖先节点的平衡因子，如果平衡因子的绝对值超过1，则进行相应的旋转操作使得树重新平衡。

AVLNode* insert(AVLNode* root, int value) {
    if (root == NULL) {
        AVLNode* new_node = (AVLNode*)malloc(sizeof(AVLNode));
        new_node -> value = value;
        new_node -> height = 1;
        new_node -> left = NULL;
        new_node -> right = NULL;
        return new_node;
    }
    if (value < root -> value) {
        root -> left = insert(root -> left, value);
    } else {
        root -> right = insert(root -> right, value);
    }
    root -> height = max(height(root -> left), height(root -> right)) + 1;
    int bf = balance_factor(root);
    if (bf > 1 && value < root -> left -> value) {
        return right_rotate(root);
    }
    if (bf > 1 && value > root -> left -> value) {
        root -> left = left_rotate(root -> left);
        return right_rotate(root);
    }
    if (bf < -1 && value < root -> right -> value) {
        root -> right = right_rotate(root -> right);
        return left_rotate(root);
    }
    if (bf < -1 && value > root -> right -> value) {
        return left_rotate(root);
    }
    return root; 
}

例子1：插入数字

以下示例代码演示了如何使用上述AVL树的基本操作实现对数字的插入。

AVLNode* root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);

例子2：查找最小节点

除了插入操作外，还可以实现其他操作，例如查找AVL树中的最小节点。以下示例代码演示了如何使用递归实现查找AVL树中的最小节点。

AVLNode* min_node(AVLNode* root) {
    if (root == NULL || root -> left == NULL) {
        return root;
    }
    return min_node(root -> left);
}

总结

本文详细介绍了如何使用C语言实现AVL树的基本操作，包括计算节点高度、计算平衡因子、左旋转、右旋转及插入操作。并通过两个示例演示了如何插入数字及查找AVL树中的最小节点。使用AVL树可以提高二叉搜索树操作的效率，对于需要频繁进行插入、删除操作的数据结构场景来说，尤其有用。