AVL树简介
AVL树是一种自平衡的二叉查找树(BST),由G.M. Adelson-Velsky和E.M. Landis在1962年提出。它的核心约束很简单:每个节点的左右子树高度差必须控制在1以内,这样插入、删除和查找的最坏情况都能维持在O(log N)。
平衡因子
每个节点维护一个_bf(平衡因子),计算方式为左子树高度减去右子树高度。
- 0:左右子树一样高
- 1:左子树比右子树高1
- -1:右子树比左子树高1
一旦平衡因子的绝对值达到2,树就失衡了,必须通过旋转来修复。
节点结构
节点结构除了键值对和左右孩子指针,还加了父指针_parent和_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;
AVLTreeNode(const pair<K, V>& kv)
: _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};
插入与平衡调整
插入仍然遵循二叉查找树的规则,但插入之后要沿着父链一路更新平衡因子,遇到失衡就旋转。
按BST规则插入新节点
先找到应该插入的位置。如果树空,新节点直接做根。否则,循环比较大小,直到指针为空。新节点挂上去后,更新父节点的平衡因子。
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);
cur->_parent = parent;
if (parent->_kv.first < kv.first) {
parent->_right = cur;
} else {
parent->_left = cur;
}




