AVL 树核心详解
你是否曾在写算法时，用二叉搜索树（BST）存数据却遭遇'超时'暴击？明明理论复杂度是 O(logn)，偏偏插入一串有序数据后，树直接退化成链表，查询效率暴跌到 O(n)？这背后的元凶，正是 BST 无法自我平衡的结构性缺陷。而 AVL 树，就是为破解这个痛点而生的平衡大师。
它不仅是首个严格平衡的二叉搜索树，每一个设计细节都藏着精妙的逻辑：为什么平衡因子要选高度差≤1 而非高度相等？旋转操作看似复杂，实则是局部修复全局平衡的贪心策略。这篇内容我们将挖透 AVL 树的底层逻辑，从诞生的根源到旋转与平衡因子的本质，最终让你明白——AVL 树不仅是一种数据结构，更是一套用最小代价解决失衡问题的方法论。
AVL 树的概念
AVL 树是二叉平衡搜索树的一种（红黑树也是）。跟普通二叉搜索树的区别在于，极端场景下 BST 会退化成类似链表的结构，而 AVL 树则不会。
一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是 AVL 树。
- 左右子树高度之差（简称平衡因子）的绝对值不超过 1（即 -1、0 或 1）。
每个节点都有它的平衡因子。AVL 树增删查改的时间复杂度都是 O(logn)，其中 n 是元素个数。
AVL 树的模拟实现
虽然 AVL 树和红黑树在手撕代码中考察频率不如基础结构高，但理解其整体模拟实现的思想以及旋转的手撕过程非常关键。这里我们重点看 C++ 的实现细节。
节点结构与插入逻辑
首先定义节点，需要存储键值对、左右孩子指针、父指针以及平衡因子 _bf。
template<class K, class V>
struct AVLTreeNode {
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf; // 平衡因子 balance factor
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};
插入时的核心难点在于更新平衡因子和必要的旋转。插入完成后，我们需要自底向上更新祖先节点的平衡因子。
template<class K, class V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
} else if (cur->_kv.first > kv.first) {
parent = cur;
cur = cur->_left;
} else {
return false; // 重复元素不插入
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first) {
parent->_right = cur;
} else {
parent->_left = cur;
}
cur->_parent = parent;
// 更新平衡因子
while (parent) {
if (cur == parent->_left) {
parent->_bf--;
} else {
parent->_bf++;
}
if (parent->_bf == 0) {
// 更新结束，说明该子树高度未变，无需继续向上
break;
} else if (parent->_bf == 1 || parent->_bf == -1) {
// 继续往上更新，因为高度变了
cur = parent;
parent = parent->_parent;
} else if (parent->_bf == 2 || parent->_bf == -2) {
// 子树不平衡了，需要旋转
if (parent->_bf == 2 && cur->_bf == 1) {
RotateL(parent); // LL 型
} else if (parent->_bf == -2 && cur->_bf == -1) {
RotateR(parent); // RR 型
} else if (parent->_bf == 2 && cur->_bf == -1) {
RotateRL(parent); // RL 型
} else if (parent->_bf == -2 && cur->_bf == 1) {
RotateLR(parent); // LR 型
}
break;
} else {
assert(false); // 防止逻辑错误
}
}
return true;
}
关于平衡因子的更新
在插入过程中，平衡因子的更新遵循以下规律：
- 新增节点在左，parent 平衡因子减减。
- 新增节点在右，parent 平衡因子加加。
- 更新后 parent 平衡因子等于 0，祖先的平衡因子不用动了，更新结束。
- 更新后 parent 平衡因子等于 1 或 -1，祖先平衡因子要动，依旧按前两点规则。
- 更新后 parent 平衡因子等于 2 或 -2，要对 parent 所在子树进行旋转，之后就更新结束了。
- 如果更新到根节点还没结束，也停止。
旋转操作详解
旋转时要确保始终是搜索树。AVL 树的旋转分为四种情况，判断依据是新节点插入的位置相对于不平衡点形成的路径形状。
1. 左旋 (RotateL)
新节点插入较高右子树的右侧（RR 型）。把 cur 的左节点接到 parent 的右边，然后把 parent 接到 cur 的左边。
void RotateL(Node* parent) {
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
if (curleft) curleft->_parent = parent;
cur->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = cur;
if (parent == _root) {
_root = cur;
cur->_parent = nullptr;
} else {
if (ppnode->_left == parent) {
ppnode->_left = cur;
} else {
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
// 单旋后，平衡因子通常归零
parent->_bf = cur->_bf = 0;
}
2. 右旋 (RotateR)
新节点插入较高左子树的左侧（LL 型）。把 cur 的右节点接到 parent 的左边，然后把 parent 接到 cur 的右边。
void RotateR(Node* parent) {
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright;
if (curright) curright->_parent = parent;
Node* ppnode = parent->_parent;
cur->_right = parent;
parent->_parent = cur;
if (ppnode == nullptr) {
_root = cur;
cur->_parent = nullptr;
} else {
if (ppnode->_left == parent) {
ppnode->_left = cur;
} else {
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
parent->_bf = cur->_bf = 0;
}
3. 双旋 (RotateLR & RotateRL) 当插入位置形成折线时需要双旋。例如新节点插入较高左子树的右侧（LR 型），需要先左旋再右旋。
// 先左旋再右旋
void RotateLR(Node* parent) {
Node* cur = parent->_left;
Node* curright = cur->_right;
int bf = curright->_bf;
RotateL(parent->_left);
RotateR(parent);
// 双旋后平衡因子需根据插入位置调整
if (bf == 0) {
parent->_bf = 0; cur->_bf = 0; curright->_bf = 0;
} else if (bf == -1) {
parent->_bf = 1; cur->_bf = 0; curright->_bf = 0;
} else if (bf == 1) {
parent->_bf = 0; cur->_bf = -1; curright->_bf = 0;
}
}
// 先右旋再左旋
void RotateRL(Node* parent) {
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0) {
cur->_bf = 0; curleft->_bf = 0; parent->_bf = 0;
} else if (bf == 1) {
cur->_bf = 0; curleft->_bf = 0; parent->_bf = -1;
} else if (bf == -1) {
cur->_bf = 1; curleft->_bf = 0; parent->_bf = 0;
}
}
快速判断旋转类型：
- 沿着
cur点向右偏的直线 -> 右旋 - 沿着
cur点向左偏的直线 -> 左旋 cur在最左边的折线 -> 先左旋再右旋cur在最右边的折线 -> 先右旋再左旋
AVL 树的删除
删除操作的步骤与插入类似，但规则有所不同：
- 按搜索树的规则查找并删除节点。
- 更新平衡因子。
- 出现异常（平衡因子变为 ±2）时进行旋转。
注意： 这里的规则跟插入的时候不一样。删除时，如果节点的平衡因子更新为 ±1 就停止（因为高度没变），为 0 的话才向上走（因为高度降低了）。异常之后旋转的条件依然是平衡因子为 ±2 时处理。
AVL 树的验证
如何验证你写的 AVL 树是否正确？不能仅依赖平衡因子，因为可能更新平衡因子的逻辑本身就有 BUG。也不能仅靠中序遍历有序来证明，那只能说明它是二叉搜索树。
最稳妥的方式是计算实际高度并与平衡因子对比。
int Height(Node* root) {
if (root == nullptr) return 0;
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool IsBalance(Node* root) {
if (root == nullptr) return true;
int leftHight = Height(root->_left);
int rightHight = Height(root->_right);
if (abs(rightHight - leftHight) != abs(root->_bf)) {
cout << "平衡因子异常:" << root->_kv.first << endl;
return false;
}
return abs(rightHight - leftHight) < 2 &&
IsBalance(root->_left) &&
IsBalance(root->_right);
}
思考与练习
现有一棵无重复关键字的平衡二叉树（AVL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是：
A. 根结点的度一定为 2 B. 树中最小元素一定是叶结点 C. 最后插入的元素一定是叶结点 D. 树中最大元素一定是无左子树
解析： 选 D。因为是降序序列，说明是反序的中序遍历（右->根->左），或者理解为树的结构使得最大值在左侧路径的最末端。对于 AVL 树，最大元素一定没有右子树（如果是升序），这里是降序，意味着最大元素在左子树的最深处且无左子树。具体取决于中序遍历的定义方向，但通常最大元素在无左子树的情况下更容易被访问到（视遍历顺序而定）。此题主要考察对树结构的理解，C 选项错在插入后可能会旋转导致原叶子变成非叶子。