什么是 AVL 树
AVL 树是自平衡二叉搜索树：它保证任意节点的左右子树高度差（平衡因子）绝对值不超过 1，从而把查找、插入、删除的复杂度稳定在 O(log n)，避免普通 BST 退化成链表的极端情况。
核心原理：平衡因子与旋转
节点平衡因子 = 左子树高度 − 右子树高度。插入或删除打破平衡（|因子| > 1）时，用四种旋转恢复：
- LL（右旋）：左子树偏高且”左左”失衡，对当前节点右旋；
- RR（左旋）：右子树偏高且”右右”失衡，对当前节点左旋；
- LR（先左后右双旋）：先对左子节点左旋，再对当前节点右旋；
- RL（先右后左双旋）：先对右子节点右旋，再对当前节点左旋。
C++ 实现
#include <iostream>
#include <algorithm>
struct AVLNode {
int key;
AVLNode* left;
AVLNode* right;
int height;
AVLNode(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};
class AVLTree {
private:
AVLNode* root = nullptr;
int height(AVLNode* n) { return n ? n->height : 0; }
int balance(AVLNode* n) { return n ? height(n->left) - height(n->right) : 0; }
// 右旋（LL）
AVLNode* rightRotate(AVLNode* y) {
AVLNode* x = y->left;
AVLNode* T2 = x->right;
x->right = y;
y->left = T2;
y->height = std::max(height(y->left), height(y->right)) + 1;
x->height = std::max(height(x->left), height(x->right)) + 1;
return x;
}
// 左旋（RR）
AVLNode* leftRotate(AVLNode* x) {
AVLNode* y = x->right;
AVLNode* T2 = y->left;
y->left = x;
x->right = T2;
x->height = std::max(height(x->left), height(x->right)) + 1;
y->height = std::max(height(y->left), height(y->right)) + 1;
return y;
}
AVLNode* insert(AVLNode* node, int key) {
if (!node) return new AVLNode(key);
if (key key) node->left = insert(node->left, key);
else if (key > node->key) node->right = insert(node->right, key);
else return node; // 不允许重复键
node->height = 1 + std::max(height(node->left), height(node->right));
int b = balance(node);
if (b > 1 && key left->key) return rightRotate(node); // LL
if (b node->right->key) return leftRotate(node); // RR
if (b > 1 && key > node->left->key) { // LR
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (b < -1 && key right->key) { // RL
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
AVLNode* minNode(AVLNode* n) {
while (n->left) n = n->left;
return n;
}
AVLNode* remove(AVLNode* root, int key) {
if (!root) return root;
if (key key) root->left = remove(root->left, key);
else if (key > root->key) root->right = remove(root->right, key);
else {
if (!root->left || !root->right) { // 0 或 1 个子节点
AVLNode* tmp = root->left ? root->left : root->right;
delete root;
return tmp;
}
// 两个子节点：用中序后继顶替
AVLNode* succ = minNode(root->right);
root->key = succ->key;
root->right = remove(root->right, succ->key);
}
if (!root) return root;
root->height = 1 + std::max(height(root->left), height(root->right));
int b = balance(root);
if (b > 1 && balance(root->left) >= 0) return rightRotate(root); // LL
if (b > 1 && balance(root->left) left = leftRotate(root->left);
return rightRotate(root);
}
if (b right) <= 0) return leftRotate(root); // RR
if (b right) > 0) { // RL
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
void inorder(AVLNode* n) {
if (!n) return;
inorder(n->left);
std::cout <key <right);
}
public:
void insert(int k) { root = insert(root, k); }
void remove(int k) { root = remove(root, k); }
bool search(int k) {
AVLNode* cur = root;
while (cur) {
if (k key) cur = cur->left;
else if (k > cur->key) cur = cur->right;
else return true;
}
return false;
}
void printInorder() { inorder(root); std::cout << std::endl; }
};
int main() {
AVLTree t;
for (int k : {10, 20, 30, 40, 50, 25}) t.insert(k);
t.printInorder(); // 升序
t.remove(20);
t.printInorder();
std::cout << (t.search(30) ? "found 30" : "not found") << std::endl;
return 0;
}
实现要点
- 每个节点额外存
height，旋转后先更新子树高度再更新自己； - 插入用”键值与左右子节点比较”判断失衡类型，删除则用”子节点的平衡因子”判断——两种场景的四种情况判断条件不同，容易写混；
- 删除有两个子节点时用中序后继顶替，等价于删除后继节点，然后照常回溯平衡；
- 递归插入/删除后都要先更新高度再检查平衡，顺序不能反。
复杂度与对比
- 查找/插入/删除：O(log n)；空间 O(n)。
- 相比红黑树：AVL 平衡更严格、查找更快，但插入删除的旋转更多；红黑树牺牲一点查找性能换取更少的旋转。工程上（如 C++ std::map、Linux 内核）多用红黑树，AVL 更常用于教学与需要频繁查询的场景。