前言
AVL 树是最早被提出的自平衡二叉搜索树，由 Adelson-Velsky 和 Landis 在 1962 年发表。它在普通二叉搜索树的基础上增加一条约束：任意节点的左右子树高度差不超过 1。每次插入或删除后，如果某条路径上的节点失衡，就通过旋转把它调整回来，从而保证树高始终是 O(log n)。
常见误解有三个。第一，把空树的高度定义成 -1 和 0 混用。两种约定本身都可以，但必须在整份代码里统一，否则平衡因子会整体偏移 1，旋转条件永远不成立或永远成立。第二，以为插入只需要在根节点检查平衡。失衡可能发生在从插入点到根的整条路径上，必须沿着递归返回的路径逐层更新高度并重平衡。第三，以为 AVL 树和红黑树没有区别。两者都保持 O(log n)，但 AVL 对平衡的要求更严格，查找路径更短，插入删除时可能需要更多次旋转；红黑树放松了平衡，写操作通常更省调整。
本文实现 AVL 树的插入部分，包括四种旋转和平衡因子维护，并给出中序遍历与平衡性检查。示例以 C++17 为准。删除操作的思路会在文中说明，但代码只保留插入，避免篇幅失控。
一、节点、高度与平衡因子
节点保存键、高度和两个子指针。高度定义为「从该节点到最远叶子的边数加一」，空节点高度为 0，叶子高度为 1。这个约定下，节点高度等于左右孩子高度的较大值加一。
平衡因子（balance factor）定义为左子树高度减右子树高度。AVL 要求每个节点的平衡因子只能是 -1、0 或 1。大于 1 说明左边过高，小于 -1 说明右边过高。
高度必须缓存在节点里，而不是每次递归计算。如果每次求高度都遍历子树，单次插入的代价会从 O(log n) 退化到 O(n)。缓存的代价是每次结构变化后要更新，更新顺序错了会导致平衡因子基于过期数据计算，旋转方向可能选错。
| 量 | 定义 | 空节点 | 叶子 |
|---|
| 高度 | 到最远叶子的边数加一 | 0 | 1 |
| 平衡因子 | 左高减右高 | 0 | 0 |
| 允许范围 | 平衡因子的绝对值不超过 1 | — | — |
二、四种失衡与旋转
插入导致失衡时，从失衡节点往下看，新节点所在的方向有四种组合：
| 类型 | 失衡节点的平衡因子 | 左孩子/右孩子的平衡因子 | 调整方式 |
|---|
| LL | 大于 1 | 左孩子不小于 0 | 对失衡节点右旋一次 |
| LR | 大于 1 | 左孩子小于 0 | 先对左孩子左旋，再对失衡节点右旋 |
| RR | 小于 -1 | 右孩子不大于 0 | 对失衡节点左旋一次 |
| RL | 小于 -1 | 右孩子大于 0 | 先对右孩子右旋，再对失衡节点左旋 |
右旋（rotate right）以失衡节点 y 为轴，把它的左孩子 x 提上来：x 的右子树变成 y 的左子树，y 变成 x 的右孩子。左旋是镜像操作。旋转只改变三条指针，不搬移节点，代价是常数时间。
旋转完成后必须更新高度，而且顺序不能反。以右旋为例，y 下沉后成为 x 的孩子，y 的高度依赖它的新孩子，所以要先更新 y，再更新 x。反过来先更新 x 时，x 的高度还没算上 y 的最终高度，结果偏小。
LR 和 RL 是「双旋」：先对孩子的方向做一次单旋，把折线形变成直线形，再对失衡节点做一次单旋。只做一次单旋无法解决折线形失衡，这是实现中最常见的错误之一。
三、插入与重平衡
插入沿用二叉搜索树的递归框架：比较键，往左或往右递归，遇到空位创建节点。区别在于递归返回后不能直接返回当前节点，而要先把当前节点的高度更新，再检查平衡因子，必要时旋转，最后返回新的子树根。
由于旋转可能改变子树的根，父节点必须用返回值重新接上孩子。写成insert(n->left, key);而忽略返回值，旋转后的新根就丢了，树会被破坏。正确写法是n->left = insert(n->left, key);。
重复键的处理要事先约定。本文选择忽略重复插入，直接返回原节点。也可以在每个节点上增加计数，或者允许重复键放到右子树；不同约定影响查找和删除的语义，但都必须保持一致。
删除比插入复杂。删除节点后，要从被删除位置一路向上重平衡；被删节点有两个孩子时，通常用中序后继（右子树的最小节点）替换它的键，再删除后继。后继节点也可能触发失衡，旋转的四种情况与插入相同，但判断条件要覆盖孩子平衡因子为 0 的情形。本文不展开删除代码，实现时应当以标准教材或权威资料为准。
四、完整示例
// 适用于 C++17
#include <algorithm>
#include <iostream>
struct Node {
int key;
int height;
Node* left;
Node* right;
explicit Node(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};
class AVLTree {
public:
AVLTree() = default;
~AVLTree() { destroy(root_); }
AVLTree(const AVLTree&) = delete;
AVLTree& operator=(const AVLTree&) = delete;
void insert(int key) { root_ = insert(root_, key); }
void printInOrder() const {
print(root_);
std::cout << '\n';
}
int height() const { return height(root_); }
bool balanced() const { return balanced(root_); }
private:
static int height(const Node* n) {
return n == nullptr ? 0 : n->height;
}
static void update(Node* n) {
n->height = 1 + std::max(height(n->left), height(n->right));
}
static int balanceFactor(const Node* n) {
return n == nullptr ? 0 : height(n->left) - height(n->right);
}
static Node* rotateRight(Node* y) {
Node* x = y->left;
Node* middle = x->right;
x->right = y;
y->left = middle;
update(y); // 先更新下沉的节点
update(x); // 再更新新的子树根
return x;
}
static Node* rotateLeft(Node* x) {
Node* y = x->right;
Node* middle = y->left;
y->left = x;
x->right = middle;
update(x);
update(y);
return y;
}
static Node* rebalance(Node* n) {
update(n);
const int bf = balanceFactor(n);
if (bf > 1) {
if (balanceFactor(n->left) < 0) {
n->left = rotateLeft(n->left); // LR
}
return rotateRight(n); // LL
}
if (bf < -1) {
if (balanceFactor(n->right) > 0) {
n->right = rotateRight(n->right); // RL
}
return rotateLeft(n); // RR
}
return n;
}
static Node* insert(Node* n, int key) {
if (n == nullptr) {
return new Node(key);
}
if (key < n->key) {
n->left = insert(n->left, key);
} else if (key > n->key) {
n->right = insert(n->right, key);
} else {
return n; // 重复键忽略
}
return rebalance(n);
}
static void print(const Node* n) {
if (n == nullptr) return;
print(n->left);
std::cout << n->key << ' ';
print(n->right);
}
static bool balanced(const Node* n) {
if (n == nullptr) return true;
const int diff = height(n->left) - height(n->right);
if (diff < -1 || diff > 1) return false;
return balanced(n->left) && balanced(n->right);
}
static void destroy(Node* n) {
if (n == nullptr) return;
destroy(n->left);
destroy(n->right);
delete n;
}
Node* root_ = nullptr;
};
int main() {
AVLTree tree;
for (int key : {30, 20, 10, 25, 28, 27, 5, 40, 50}) {
tree.insert(key);
}
tree.printInOrder();
std::cout << "height=" << tree.height() << '\n';
std::cout << std::boolalpha << tree.balanced() << '\n';
return 0;
}推演插入序列。先插入 30、20、10，此时 30 的平衡因子为 2，属于 LL，对 30 右旋一次，20 成为根，10 和 30 分别是左右孩子。继续插入 25、28，28 挂在 25 的右边，25 所在子树出现 LR 形状，先对 25 左旋，再对 20 右旋（实际失衡点要沿路径判断），28 被提到该子树的根。接着插入 27，触发新的调整；最后插入 5、40、50，50 使 40 的平衡因子变成 -2，属于 RR，对 40 左旋一次。
中序遍历的结果应当是按升序排列的键，因为 AVL 树首先是一棵二叉搜索树，旋转不改变中序序列。height()返回根节点缓存的高度，balanced()递归检查每个节点的左右高度差，用于确认调整逻辑没有遗漏。
rotateRight里的middle是 x 的右子树。右旋之后，x 的右孩子变成 y，而 x 原来的右子树必须挂到 y 的左边，否则这部分节点会丢失。左旋同理。这两条「转移子树」的语句是旋转正确性的关键，不能省略。
五、复杂度与取舍
AVL 树的查找、插入、删除都是 O(log n)，因为树高被限制在约 1.44 log(n) 的量级。每个节点额外保存一个int高度，空间开销是常数。
与红黑树相比，AVL 的平衡更严格，查找时经过的节点更少；但插入和删除后可能需要沿路径做更多次旋转，写操作的成本更高。读多写少的场景更适合 AVL，读写均衡或写操作频繁的场景，红黑树（例如std::map的常见实现）通常更合适。
实现上，递归写法简洁，但树很深时会有栈溢出风险；AVL 的树高是对数级，正常数据量下问题不大。析构函数是递归的，对于极端深的树同样要注意；如果需要处理不可信输入，应限制树高或改用迭代式释放。
常见坑点
坑点一：空节点高度在代码里前后不一致。
❌ 一处按 -1 处理，另一处按 0 处理，平衡因子整体偏移。
✅ 全文统一用空节点高度 0、叶子高度 1，或统一用 -1 和 0。
坑点二：旋转后高度更新顺序反了。
❌ 先update(x)再update(y)，x 的高度基于 y 的旧值计算。
✅ 右旋先更新 y，再更新 x；左旋先更新 x，再更新 y。
坑点三：LR/RL 只做单旋。
❌ 左孩子右重时直接右旋，折线形没有拉直，旋转后仍然失衡。
✅ 先对孩子做反向单旋，再对失衡节点做同向单旋。
坑点四：插入后忽略递归返回值。
❌insert(n->left, key);，旋转产生的新子树根没有接回父节点。
✅n->left = insert(n->left, key);。
坑点五：只在根节点检查平衡。
❌ 插入后只判断root_的平衡因子，路径中间的失衡被漏掉。
✅ 在递归返回的每一层都更新高度并调用重平衡。
坑点六：平衡因子的符号定义反了。
❌ 用右高减左高，却按左高减右高的条件写旋转分支。
✅ 明确定义为左高减右高，并让判断条件与定义一致。
坑点七：重复键处理不一致。
❌ 插入时允许重复，查找时假设唯一，删除时只删一个。
✅ 明确约定忽略、计数或放到某一侧，并让所有操作遵守。
坑点八：以为 AVL 在任何场景都比红黑树好。
❌ 写操作频繁的系统也一律选 AVL。
✅ 读多写少选 AVL；写多或需要与标准库容器行为接近时选红黑树。
总结
| 操作 | 复杂度 | 关键点 |
|---|
| 查找 | O(log n) | 树高受平衡因子约束 |
| 插入 | O(log n) | 递归返回时逐层更新与重平衡 |
| 删除 | O(log n) | 删除后沿路径重平衡，双孩子用后继替换 |
| 旋转 | O(1) | 转移子树、按顺序更新高度 |
| 空间 | O(n) | 每个节点多存一个高度 |
AVL 树的代码量不大，难点在于把「高度约定、平衡因子方向、旋转后的高度更新顺序、递归返回值」这四件事保持一致。任何一处不一致，树可能仍然能跑，但会悄悄失去平衡，最终退化成链表。写完插入后，用中序遍历检查有序性、用递归检查每个节点的平衡因子，是成本最低的自检方式。
