AVL 树的概念
二叉搜索树虽然能提升查找效率，但如果数据有序或接近有序，它会退化为单支树，查找效率降至线性。为了解决这个问题，1962 年两位俄罗斯数学家 G.M.Adelson-Velskii 和 E.M.Landis 提出了 AVL 树。
AVL 树是一种自平衡的二叉搜索树（BST）。它的核心性质是：每个结点的左右子树高度之差的绝对值不超过 1。这保证了树的高度始终保持在 O(log n)，从而维持高效的查找、插入和删除操作。
- 平衡因子（bf）：通常定义为左子树深度减去右子树深度。在本实现中，为了配合代码逻辑，我们采用
右子树高度 - 左子树高度的定义方式。 - 自平衡机制：当插入或删除节点导致平衡因子绝对值超过 1 时，通过旋转操作（单旋或双旋）重新调整结构。
如果一棵二叉搜索树满足上述高度平衡条件，它就是 AVL 树。对于 n 个结点，其高度可保持在 O(log₂n)，搜索时间复杂度同样为 O(log₂n)。
AVL 树节点的定义
我们需要一个三叉链表的节点结构，包含左右子指针、父指针、平衡因子以及键值对。
template<class K, class V>
struct AVLTreeNode {
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf; // 平衡因子
pair<K, V> _kv;
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv) {}
};
AVL 树的插入
AVL 树的插入基于二叉搜索树，但多了平衡因子的更新和必要的旋转。流程大致分为三步：找到位置插入、更新祖先节点的平衡因子、若失衡则旋转。
插入新节点后，从该节点的父节点开始向上回溯，更新路径上所有祖先的平衡因子。根据当前节点是父节点的左孩子还是右孩子，平衡因子的增减方向不同。
- 若插入在左子树，父节点 bf 减 1。
- 若插入在右子树，父节点 bf 加 1。
更新过程中有三种情况：
- bf 变为 0：说明插入到了较矮的子树，现在两边平衡了。以该节点为根的子树高度未变，停止更新。
- bf 变为 ±1：说明子树高度变了，但整体仍平衡。继续向上更新祖父节点。
- bf 变为 ±2：说明失衡了，必须旋转。此时引起失衡的子节点（cur）的 bf 必定是 ±1，不可能是 0。
一旦旋转完成，子树高度恢复原状，无需再向上传播更新。
bool {
(_root == ) {
_root = (kv);
;
}
Node* parent = ;
Node* cur = _root;
(cur) {
(cur->_kv.first > kv.first) {
parent = cur;
cur = cur->_left;
} (cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
} {
;
}
}
cur = (kv);
(parent->_kv.first < kv.first) {
parent->_right = cur;
} {
parent->_left = cur;
}
cur->_parent = parent;
(parent) {
(cur == parent->_left) {
parent->_bf--;
} {
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);
}
;
}
}
;
}
