平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，它的左右子树的高度差不超过1，这样可以保证树的高度相对较低，从而使得查找、插入和删除操作的时间复杂度保持在 。
平衡二叉树的基本概念
1. 二叉树：每个节点最多有两个子节点，分别称为左子节点和右子节点。
2. 平衡条件：对于每个节点，左子树和右子树的高度差的绝对值不超过1。
3. 高度：树的高度是从根节点到最深叶子节点的最长路径上的边的数量。
AVL树
AVL树是最早的自平衡二叉查找树，由G.M. Adelson-Velsky和E.M. Landis在1962年提出。AVL树通过在每个节点存储一个平衡因子（左子树高度减去右子树高度）来保持平衡。
AVL树的基本操作
1. 插入：插入新节点后，检查树的平衡情况，必要时进行旋转操作以保持平衡。
2. 删除：删除节点后，同样检查树的平衡情况，并进行旋转操作。
3. 旋转：包括左旋、右旋、左右旋和右左旋四种操作，用于调整树的结构。
AVL树的实现
下面是一个简单的AVL树实现，包括插入和旋转操作的示例代码：
#include <stdio.h>
#include <stdlib.h>
// AVL树节点结构
typedef struct Node {
int key;
int height; // 节点的高度
struct Node* left;
struct Node* right;
} Node;
// 获取节点的高度
int height(Node* N) {
if (N == NULL)
return 0;
return N->height;
}
// 获取平衡因子
int getBalance(Node* N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// 创建新节点
Node* newNode(int key) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // 新节点的高度为1
return node;
}
// 右旋转
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
// 进行旋转
x->right = y;
y->left = T2;
// 更新高度
y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
return x; // 返回新的根节点
}
// 左旋转
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
// 进行旋转
y->left = x;
x->right = T2;
// 更新高度
x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
return y; // 返回新的根节点
}
// 插入节点
Node* insert(Node* node, int key) {
// 1. 执行常规的BST插入
if (node == NULL)
return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // 不允许重复的键
return node;
// 2. 更新节点的高度
node->height = 1 + (height(node->left) > height(node->right) ? height(node->left) : height(node->right));
// 3. 检查平衡性
int balance = getBalance(node);
// 如果不平衡，有四种情况
// 左左情况
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// 右右情况
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// 左右情况
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// 右左情况
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
// 返回（未改变的）节点指针
return node;
}
// 中序遍历
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
int main() {
Node* 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);
// 中序遍历
printf("中序遍历AVL树：");
inorder(root);
printf("\n");
return 0;
}
代码说明
1. 节点结构：`Node`结构体包含键值、节点高度和左右子节点的指针。
2. 高度和平衡因子的计算：`height`和`getBalance`函数用于计算节点的高度和获取平衡因子。
3. 旋转操作：`rightRotate`和`leftRotate`函数用于进行树的旋转，以保持平衡。
4. 插入操作：`insert`函数用于插入新节点并保持AVL树的平衡。
5. 中序遍历：`inorder`函数用于遍历树并输出节点的键值。