平衡二叉排序树（Balanced Binary Search Tree）是一种自平衡的二叉查找树，它能够在插入、删除节点时自动调整以保持树的平衡，从而在平均情况下具有较好的性能。常见的平衡二叉排序树有AVL树和红黑树。

1. AVL树

AVL树是最早的平衡二叉排序树，得名于它的发明者G.M. Adelson-Velsky和E.M. Landis。在AVL树中，任意节点的两个子树的高度最大差别为1，且每个节点的左子树和右子树都是AVL树。

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

```c

include

include

// 定义节点结构体
typedef struct Node {
int key;
struct Node left;
struct Node right;
int height;
} Node;

// 定义AVL树结构体
typedef struct {
Node* root;
} AVLTree;

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

// 计算平衡因子
int getBalance(Node* node) {
if (node == NULL) {
return 0;
} else {
return height(node->left) - height(node->right);
}
}

// 右旋操作
Node rightRotate(Node y) {
Node x = y->left;
Node T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x; // 新根节点
}

// 左旋操作
Node leftRotate(Node x) {
Node y = x->right;
Node T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y; // 新根节点
}

// 插入节点并保持平衡（AVL插入）
Node insertNode(Node node, int key) {
if (node == NULL) {
return (Node*)malloc(sizeof(Node)); // 创建新节点并返回根节点指针
} else if (key < node->key) {
node->left = insertNode(node->left, key); // 递归左子树插入新节点并返回新的左子树根节点指针
if (getBalance(node->left) == -2) { // 左子树过高，需要进行左旋操作以保持平衡
if (getBalance(node->left->left) >= 0) { // 左子树的左子树非空，进行左左旋操作（LL）以保持平衡
node = leftRotate(node); // 返回新的根节点指针（现在指向原来的左子树的父节点）
} else { // 左子树的左子树为空，进行左右旋操作（LR）以保持平衡（即右旋+父节点上移）
node->left = rightRotate(node->left); // 对左子树进行右旋操作，返回新的左子树的根节点指针（现在指向原来的右子树的父节点）
}
}
} else if (key > node->key) { // 如果key大于node的key，则递归右子树插入新节点并返回新的右子树根节点指针，否则直接返回当前节点指针（重复key则不插入）
node->right = insertNode(node