AVL树通过维持左右子树高度差不超过1来保证操作时间复杂度为O(log n)，需在插入删除后更新高度并进行旋转调整。
AVL树是一种自平衡的二叉搜索树，它通过维持左右子树的高度差不超过1来保证树的整体高度始终接近log(n)，从而确保查找、插入和删除操作的时间复杂度为O(log n)。在C++中实现AVL树需要理解二叉搜索树的基本结构，并加入平衡因子的维护与旋转操作。
AVL树节点设计
每个节点除了存储值外，还需要记录当前子树的高度，以便计算平衡因子（左子树高度减右子树高度）：
struct Node {
int data;
Node* left;
Node* right;
int height;
Node(int value) : data(value), left(nullptr), right(nullptr), height(1) {}};
高度初始化为1，因为单个节点的高度是1（不是0）。
立即学习“C++免费学习笔记（深入）”；
基本操作：获取高度与平衡因子
封装两个辅助函数用于判断是否失衡以及进行后续旋转：
int getHeight(Node* node) {
return node ? node->height : 0;
}
int getBalanceFactor(Node* node) {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
}
这两个函数会在插入和删除后频繁调用，用来决定是否需要旋转调整。
四种旋转操作
当某个节点的平衡因子大于1或小于-1时，就需要通过旋转恢复平衡。共四种情况：
右旋（LL型）
适用于左子树过高且新节点插入在左侧路径上：
Node* rotateRight(Node* y) {
Node* x = y->left;
Node* 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; // 新的根
}
左旋（RR型）
适用于右子树过高：
Node* rotateLeft(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y; // 新的根
}
左右双旋（LR型）
先对左孩子左旋，再对当前节点右旋：
Node* rotateLeftRight(Node* node) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
右左双旋（RL型）
先对右孩子右旋，再对当前节点左旋：
Node* rotateRightLeft(Node* node) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}
插入操作
插入逻辑类似BST，但在递归返回过程中更新高度并检查平衡性：
Node* insert(Node* root, int value) {
if (!root)
return new Node(value);
if (value < root->data)
root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);
else
return root; // 不允许重复键
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
int balance = getBalanceFactor(root);
// LL型
if (balance > 1 && value < root->left->data)
return rotateRight(root);
// RR型
if (balance < -1 && value > root->right->data)
return rotateLeft(root);
// LR型
if (balance > 1 && value > root->left->data)
return rotateLeftRight(root);
// RL型
if (balance < -1 && value < root->right->data)
return rotateRightLeft(root);
return root;}
删除操作
删除节点需处理三种情况（无子、一子、两子），找到中序后继替代值，然后递归删除：
Node* findMin(Node* root) {
while (root && root->left)
root = root->left;
return root;
}
Node remove(Node root, int value) {
if (!root)
return root;
if (value < root->data)
root->left = remove(root->left, value);
else if (value > root->data)
root->right = remove(root->right, value);
else {
if (!root->left || !root->right) {
Node* temp = root->left ? root->left : root->right;
delete root;
return temp;
} else {
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = remove(root->right, temp->data);
}
}
if (!root) return root;
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
int balance = getBalanceFactor(root);
// 同样四种旋转修复
if (balance > 1 && getBalanceFactor(root->left) >= 0)
return rotateRight(root);
if (balance < -1 && getBalanceFactor(root->right) <= 0)
return rotateLeft(root);
if (balance > 1 && getBalanceFactor(root->left) < 0)
return rotateLeftRight(root);
if (balance < -1 && getBalanceFactor(root->right) > 0)
return rotateRightLeft(root);
return root;}
完整使用示例
可以封装成类，并提供遍历接口验证结构正确性：
class AVLTree {
public:
Node* root;
AVLTree() : root(nullptr) {}
void insert(int value) { root = insert(root, value); }
void remove(int value) { root = remove(root, value); }
void inorder(Node* node) {
if (node) {
inorder(node->left);
cout << node->data << "(" << node->height << ") ";
inorder(node->right);
}
}
void printInorder() {
inorder(root);
cout << endl;
}};
测试代码：
int main() {
AVLTree tree;
tree.insert(10);
tree.insert(20);
tree.insert(5);
tree.insert(6);
tree.insert(15);
tree.insert(25);
tree.printInorder(); // 输出应有序且各节点高度合理
tree.remove(6);
tree.printInorder();
return 0;
}
基本上就这些。只要掌握旋转时机和方式，AVL树就能稳定运行。虽然现在STL中的set/map多用红黑树实现，但AVL作为经典平衡树仍是学习数据结构的重要一环。
