自平衡二叉查找树 又称高度平衡树

AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。因此被命名为AVL树，以纪念发明者Georgy Adelson-Velsky和Evgenii Landis。

AVL树是一种自平衡二叉搜索树，其平衡性是通过旋转操作来实现的。AVL树的特点是任何节点的左右子树的高度差最多为1。当节点插入或删除时，如果导致某个节点的左右子树高度差超过1，就需要进行旋转操作来保持平衡。

AVL树有四种旋转操作：左旋、右旋、左右旋和右左旋。这些旋转操作会改变节点的父节点、左子节点和右子节点之间的关系，以达到平衡的效果。

AVL树的优点是在最坏情况下的查找、插入和删除操作都具有O(log n)的时间复杂度，相对于其他自平衡树（如红黑树）而言，其平衡性更为严格。

但AVL树的缺点是由于需要频繁进行旋转操作，导致其在插入和删除操作时的常数项比较大，因此在实际应用中，常常使用其他平衡树来代替AVL树。

以下是一个简单的C语言实现AVL树的代码：

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

// AVL树节点结构体定义
typedef struct AVLNode {
    int data;               // 节点数据
    int height;             // 节点高度
    struct AVLNode* left;   // 左子节点
    struct AVLNode* right;  // 右子节点
} AVLNode;

// 获取节点高度
int getHeight(AVLNode* node) {
    if (node == NULL) {
        return -1;
    } else {
        return node->height;
    }
}

// 更新节点高度
void updateHeight(AVLNode* node) {
    int heightLeft = getHeight(node->left);
    int heightRight = getHeight(node->right);
    node->height = (heightLeft > heightRight ? heightLeft : heightRight) + 1;
}

// 右旋操作
AVLNode* rightRotate(AVLNode* node) {
    AVLNode* leftChild = node->left;
    node->left = leftChild->right;
    leftChild->right = node;
    updateHeight(node);
    updateHeight(leftChild);
    return leftChild;
}

// 左旋操作
AVLNode* leftRotate(AVLNode* node) {
    AVLNode* rightChild = node->right;
    node->right = rightChild->left;
    rightChild->left = node;
    updateHeight(node);
    updateHeight(rightChild);
    return rightChild;
}

// 左右旋操作
AVLNode* leftRightRotate(AVLNode* node) {
    node->left = leftRotate(node->left);
    return rightRotate(node);
}

// 右左旋操作
AVLNode* rightLeftRotate(AVLNode* node) {
    node->right = rightRotate(node->right);
    return leftRotate(node);
}

// 插入节点
AVLNode* insertNode(AVLNode* node, int data) {
    if (node == NULL) {
        // 创建新节点
        AVLNode* newNode = (AVLNode*)malloc(sizeof(AVLNode));
        newNode->data = data;
        newNode->height = 0;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    } else if (data < node->data) {
        node->left = insertNode(node->left, data);
        // 检查是否需要旋转
        if (getHeight(node->left) - getHeight(node->right) == 2) {
            if (data < node->left->data) {
                node = rightRotate(node);
            } else {
                node = leftRightRotate(node);
            }
        }
    } else if (data > node->data) {
        node->right = insertNode(node->right, data);
        // 检查是否需要旋转
        if (getHeight(node->right) - getHeight(node->left) == 2) {
            if (data > node->right->data) {
                node = leftRotate(node);
            } else {
                node = rightLeftRotate(node);
            }
        }
    }
    // 更新节点高度
    updateHeight(node);
    return node;
}

// 遍历AVL树
void traverse(AVLNode* node) {
    if (node != NULL) {
        printf("%d ", node->data);
        traverse(node->left);
        traverse(node->right);
    }
}