AVL 树（以发明者 Adelson-Velsky 和 Landis 命名）是计算机科学中第一种自平衡二叉搜索树。
它在 BST 的基础上增加了一个硬性条件：任何节点的两个子树的高度差（平衡因子）最多为 1。
1. 核心概念：平衡因子 (Balance Factor)
对于 AVL 树中的任何节点 $N$，其平衡因子定义为：
$$BF(N) = Height(LeftSubtree) - Height(RightSubtree)$$
- $BF = 0$：左右完全平衡。
- $BF = 1$ 或 $-1$：轻微倾斜，但仍被视为平衡。
- $BF > 1$ 或 $< -1$：失去了平衡，需要通过旋转来修复。
2. 四种旋转方式
当我们在 AVL 树中插入或删除节点导致失衡时，会根据失衡的形态采取四种不同的旋转操作：
1. 左左型 (LL) -> 右旋 (Right Rotation)
插入点位于左子树的左侧。
2. 右右型 (RR) -> 左旋 (Left Rotation)
插入点位于右子树的右侧。
3. 左右型 (LR) -> 先左旋再右旋
插入点位于左子树的右侧。先对左子树进行左旋，变成 LL 型，再进行一次右旋。
4. 右左型 (RL) -> 先右旋再左旋
插入点位于右子树的左侧。先对右子树进行右旋，变成 RR 型，再进行一次左旋。
3. AVL 树的 C++ 实现
AVL 树的代码比普通 BST 复杂，因为每次插入后都需要更新高度并回溯检查平衡。
C++
#include <iostream>
#include <algorithm>using namespace std;struct Node {int val;int height; // 记录高度以计算平衡因子Node *left, *right;Node(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
};class AVLTree {
public:Node* root = nullptr;// 获取高度的辅助函数int getHeight(Node* n) { return n ? n->height : 0; }// 计算平衡因子int getBalance(Node* n) { return n ? getHeight(n->left) - getHeight(n->right) : 0; }// 右旋转 (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;}// 递归插入Node* insert(Node* node, int val) {if (!node) return new Node(val);if (val < node->val) node->left = insert(node->left, val);else if (val > node->val) node->right = insert(node->right, val);else return node; // 不允许重复值// 1. 更新当前节点高度node->height = 1 + max(getHeight(node->left), getHeight(node->right));// 2. 获取平衡因子并检查是否失衡int balance = getBalance(node);// LL 情况if (balance > 1 && val < node->left->val) return rotateRight(node);// RR 情况if (balance < -1 && val > node->right->val) return rotateLeft(node);// LR 情况if (balance > 1 && val > node->left->val) {node->left = rotateLeft(node->left);return rotateRight(node);}// RL 情况if (balance < -1 && val < node->right->val) {node->right = rotateRight(node->right);return rotateLeft(node);}return node;}void inorder(Node* n) {if (!n) return;inorder(n->left);cout << n->val << " ";inorder(n->right);}
};
4. AVL 树 vs 红黑树 (Red-Black Tree)
在实际应用中，你可能经常听到这两者的对比：
| 特性 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡程度 | 严格平衡 (高度差 $\le 1$) | 弱平衡 (最长路径不超最短两倍) |
| 查找性能 | 更好 (因为树更矮) | 稍逊 |
| 插入/删除性能 | 较慢 (可能涉及多次旋转) | 更好 (旋转次数少) |
| 适用场景 | 查找频繁、插入删除少的场景 | 插入删除频繁的场景 (如 C++ STL, Java HashMap) |