AVL 树原理与 C++ 实现详解
一、AVL 树的引入
二叉搜索树（BST）虽然提高了查找效率，但在数据有序或近似有序时，会退化为单支树，导致时间复杂度从 O(logN) 降至 O(N)。为了解决这个问题，前苏联科学家 G. M. Adelson-Velsky 和 E. M. Landis 提出了 AVL 树。
二、AVL 树的概念
AVL 树是最先发明的自平衡二叉搜索树。它是一颗空树，或者具备以下性质的二叉搜索树：
- 左右子树都是 AVL 树。
- 左右子树的高度差（平衡因子）的绝对值不超过 1。
平衡因子定义为右子树高度减去左子树高度。任何结点的平衡因子只能是 -1、0 或 1。当某个节点的平衡因子绝对值大于 1 时，就需要通过旋转来调整平衡。
为什么高度差不超过 1 而不是 0？ 要求高度差为 0 意味着完全平衡，这在节点数为偶数时很难做到（例如 2 个节点）。高度差允许为 1 能在保持高效查询的同时，降低维护成本。
三、AVL 树的实现
3.1 节点定义
AVL 树本质是 <key, value> 类型的平衡搜索二叉树。由于插入或删除会影响父节点的高度，进而影响平衡因子，因此通常采用三叉链结构（包含 _parent 指针），并引入 int _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; // 平衡因子，使用 int 而非 size_t 以支持负值
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};
3.2 插入逻辑
AVL 树的插入基于 BST 规则，但插入后需向上更新平衡因子。若发现不平衡（平衡因子绝对值为 2），则进行旋转。
更新平衡因子的原则：
- 新增节点在 parent 右子树，parent 平衡因子 ++。
- 新增节点在 parent 左子树，parent 平衡因子 --。
- 若 parent 平衡因子变为 0，说明该子树高度未变，停止更新。
- 若 parent 平衡因子绝对值为 1，说明高度增加，继续向上传递。
- 若 parent 平衡因子绝对值为 2，说明失衡，需旋转。
bool Insert(const pair<K, V>& kv) {
if (_root == ) {
_root = (kv);
;
}
Node* parent = ;
Node* cur = _root;
(cur) {
(cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
} (cur->_kv.first > kv.first) {
parent = cur;
cur = cur->_left;
} {
;
}
}
cur = (kv);
(parent->_kv.first < kv.first) {
parent->_right = cur;
} {
parent->_left = cur;
}
cur->_parent = parent;
(parent) {
(cur == parent->_right) {
parent->_bf++;
} (cur == parent->_left) {
parent->_bf--;
}
(parent->_bf == ) {
;
} (parent->_bf == || parent->_bf == ) {
cur = parent;
parent = parent->_parent;
} {
(parent->_bf == && cur->_bf == ) (parent);
(parent->_bf == && cur->_bf == ) (parent);
(parent->_bf == && cur->_bf == ) (parent);
(parent->_bf == && cur->_bf == ) (parent);
;
}
}
;
}
