AVL树通过旋转操作维持平衡，确保操作时间复杂度为O(log n)。
AVL树是一种自平衡二叉搜索树，它通过保持每个节点的左右子树高度差不超过1来确保查找、插入和删除操作的时间复杂度始终为O(log n)。C++中实现AVL树需要结合二叉搜索树的基本结构，并在插入和删除后通过旋转操作维持平衡。
AVL树的基本结构
每个AVL节点包含数据值、左右子节点指针以及一个表示该节点高度的整数。结构定义如下：
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
int height;
TreeNode(int val) : data(val), left(nullptr), right(nullptr), height(1) {}};
高度信息用于计算平衡因子（左子树高度减右子树高度），当平衡因子绝对值大于1时，说明树失衡，需进行旋转调整。
旋转操作详解
AVL树通过四种旋转操作恢复平衡：左旋、右旋、左右双旋、右左双旋。这些操作是核心机制。
- 右旋转（Right Rotation）：适用于“左左”情况，即左子树过高且新节点插入在左侧。
- 左旋转（Left Rotation）：适用于“右右”情况，即右子树过高且新节点插入在右侧。
- 左右双旋：先对左子节点左旋，再对当前节点右旋，处理“左右”插入情形。
- 右左双旋：先对右子节点右旋，再对当前节点左旋，应对“右左”插入情形。
旋转函数示例如下：
int getHeight(TreeNode* node) {
return node ? node->height : 0;
}
int getBalance(TreeNode* node) {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
}
TreeNode rotateRight(TreeNode y) {
TreeNode x = y->left;
TreeNode T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}
TreeNode rotateLeft(TreeNode x) {
TreeNode y = x->right;
TreeNode T2 = y->left;
y->left = x;
x->righ
t = T2;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;
}
t = T2;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;插入操作与平衡维护
插入过程类似二叉搜索树，递归找到位置后创建新节点。回溯过程中更新各节点高度并检查平衡性，必要时执行相应旋转。
TreeNode* insert(TreeNode* root, int data) {
if (!root)
return new TreeNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
else
return root; // 不允许重复值
root->height = 1 + max(getHeight(root->left), getHeight(root->right));
int balance = getBalance(root);
// 左左情况
if (balance > 1 && data < root->left->data)
return rotateRight(root);
// 右右情况
if (balance < -1 && data > root->right->data)
return rotateLeft(root);
// 左右情况
if (balance > 1 && data > root->left->data) {
root->left = rotateLeft(root->left);
return rotateRight(root);
}
// 右左情况
if (balance < -1 && data < root->right->data) {
root->right = rotateRight(root->right);
return rotateLeft(root);
}
return root;}
完整性与使用建议
实际应用中还需实现删除操作，其逻辑更复杂：删除后同样要更新高度并判断是否失衡，然后选择合适旋转修复。遍历方式如中序遍历可用于验证树的有序性。
调试时可添加打印函数输出树结构或节点高度，便于观察旋转效果。注意内存管理，在大型项目中考虑智能指针避免泄漏。
基本上就这些。掌握AVL树的关键在于理解旋转的本质——通过局部结构调整恢复全局平衡，而递归插入提供了天然的回溯时机来进行这些调整。
