c语言平衡二叉排序树的建立

平衡二叉排序树（AVL树）是一种自平衡的二叉搜索树，保证在最坏情况下的时间复杂度为O(log N)。下面是C语言实现平衡二叉排序树的基本步骤：

1. 定义AVL树结构体节点：

typedef struct AVLNode {
    int data; // 存储数据
    int height; // 节点高度
    struct AVLNode *left; // 左子节点指针
    struct AVLNode *right; // 右子节点指针
} AVLNode;

2. 定义AVL树结构体：

typedef struct AVLTree {
    AVLNode *root; // 根节点指针
} AVLTree;

3. 实现计算节点高度的函数：

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

4. 实现计算节点平衡因子的函数：

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

5. 实现AVL树的左旋和右旋操作：

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

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

6. 实现AVL树的插入操作：

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

7. 实现AVL树的查找操作：

AVLNode *search(AVLNode *node, int data) {
    if (node == NULL) {
        return NULL;
    }
    if (data == node->data) {
        return node;
    }
    if (data < node->data) {
        return search(node->left, data);
    } else {
        return search(node->right, data);
    }
}

8. 最后，定义AVL树的初始化和销毁操作：

void init_avl_tree(AVLTree *tree) {
    tree->root = NULL;
}

void destroy_avl_tree(AVLNode *node) {
    if (node == NULL) {
        return;
    }
    destroy_avl_tree(node->left);
    destroy_avl_tree(node->right);
    free(node);
}

这样就完成了平衡二叉排序树的建立。