AVL 树是一种自平衡二叉搜索树，通过维护节点平衡因子（左右子树高度差）不超过 1 来保证操作效率。详细阐述了 AVL 树的结构定义、插入与删除操作逻辑，重点讲解了四种旋转策略（左单旋、右单旋、左右双旋、右左双旋）以恢复树的平衡。内容涵盖平衡因子更新规则、失衡检测时机及具体的 C++ 代码实现，旨在帮助开发者深入理解 AVL 树的底层原理与维护机制。
AVL 树是由 Adelson-Velsky 和 Landis 发明的第一种自平衡二叉搜索树，它通过控制每个节点左右子树的高度差（称为）不超过 1，确保树的高度维持在对数级别。这种自平衡特性使得 AVL 树的查找、插入和删除操作的时间复杂度保持在 O(log N)，从而提升效率。
二叉搜索树结构：AVL 树是一种特殊的二叉搜索树，每个节点的平衡因子始终保持在 -1、0 或 1 之间。平衡因子：平衡因子定义为右子树高度减去左子树高度。若某个节点的平衡因子超出此范围，则需进行旋转以恢复平衡。
未平衡的二叉搜索树在最坏情况下可能退化成链表，导致操作时间复杂度增至 O(N)。AVL 树通过保持树的高度平衡，保证了查找、插入和删除操作的高效性。
template <class K, class V>
struct AVLTreeNode {
pair<K, V> _kv; // Key-Value 结构
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent; // 需要 parent 指针，后续更新平衡因子可以看到
int _bf; // 平衡因子
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:
// ...
private:
// ...
Node* _root = nullptr;
};
AVL 树的插入按照二叉搜索树的规则进行插入，但是会在不平衡的条件下进行旋转操作。也就是说，AVL 树的插入操作主要分为三个部分：找到插入位置、插入节点、更新平衡因子并旋转（如果需要）。
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
如果 AVL 树当前为空树，即 _root 为 nullptr，直接将新节点作为根节点插入，并结束操作。因为此时没有其他节点需要进行平衡因子的调整，所以插入结束。
Node* parent = nullptr;
Node* cur = _root;
// find insert place
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; // Duplicate key, insertion failed
}
}
在树中插入节点时，需要按照二叉搜索树的规则找到适当的位置：
cur）的键值（cur->_kv.first）与要插入的值（kv.first）进行比较。通过遍历，cur 最终会指向 nullptr，即找到了插入的位置，parent 指向插入节点的父节点。
cur = new Node(kv);
if (parent->_kv.first < kv.first) {
parent->_right = cur;
} else {
parent->_left = cur;
}
cur->_parent = parent;
找到插入位置后，新节点 cur 将被创建并插入到父节点 parent 的左子树或右子树中。此时新节点已经成功插入，但它可能会影响树的平衡，需要继续调整平衡因子。
while (parent) {
if (cur == parent->_left) {
parent->_bf--; // 插入左子树，平衡因子 -1
} else {
parent->_bf++; // 插入右子树，平衡因子 +1
}
if (parent->_bf == 0) {
break; // 如果平衡因子为 0，树高度未变，停止更新
} else if (parent->_bf == -1 || parent->_bf == 1) {
cur = parent;
parent = parent->_parent; // 继续向上更新平衡因子
} else if (parent->_bf == -2 || parent->_bf == 2) {
// 需要旋转
// ...
break;
} else {
assert(false); // 出现了异常情况
}
}
平衡因子的更新：更新原则平衡因⼦ = 右⼦树⾼度 - 左⼦树⾼度只有⼦树⾼度变化才会影响当前结点平衡因⼦。插⼊结点，会增加⾼度，所以新增结点在
parent的右⼦树，parent的平衡因⼦++，新增结点在 parent 的左⼦树，parent平衡因⼦--parent所在⼦树的⾼度是否变化决定了是否会继续往上更新更新停止条件更新后parent的平衡因⼦等于0，更新中 parent 的平衡因⼦变化为-1->0或者1->0，说明更新前parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会影响parent的⽗亲结点的平衡因⼦，更新结束。更新后parent的平衡因⼦等于1或-1，更新前更新中parent的平衡因⼦变化为0->1或者0->-1，说明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所在的⼦树符合平衡要求，但是⾼度增加了1，会影响parent的⽗亲结点的平衡因⼦，所以要继续向上更新。更新后 parent 的平衡因⼦等于2或-2，更新前更新中parent的平衡因⼦变化为1->2或者-1->-2，说明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：
parent ⼦树旋转平衡。parent ⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束。保持搜索树的规则通过降低旋转树的高度，让旋转的树从不平衡变为平衡
通过不同的情况，旋转分为四种：左单旋、右单旋、左右单旋、右左单旋。
右单旋用于修复左左失衡（LL 失衡），即插入的新节点位于左子树的左侧，导致该节点的左子树高度比右子树大 2。
通过右旋，可以将失衡的左子树提升到当前节点的根节点位置，将当前节点向右旋转，形成新的平衡状态。
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 将 subL 的右子树 subLR 链接为 parent 的左子树
parent->_left = subLR;
if (subLR) {
subLR->_parent = parent;
}
// 将 subL 提升为 parent 的父节点
Node* pParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
// 更新父节点指针，如果 parent 是根节点，则更新根节点
if (pParent == nullptr) {
_root = subL;
subL->_parent = nullptr;
} else {
if (pParent->_left == parent) {
pParent->_left = subL;
} else {
pParent->_right = subL;
}
subL->_parent = pParent;
}
// 调整平衡因子
parent->_bf = subL->_bf = 0;
}
将
parent的左子树（即subL）提升为新的根节点。将subL的右子树（即subLR，subL的右子树是parent左子树中最大的节点，对于右子树来说是最小的节点，所以用来做parent的左子树用来保持搜索树的规则）链接为parent的左子树。将subL的右子树设置为parent。如果parent是树的根节点，需要更新树的根节点为subL，否则，将subL链接到parent的父节点上。
左单旋用于修复右右失衡（RR 失衡），即插入的新节点位于右子树的右侧，导致该节点的右子树高度比左子树大 2。
通过左旋，可以将失衡的右子树提升到当前节点的根节点位置，将当前节点向左旋转，形成新的平衡状态。
void RotateL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
// 将 subR 的左子树 subRL 链接为 parent 的右子树
parent->_right = subRL;
if (subRL) {
subRL->_parent = parent;
}
// 将 subR 提升为 parent 的父节点
Node* pParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
// 更新父节点指针，如果 parent 是根节点，则更新根节点
if (pParent == nullptr) {
_root = subR;
subR->_parent = nullptr;
} else {
if (pParent->_left == parent) {
pParent->_left = subR;
} else {
pParent->_right = subR;
}
subR->_parent = pParent;
}
// 调整平衡因子
parent->_bf = subR->_bf = 0;
}
将
parent的右子树（即subR）提升为新的根节点。将subR的左子树（即subRL，subR的左子树是parent右子树中最小的节点，对于左子树来说是最大的节点，所以用来做parent的右子树用来保持搜索树的规则）链接为parent的右子树。将subR的左子树设置为parent。如果parent是树的根节点，需要更新树的根节点为subR，否则，将subR链接到parent的父节点上。
左右双旋用于修复左右失衡（LR 失衡），这种情况发生在插入的节点位于左子树的右侧，导致左子树比右子树高 2，但左子树的右子树比左子树的左子树高。这种情况下，仅仅进行一次右旋（RR 旋转）无法恢复平衡，必须先进行左旋（LL 旋转），再进行右旋。
subLR 节点（左子树的右子树）的平衡因子。旋转后，需要根据 subLR 的平衡因子来决定父节点、subL（左子树）和 subLR 的平衡因子如何调整：subLR 的平衡因子为 0，由 subLR 左子树右子树分给 parent 和 subL 的左右子树高度相同，则所有节点的平衡因子重置为 0。subLR 的平衡因子为 1，表示 subLR 的右子树会比左子树低 1，subLR 左子树会分配给 subL 作为右子树，此时 subL 左子树比分配的右子树高 1，所以 subL 的平衡因子应该更新为 -1，而右子树会分给 parent 作为左子树，两个子树高度相同，平衡因子为 0。subLR 的平衡因子为 -1，表示 subLR 的左子树比右子树低 1，subLR 左子树会分配给 subL 作为右子树，两个子树高度相同，subL 平衡因子更新为 0，而右子树会分给 parent 作为左子树，会比 parent 右子树低 1，所以 parent 的平衡因子应该更新为 1。void RotateLR(Node* parent) {
Node* subL = parent->_left; // 左子树
Node* subLR = subL->_right; // 左子树的右子树
int bf = subLR->_bf; // 记录旋转前 subLR 的平衡因子
// 第一步：对子树进行左旋
RotateL(parent->_left);
// 第二步：对当前节点进行右旋
RotateR(parent);
// 根据旋转后 subLR 的平衡因子更新平衡因子
if (bf == 0) {
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
} else if (bf == 1) {
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
} else if (bf == -1) {
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
} else {
assert(false); // 不应发生的情况
}
}
右左双旋用于修复右左失衡（RL 失衡），这种情况发生在插入的节点位于右子树的左侧，导致右子树比左子树高 2，但右子树的左子树比右子树的右子树高。类似于左右双旋，这种情况不能通过一次左旋解决，必须先进行右旋（RR 旋转），再进行左旋。
subRL（右子树的左子树）的平衡因子，旋转后根据 subRL 的平衡因子来调整父节点、subR 和 subRL 的平衡因子。void RotateRL(Node* parent) {
Node* subR = parent->_right; // 右子树
Node* subRL = subR->_left; // 右子树的左子树
int bf = subRL->_bf; // 记录旋转前 subRL 的平衡因子
// 第一步：对右子树进行右旋
RotateR(parent->_right);
// 第二步：对当前节点进行左旋
RotateL(parent);
// 根据旋转后 subRL 的平衡因子更新平衡因子
if (bf == 0) {
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
} else if (bf == 1) {
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
} else if (bf == -1) {
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
} else {
assert(false); // 不应发生的情况
}
}
AVL 树是自平衡的二叉搜索树，所以查找操作与普通的二叉搜索树一致。由于 AVL 树保持了平衡，它的查找时间复杂度为 O(log N)，其中 N 是节点的数量。每次查找都是通过比较键值，沿着树的一条路径从根节点到叶节点。
查找操作从根节点开始，比较目标键值（key）与当前节点的键值（cur->_kv.first）：
nullptr，说明树中没有该键值，返回 nullptr。Node* Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_kv.first < key) {
cur = cur->_right; // 查找右子树
} else if (cur->_kv.first > key) {
cur = cur->_left; // 查找左子树
} else {
return cur; // 找到目标节点
}
}
return nullptr; // 未找到，返回空指针
}
AVL 树的核心特性是自平衡。为了确保树的平衡，每个节点的左右子树高度差不能超过 1。因此，平衡检测的目的是检查每个节点的左右子树高度差是否满足这个条件，并验证节点的平衡因子是否正确。
-1, 0, 1。int _Height(Node* root) {
if (root == nullptr) {
return 0; // 空树的高度为 0
}
int leftHeight = _Height(root->_left); // 计算左子树的高度
int rightHeight = _Height(root->_right); // 计算右子树的高度
return (leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1); // 返回更大的子树高度加 1
}
bool _IsBalanceTree(Node* root) {
// 空树也是 AVL 树
if (root == nullptr) {
return true;
}
// 计算左右子树的高度
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;
// 检查平衡因子是否正确，左右子树高度差是否超出范围
if (abs(diff) >= 2) {
cout << root->_kv.first << " 高度差异常" << endl;
return false;
}
if (root->_bf != diff) {
cout << root->_kv.first << " 平衡因子异常" << endl;
return false;
}
// 递归检查左右子树是否平衡
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
AVL 树的核心在于保持树的平衡性，即每个节点的平衡因子（左右子树高度差）保持在 -1、0、1 之间。当插入或删除节点后，树可能失衡，此时需要通过旋转来恢复平衡。具体的旋转方式取决于失衡的位置和失衡的类型。
在插入节点后，从插入位置沿着路径向上更新每个祖先节点的平衡因子：
parent->_bf--，平衡因子减 1。parent->_bf++，平衡因子加 1。更新的过程中有三种可能情况：
当检测到某个节点的平衡因子为 2 或 -2 时，表示该节点失衡。失衡分为四种类型，具体的旋转操作取决于失衡的子树是左子树还是右子树，以及失衡的方向是左左失衡（LL）、右右失衡（RR）、左右失衡（LR） 还是 右左失衡（RL）。
if (parent->_bf == -2 && cur->_bf == -1) {
RotateR(parent);
}
插入前： 10
/
5
/
2
插入 1 后，导致 10 左左失衡。
右旋后： 5
/ \
2 10
/
1
if (parent->_bf == 2 && cur->_bf == 1) {
RotateL(parent);
}
插入前： 10
\
15
\
20
插入 25 后，导致 10 右右失衡。
左旋后： 15
/ \
10 20
\
25
if (parent->_bf == -2 && cur->_bf == 1) {
RotateLR(parent);
}
插入前： 10
/
5
\
8
插入 9 后，导致 10 左右失衡。
左右双旋后： 8
/ \
5 10
/
9
if (parent->_bf == 2 && cur->_bf == -1) {
RotateRL(parent);
}
插入前： 10
\
20
/
15
插入 12 后，导致 10 右左失衡。
右左双旋后： 15
/ \
10 20
/
12
在代码中，旋转的具体逻辑如下：
while (parent) {
if (cur == parent->_left) {
parent->_bf--; // 插入在左子树，平衡因子减 1
} else {
parent->_bf++; // 插入在右子树，平衡因子加 1
}
if (parent->_bf == 0) {
break; // 平衡因子为 0，树的高度没有变化，停止更新
} 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) {
RotateR(parent); // 左左失衡 -> 右单旋
} else if (parent->_bf == 2 && cur->_bf == 1) {
RotateL(parent); // 右右失衡 -> 左单旋
} else if (parent->_bf == -2 && cur->_bf == 1) {
RotateLR(parent); // 左右失衡 -> 左右双旋
} else if (parent->_bf == 2 && cur->_bf == -1) {
RotateRL(parent); // 右左失衡 -> 右左双旋
} else {
assert(false); // 不应发生的情况
}
break;
} else {
assert(false); // 不应发生的情况
}
}
AVL 树节点的删除较为复杂，可以选择性理解
AVL 树节点的删除操作类似于二叉搜索树的删除，但需要额外维护 AVL 树的平衡性。当删除一个节点后，可能会导致 AVL 树失衡，因此在删除节点后需要通过更新平衡因子并执行旋转来恢复平衡。
如果删除的节点是叶子节点，那么直接删除该节点，不需要其他调整。然后从父节点开始，检查树是否失衡。
如果删除的节点只有一个子节点（左子节点或右子节点），那么直接用该子节点替换要删除的节点。同样，从父节点开始更新平衡因子并检查是否需要旋转。
如果删除的节点有两个子节点，则需要找到该节点的前驱节点或后继节点，并用该前驱或后继节点的值替换要删除的节点。然后，递归删除前驱或后继节点，这样问题就转化为删除一个有一个子节点或没有子节点的节点。
在删除节点后，树可能失衡，原因是删除节点后会减小某些子树的高度，从而导致其祖先节点的平衡因子发生变化。因此，需要从删除节点的父节点开始，逐级更新平衡因子，并根据情况执行旋转操作。
和插入操作类似，删除节点后如果某个节点的平衡因子变为 2 或 -2，需要通过旋转来恢复平衡。常见的失衡和旋转情况有：
以下是一个 AVL 树删除节点的简化实现。
template <class K, class V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
public:
bool Erase(const K& key) {
Node* parent = nullptr;
Node* cur = _root;
// 1. 查找要删除的节点
while (cur) {
if (cur->_kv.first < key) {
parent = cur;
cur = cur->_right;
} else if (cur->_kv.first > key) {
parent = cur;
cur = cur->_left;
} else {
break;
}
}
if (!cur) {
return false; // 节点不存在
}
// 2. 执行删除操作
// 如果有两个子节点
if (cur->_left && cur->_right) {
Node* replace = cur->_left;
parent = cur;
// 找到左子树的最右节点（即前驱节点）
while (replace->_right) {
parent = replace;
replace = replace->_right;
}
// 用前驱节点替换当前节点的值
cur->_kv = replace->_kv;
cur = replace;
}
// 只有一个子节点或没有子节点
Node* subTree = cur->_left ? cur->_left : cur->_right;
if (!parent) {
// 删除的是根节点
_root = subTree;
} else {
if (parent->_left == cur) {
parent->_left = subTree;
} else {
parent->_right = subTree;
}
if (subTree) {
subTree->_parent = parent;
}
}
// 删除节点
delete cur;
// 3. 更新平衡因子并旋转
while (parent) {
if (subTree == parent->_left) {
parent->_bf++;
} else {
parent->_bf--;
}
if (parent->_bf == 1 || parent->_bf == -1) {
break; // 高度没有发生变化，停止调整
}
if (parent->_bf == 2 || parent->_bf == -2) {
// 旋转
Rebalance(parent);
}
subTree = parent;
parent = parent->_parent;
}
return true;
}
private:
// 恢复平衡的方法，根据不同情况选择旋转方式
void Rebalance(Node* parent) {
if (parent->_bf == 2) {
if (parent->_right->_bf >= 0) {
RotateL(parent); // LL 旋转
} else {
RotateRL(parent); // RL 旋转
}
} else if (parent->_bf == -2) {
if (parent->_left->_bf <= 0) {
RotateR(parent); // RR 旋转
} else {
RotateLR(parent); // LR 旋转
}
}
}
// 左旋，右旋，左右双旋，右左双旋函数省略
};
与插入操作类似，删除节点后如果某个节点的平衡因子变为 2 或 -2，则需要进行旋转：
通过这些旋转操作，AVL 树可以在删除节点后保持平衡，确保树的高度始终维持在对数级别 ( O(log N) )。
2 或 -2 时，通过适当的旋转恢复树的平衡。AVL 树的删除比插入稍微复杂，因为可能涉及前驱节点或后继节点的替换，以及删除后的平衡恢复。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online