二叉平衡树AVL的核心特性是任意节点的左右子树高度差不超过1，当插入或删除节点导致失衡时，需要通过旋转操作恢复平衡。旋转分为LL、RR、LR、RL四种类型，对应不同的失衡场景。
AVL树节点定义
首先定义AVL树的节点结构，包含节点值、左右子节点指针以及节点高度，高度用于判断树是否失衡。
#include <iostream>
#include <algorithm>
using namespace std;
// AVL树节点结构
struct AVLNode {
int val; // 节点存储的值
AVLNode* left; // 左子节点指针
AVLNode* right; // 右子节点指针
int height; // 节点高度
// 构造函数
AVLNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {}
};
// 获取节点高度，空节点高度为0
int getHeight(AVLNode* node) {
if (node == nullptr) {
return 0;
}
return node->height;
}
// 获取节点平衡因子，左子树高度减右子树高度
int getBalanceFactor(AVLNode* node) {
if (node == nullptr) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}
四种旋转操作实现
1. LL旋转（右旋）
LL旋转适用于当前节点的平衡因子大于1，且左子节点的平衡因子大于等于0的场景，即失衡节点左子树的左子树过高。操作逻辑是将左子节点提升为新的根，原失衡节点作为新根的右子节点，原左子节点的右子树作为原失衡节点的左子树。
// LL旋转（右旋）
AVLNode* rotateLL(AVLNode* node) {
AVLNode* leftChild = node->left; // 获取失衡节点的左子节点
AVLNode* leftRight = leftChild->right; // 获取左子节点的右子树
// 调整指针关系
leftChild->right = node;
node->left = leftRight;
// 更新节点高度，先更新原失衡节点，再更新新的根节点
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
leftChild->height = max(getHeight(leftChild->left), getHeight(leftChild->right)) + 1;
return leftChild; // 返回新的根节点
}
2. RR旋转（左旋）
RR旋转适用于当前节点的平衡因子小于-1，且右子节点的平衡因子小于等于0的场景，即失衡节点右子树的右子树过高。操作逻辑是将右子节点提升为新的根，原失衡节点作为新根的左子节点，原右子节点的左子树作为原失衡节点的右子树。
// RR旋转（左旋）
AVLNode* rotateRR(AVLNode* node) {
AVLNode* rightChild = node->right; // 获取失衡节点的右子节点
AVLNode* rightLeft = rightChild->left; // 获取右子节点的左子树
// 调整指针关系
rightChild->left = node;
node->right = rightLeft;
// 更新节点高度，先更新原失衡节点，再更新新的根节点
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
rightChild->height = max(getHeight(rightChild->left), getHeight(rightChild->right)) + 1;
return rightChild; // 返回新的根节点
}
3. LR旋转
LR旋转适用于当前节点的平衡因子大于1，且左子节点的平衡因子小于0的场景，即失衡节点左子树的右子树过高。操作逻辑是先对左子节点进行RR旋转，再对失衡节点进行LL旋转。
// LR旋转，先左旋左子节点，再右旋失衡节点
AVLNode* rotateLR(AVLNode* node) {
node->left = rotateRR(node->left); // 对左子节点做RR旋转
return rotateLL(node); // 对失衡节点做LL旋转
}
4. RL旋转
RL旋转适用于当前节点的平衡因子小于-1，且右子节点的平衡因子大于0的场景，即失衡节点右子树的左子树过高。操作逻辑是先对右子节点进行LL旋转，再对失衡节点进行RR旋转。
// RL旋转，先右旋右子节点，再左旋失衡节点
AVLNode* rotateRL(AVLNode* node) {
node->right = rotateLL(node->right); // 对右子节点做LL旋转
return rotateRR(node); // 对失衡节点做RR旋转
}
插入节点时的平衡调整
插入节点后，需要从插入位置向上回溯更新节点高度，判断每个节点是否失衡，根据平衡因子和子节点的平衡因子选择对应的旋转操作。
// 向AVL树插入节点
AVLNode* insertNode(AVLNode* root, int val) {
// 普通二叉搜索树插入逻辑
if (root == nullptr) {
return new AVLNode(val);
}
if (val < root->val) {
root->left = insertNode(root->left, val);
} else if (val > root->val) {
root->right = insertNode(root->right, val);
} else {
// 重复值不插入
return root;
}
// 更新当前节点高度
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
// 计算平衡因子，判断是否失衡
int balance = getBalanceFactor(root);
// LL情况
if (balance > 1 && val < root->left->val) {
return rotateLL(root);
}
// RR情况
if (balance < -1 && val > root->right->val) {
return rotateRR(root);
}
// LR情况
if (balance > 1 && val > root->left->val) {
return rotateLR(root);
}
// RL情况
if (balance < -1 && val < root->right->val) {
return rotateRL(root);
}
return root; // 未失衡，返回原节点
}
完整测试示例
以下代码测试插入一组节点，验证四种旋转操作的正确性，插入后中序遍历结果应为有序序列。
// 中序遍历AVL树
void inorderTraversal(AVLNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
AVLNode* root = nullptr;
// 测试插入序列，会触发不同的旋转场景
int nums[] = {10, 20, 30, 40, 50, 25};
for (int num : nums) {
root = insertNode(root, num);
}
cout << "AVL树中序遍历结果：";
inorderTraversal(root);
cout << endl;
return 0;
}