【C++】《再也不怕 AVL 树！图解高度平衡二叉搜索树：节点定义、插入、四大旋转、校验、删除与性能》---详解
上节我们介绍了map / multimap / set / multiset这几个容器，它们有一个共同特点：底层都是用二叉搜索树实现的。
不过，二叉搜索树有个明显的缺陷——当插入的数据有序或接近有序时，树结构会退化成单支树（看起来就像链表一样），这样一来，查找效率就从 O(logN) 降到了 O(N)。
所以，实际底层并没有直接使用普通的二叉搜索树，而是采用了平衡处理后的红黑树，确保各项操作都能保持较高的效率。
一.AVL树（高度平衡二叉搜索树）
1.概念：
我们都知道，二叉搜索树它虽然可以缩短查找的效率，但在这种如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率变得很低。
分两种的结果：
- 最优情况下，有 n 个结点的二叉搜索树为完全二叉树，查找效率为：O(log₂N)。
- 最坏情况下，有 n 个结点的二叉搜索树退化为单支树，查找效率为：O(N)。
因此，AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，他们在1962年的论⽂《An algorithm for the organization of information》中发表了它。他们提出了一个概念平衡因子，每个结点都有⼀个平衡因⼦，任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1，AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡，就像⼀个⻛向标⼀样。
总结：AVL树是最早发明的自平衡二叉搜索树，其特点是任意节点的左右子树高度差（平衡因子）的绝对值不超过1，从而保证了树的高度始终维持在 O(logN)，避免了二叉搜索树退化为链表的情况。
一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是 AVL 树。
- 左右子树高度之差（简称平衡因子）的绝对值不超过 1（-1/0/1）。
假如一棵二叉搜索树是高度平衡的，那么它就是 AVL 树。如果它有 n 个结点，对应的它其高度可保持在 O(log₂n)，搜索时间复杂度 O(log₂n)。
思考⼀下为什么AVL树是⾼度平衡搜索二叉树，要求⾼度差不超过1，⽽不是⾼度差是0呢？0不是更好的平衡吗？
画画图分析我们发现，不是不想这样设计，⽽是有些情况是做不到⾼度差是0的。比如⼀棵树是2个结点，4个结点等情况下，⾼度差最好就是1，⽆法做到⾼度差是0
同时：AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在 logN ，那么增删查改的效率也可以控制在 O(logN) ，相⽐⼆叉搜索树有了本质的提升。
2.AVL 树节点的定义
AVL树的节点是一个三叉链结构，除了包含指向左右孩子的指针外，还多了一个指向其父节点的指针。数据域存储的是键值对，即
pair对象。此外，每个节点还引入了一个平衡因子（bf，即 balance factor），用来记录当前节点的平衡状态，判断是否需要进行旋转调整。
// AVL树节点的定义（KV模型）
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<T>* _left; // 该节点的左孩子
AVLTreeNode<T>* _right; // 该节点的右孩子
AVLTreeNode<T>* _parent; // 该节点的双亲指针
pair<K, V> _kv; // 键值对
int _bf; // 平衡因子= 右子树高度-左子树高度
// 构造函数
AVLTreeNode(const pari<K, V>& kv)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};
// AVL树的定义（KV模型）
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
// 成员函数
......
private:
Node* _root;
}3.AVL树的插入
AVL树插⼊⼀个值的大概过程：
1. 插入⼀个值按二叉搜索树规则进行插入。
2. 新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦所以更新从新增结点->根结点路径上的平衡因⼦，实际中最坏情况下要更新到根，有些情况更新到中间就可以停⽌了，具体情况我们下⾯再详细分析。
3. 更新平衡因子过程中没有出现问题，则插⼊结束
4. 更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树的高度，不会再影响上⼀层，所以插入结束。
// 插入节点
bool Insert(const pair<K, V>& kv)
{
// 第一步：如果树为空，直接插入根节点
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
//第二步：寻找适合插入的空位置
Node* parent = nullptr; // 记录当前节点的父亲（插入后需要连接）
Node* cur = _root; // 记录当前节点
while (cur) // cur 为空时，说明找到了插入位置
{
if (kv.first > cur->_kv.first) // 插入的 key 大于当前节点就往右走
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first) // 插入的 key 小于当前节点就往左走
{
parent = cur;
cur = cur->_left;
}
else // 说明key已存在AVL树不允许重复键
{
return false;
}
}
// 第三步：插入新节点
cur = new Node(kv); // 申请新节点
// 判断新节点是 parent 的左孩子还是右孩子
if (cur->_kv.first > parent->_kv.first)
{
parent->_right = cur; // 插入到右子树
}
else
{
parent->_left = cur; // 插入到左子树
}
cur->_parent = parent; // 设置新节点的父指针（三叉链需要）
//第四步：控制平衡（更新平衡因子 + 旋转调整）
// 1、更新平衡因子（沿插入路径向上更新）
// 2、根据平衡因子判断是否需要旋转
// 3、旋转后调整相关节点的平衡因子
......//后面我们详细介绍
return true;
}更新平衡因子：
（1）插入新节点cur后，其父节点parent的平衡因子一定会发生改变，因此必须进行更新。在插入之前，parent的平衡因子只能是-1、0、1这三种情况之一。
具体更新规则如下：
-
如果
cur插入在新节点父亲（parent） 的左侧，说明左子树高度增加了，父亲（parent） 的平衡因子减1 -
如果
cur插入在新节点父亲（parent） 的右侧，说明右子树高度增加了，父亲（parent） 的平衡因子加1
（2）新节点父亲的平衡因子更新以后，又会分为 3 种情况：parent的平衡因子可能有三种情况：0，正负 1， 正负 2。
1.如果更新完成后，parent 的平衡因子变为 0，说明插入之前 parent 的平衡因子一定是
+1或者-1。新节点补到了原本更矮的那一侧子树，抹平了左右子树的高度差，以该 parent 为根的子树整体高度没有发生变化，上层祖先不会受到本次插入的影响，AVL 性质维持，插入成功，不需要继续向上更新祖先的平衡因子。
2.如果更新完成后，parent 的平衡因子变为
+1或者-1，说明插入之前 parent 的平衡因子一定为0。本次插入使得以该 parent 为根的子树整体高度增加，高度变化会向上传递，因此需要继续向上更新祖先节点的平衡因子。最坏情况下，回溯更新会一直执行到整棵树的根节点。
3.如果更新完成后，parent 的平衡因子变为
+2或者-2，说明以该 parent 为根的子树已经违反 AVL 平衡条件，此时需要根据其子节点的平衡因子判断不平衡类型，执行对应的旋转操作。旋转修复完成后，该子树高度复原，不需要再继续向上更新祖先节点。
// 插入节点
bool Insert(const pair<K, V>& kv)
{
//控制平衡：更新平衡因子
while (parent) // 最坏情况：一路更新到根节点
{
// 步骤1：更新父节点的平衡因子
if (cur == parent->_left) // 新节点插在父亲左边那么左子树变高
parent->_bf--;
else // 新节点插在父亲右边那么右子树变高
parent->_bf++;
// 步骤2：根据更新后的平衡因子，判断是否需要继续调整
//情况1：平衡因子变为0
if (0 == parent->_bf)
{
// 说明插入前 parent 的平衡因子是 1 或 -1
// 插入后变为 0，意味着子树高度没有发生变化
// 因此不需要继续向上更新
break;
}
//情况2：平衡因子变为 1 或 -1
else if (abs(parent->_bf) == 1)
{
// 说明插入前 parent 的平衡因子是 0
// 插入后变为 1 或 -1，意味着子树高度增加了
// 需要继续向上更新祖先节点的平衡因子
cur = parent;
parent = cur->_parent;
}
//情况3：平衡因子变为 2 或 -2
else if (abs(parent->_bf) == 2)
{
// 说明插入后 parent 已经失衡，需要进行旋转调整
// 1、左单旋：父节点右边高（2），且右孩子右边也高（1）
// 用到插入节点在较高右子树的右侧
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
// 2、右单旋：父节点左边高（-2），且左孩子左边也高（-1）
//用到插入节点在较高左子树的左侧
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
// 3、左右双旋：父节点左边高（-2），但左孩子的右边高（1）
// 用到插入节点在较高左子树的右侧
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
// 4、右左双旋：父节点右边高（2），但右孩子的左边高（-1）
//用到插入节点在较高右子树的左侧
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
break; // 旋转完成后树已平衡，退出循环
}
//情况4：出现其他值（理论上不可能）
else
{
assert(false); // 如果走到这里，说明平衡因子有 bug
}
}
return true;
}4.AVL树的旋转
如果在一棵原本平衡的 AVL 树中插入一个新节点，可能会导致某些节点的平衡因子变为
2或-2，从而破坏了树的平衡性。此时必须对树的结构进行调整，使其重新达到平衡状态，这个调整过程称为旋转。
根据新节点插入位置的不同，AVL 树的旋转分为四种：左单旋、右单旋、左右双旋、右左双旋。旋转的本质是：在遵循二叉搜索树规则的前提下，让左右子树高度均衡，从而降低整棵树的高度。
如何判断旋转类型
观察失衡结点到新插入结点的路径形态：
如果路径为直线：失衡结点、孩子、孙子三代结点偏向同一侧（LL、RR），执行单旋转。
如果路径为折线：失衡结点、孩子、孙子三代结点左右方向相反（LR、RL），执行双旋转。
出现失衡的这部分，既可以是整棵 AVL 树，也可以是大树中的某一棵局部子树，旋转操作只在该局部范围内完成。
a.新节点插入较高左子树的左侧 —— 左左（LL）：右单旋
我们将新的节点插入到了 parent 左孩子的左子树上，导致的不平衡的情况。
在插入前，AVL 树处于平衡状态。新节点插入到节点 30 的左子树中（注意：此处不一定是直接插入到 30 的左孩子位置，只要是插入到 30 的左子树中即可）。这样一来，30 的左子树增加了一层，导致以 60 为根的子树不再平衡。
为了让 60 恢复平衡，需要将 60 的左子树高度降低一层，同时右子树高度增加一层，也就是将左子树向上提，60 自然往下转。
由于 60 > 30，60 只能放在 30 的右子树位置。如果 30 原本有右子树（记为
subLR），那么subLR中的所有节点值一定大于 30 且小于 60，所以只能将它放在 60 的左子树位置。旋转完成后，更新相关节点的平衡因子即可。
右单旋的触发条件
parent的平衡因子为 -2（左边高）
parent左孩子的平衡因子为 -1观察发现，两个平衡因子同为负数，说明整条路径都是左边高，路径是一条直线，因此只需要做右单旋即可恢复平衡。
给大家一个小小的判断口诀：平衡因子同为负 ---> 左边高 --> 路径是直线 --> 右单旋
右单旋操作步骤：
第一步：让
subL的右子树subLR成为parent的左子树因为
subLR中所有节点的值都大于 30 且小于 60，放在 60 的左边是符合 BST 规则的。第二步：让
parent成为subL的右子树因为 60 大于 30，放在 30 的右边符合 BST 规则。
第三步：让
subL成为这棵子树的根节点此时需要考虑
parent是整棵树的根节点，还是一棵子树：
如果是整棵树的根节点，旋转完成后直接将
_root更新为subL如果是某棵子树，需要判断
parent是其父节点的左孩子还是右孩子，然后将对应的指针指向subL第四步：更新
parent和subL的平衡因子为0
旋转过程中的注意事项
在旋转过程中，有几个关于父指针更新的细节需要留意：
一是
subLR是否存在的问题。subL的右孩子subLR可能有，也可能没有。只有当它存在时，才需要将其父指针指向parent，如果为空则不用管。二是
parent原来是根还是子树。
旋转完成后，subL要顶替parent的位置。这里需要判断一下parent是整棵树的根节点，还是某棵子树的根：
如果是整棵树的根，旋转后
subL成为新根，父指针置空即可；如果只是某棵子树的根，则需要先确定
parent是父节点的左孩子还是右孩子，然后把父节点对应的指针指向subL。
进行调整 subLR、parent、subL 的位置和双亲指针的指向。
// 右单旋
void _RotateR(Node* parent)
{
//1. 保存关键节点
Node* subL = parent->_left; // subL: parent的左孩子（旋转后将成为新根）
Node* subLR = subL->_right; // subLR: subL的右孩子（旋转后将成为parent的左子树）
//2. 将subLR交给parent做左子树
// 因为subLR中所有节点值 > subL && < parent，放在parent左边符合BST规则
parent->_left = subLR;
// 如果subLR存在，更新其父指针指向parent
if (subLR)
{
subLR->_parent = parent;
}
//3. 保存parent的原父节点
// 因为parent可能是某棵子树的根，旋转后需要将新的子树根subL与上层连接
Node* ppNode = parent->_parent;
// 4. 让parent成为subL的右子树
// parent > subL，放在subL右边符合BST规则
subL->_right = parent;
parent->_parent = subL; // 更新parent的父指针指向subL
//5. 让subL成为当前子树的根
if (_root == parent) // 情况A: parent是整棵树的根节点
{
_root = subL; // subL成为新的根
subL->_parent = nullptr; // 新根父指针置空
}
else // 情况B: parent只是一棵子树的根
{
// 判断parent原是左孩子还是右孩子，用subL替换上去
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode; // subL接管parent原来的父指针
}
//6. 更新平衡因子
// 右单旋后，parent和subL的左右子树高度相等，平衡因子都变为0
parent->_bf = 0;
subL->_bf = 0;
}b.新节点插入较高右子树的右侧 —— 右右(RR)：左单旋
在插入前，AVL 树处于平衡状态。新节点插入到节点 60 的右子树中，导致 60 的右子树增加了一层，使得以 30 为根的子树不再平衡。
为了让 30 恢复平衡，需要将 30 的右子树高度降低一层，左子树高度增加一层，也就是将右子树往上提，30 自然往下转。
由于 30 < 60，30 只能放在 60 的左子树位置。如果 60 原本有左子树（记为
subRL），那么subRL中所有节点的值一定大于 30 且小于 60，所以只能将它放在 30 的右子树位置。旋转完成后，更新相关节点的平衡因子即可。
左单旋的触发条件
parent的平衡因子为 2（右边高）
parent右孩子的平衡因子为 1两个平衡因子同为正数，说明整条路径都是右边高，路径是一条直线，因此只需要做左单旋即可恢复平衡。
判断口诀：平衡因子同为正 --> 右边高 --> 路径是直线 --> 左单旋
左单旋操作步骤
第一步：让
subR的左子树subRL成为parent的右子树因为
subRL中所有节点的值都大于 30 且小于 60，放在 30 的右边是符合 BST 规则的。第二步：让
parent成为subR的左子树因为 30 小于 60，放在 60 的左边符合 BST 规则。
第三步：让
subR成为这棵子树的根节点此时需要考虑
parent是整棵树的根节点，还是一棵子树：
如果是整棵树的根节点，旋转完成后直接将
_root更新为subR如果是某棵子树，需要判断
parent是其父节点的左孩子还是右孩子，然后将对应的指针指向subR第四步：更新
parent和subR的平衡因子为0
旋转过程中的注意事项
在旋转过程中，需要更新节点之间的父指针指向，有几个地方要特别留意：
一是
subRL的父指针要不要改。subR的左孩子subRL可能存在，也可能为空，只有它存在时才需要把它的父指针指向parent，空节点就不管了。二是
parent的父指针要指向subR。
旋转后parent变成了subR的左孩子，它的父指针自然要跟着改过去。三是新根
subR的父指针指向谁。
旋转完成后，subR顶替了原来的parent成为这棵子树的根。此时得看parent原来是整棵树的根，还是只是一棵子树的根：
是整棵树根的话，
subR就成了新根，父指针置空；是子树根的话，
subR的父指针就要指向parent原来的父节点，同时还得判断原来的parent是左孩子还是右孩子，把对应的指针指向subR。
进行调整 subRL、parent、subR 的位置和双亲指针的指向。
// 左单旋
void treeRotateLeft(Node* parent)
{
//1. 保存关键节点
Node* subR = parent->_right; // subR：parent 的右孩子（旋转后将成为新根）
Node* subRL = subR->_left; // subRL：subR 的左孩子（值介于 parent 和 subR 之间）
// 2. 将 subRL 交给 parent 做右子树
// 因为 subRL 中所有节点值 > parent && < subR，放在 parent 右边符合 BST 规则
parent->_right = subRL;
// 如果 subRL 存在，更新其父指针指向 parent
if (subRL)
{
subRL->_parent = parent;
}
//3. 保存 parent 的原父节点
// 因为 parent 可能是某棵子树的根，旋转后需要将新的子树根 subR 与上层连接
Node* ppNode = parent->_parent;
//4. 让 parent 成为 subR 的左子树
// parent < subR，放在 subR 左边符合 BST 规则
subR->_left = parent;
// 更新 parent 的父指针指向 subR
parent->_parent = subR;
// 5. 让 subR 成为当前子树的根
if (parent == _root) // 情况A：parent 是整棵树的根节点
{
_root = subR; // subR 成为新的根
subR->_parent = nullptr; // 新根父指针置空
}
else // 情况B：parent 只是一棵子树的根
{
// 判断 parent 原是左孩子还是右孩子，用 subR 替换上去
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode; // subR 接管 parent 原来的父指针
}
//6. 更新平衡因子
// 左单旋后，parent 和 subR 的左右子树高度相等，平衡因子都变为 0
parent->_bf = 0;
subR->_bf = 0;
}c.新节点插入较高左子树的右侧 —— 左右(LR)：先左单旋再右单旋（左右双旋）
将新的节点插入到了 parent 左孩子的右子树上，导致的不平衡的情况。这时我们需要的是先对 parent 的右孩子进行一次左旋，再对 parent 进行一次右旋。
这里我们将双旋变成单旋后再旋转，也就是：先对 30 进行左单旋，然后再对 90 进行右单旋，旋转完成后再考虑平衡因子的更新。
旋转之前，60 的平衡因子可能是 -1/0/1，旋转完成之后，根据情况对其他节点的平衡因子进行调整。
h==0
双旋的触发条件
判断旋转类型的一个简单规律：引发旋转的路径是直线就单旋，是折线就双旋。
当
parent的平衡因子为-2，且parent左孩子的平衡因子为1时，两个平衡因子一负一正，说明左孩子的右子树高，而parent的左子树也高，路径呈现折线形状，此时需要先对左孩子进行左旋，再对parent进行右旋，也就是左右双旋。
左右双旋的平衡因子调整
左右双旋完成后，需要根据树的结构更新平衡因子。由于新节点插入位置的不同，旋转后各节点的平衡因子也会有所差异，具体有以下三种情况：
新节点插入在
parent左孩子的右子树的左边新节点插入在
parent左孩子的右子树的右边新节点本身就是
parent左孩子的右孩子（即subLR为空，该节点就是新增的）
规律说明
观察左右双旋后的结构可以发现：节点
subLR的左右子树被分走了 —— 左子树最终成为了subL的右子树，右子树最终成了parent的左子树。根据新节点插入在subLR的左侧还是右侧，左右两棵子树的高度会有所不同，从而影响parent和subL的平衡因子，而subLR的平衡因子最终一定为0。节点 60 的左右子树被分走了，左子树最终成为了节点 30 的右子树，右子树最终成了节点 90 的左子树。
void _RotateLR(Node* parent)
{
// 1. 保存关键节点
Node* subL = parent->_left; // subL: parent的左孩子
Node* subLR = subL->_right; // subLR: subL的右孩子（旋转的"折点"）
// 旋转之前，由于插入新节点的位置不同，subLR的平衡因子可能为 -1/0/1
// 记录下这个值，旋转完成后需要根据它来调整各节点的平衡因子
int bf = subLR->_bf;
//2. 分两步旋转
// 第一步：先对parent的左孩子进行左单旋（让折线变直线）
RotateL(parent->_left);
// 第二步：再对parent进行右单旋（恢复平衡）
RotateR(parent);
// 3. 根据bf调整平衡因子
// 旋转完成后，subLR成为新的根，其平衡因子一定为0
subLR->_bf = 0;
if (bf == -1)
{
// 新节点插入在subLR的左侧
parent->_bf = 1; // parent右子树偏高
subL->_bf = 0;
}
else if (bf == 1)
{
// 新节点插入在subLR的右侧
parent->_bf = 0;
subL->_bf = -1; // subL左子树偏高
}
else if (bf == 0)
{
// subLR本身就是新插入的节点
parent->_bf = 0;
subL->_bf = 0;
}
else
{
// 其他值说明出了问题
assert(false);
}
}d.新节点插入较高右子树的左侧 —— 右左(RL)：先右单旋再左单旋（右左双旋）
这里我们将新的节点插入到了 parent 右孩子的左子树上，导致的不平衡的情况。这时我们需要的是先对 parent 的右孩子进行一次右旋，再对 parent 进行一次左旋。
当h == 1时
右左双旋的触发条件
判断旋转类型有个简单的规律：引发旋转的路径是直线就单旋，是折线就双旋。
当
parent的平衡因子为2，且parent右孩子的平衡因子为-1时，两个平衡因子一正一负，说明右孩子的左子树高，而parent的右子树也高，路径呈现折线形状，所以需要先对右孩子进行右旋，再对parent进行左旋，这就是右左双旋。给大家一个判断口诀：平衡因子一正一负 --> 路径是折线 --> 双旋
右左双旋的平衡因子调整
右左双旋完成后，需要根据树的结构更新平衡因子。由于新节点插入位置的不同，旋转后各节点的平衡因子也会有所差异，具体有以下三种情况：
新节点插入在
parent右孩子的左子树的左侧新节点插入在
parent右孩子的左子树的右侧新节点本身就是
parent右孩子的左孩子
规律说明
观察右左双旋后的结构可以发现：节点
subRL的左右子树被分走了 —— 左子树最终成为了parent的右子树，右子树最终成了subR的左子树。根据新节点插入在subRL的左侧还是右侧，左右两棵子树的高度会有所不同，从而影响parent和subR的平衡因子，而subRL的平衡因子最终一定为0。节点 60 的左右子树被分走了，左子树 b 最终成了节点 30 的右子树，右子树 c 最终成了节点 90 的左子树。
// 右左双旋
void treeRotateRL(Node* parent)
{
// 1. 保存关键节点
Node* subR = parent->_right; // subR: parent的右孩子
Node* subRL = subR->_left; // subRL: subR的左孩子（旋转的折点）
// 旋转之前，由于插入新节点的位置不同，subRL的平衡因子可能为 -1/0/1
// 记录下这个值，旋转完成后需要根据它来调整各节点的平衡因子
int bf = subRL->_bf;
// 2. 分两步旋转
// 第一步：先对parent的右孩子进行右单旋（让折线变直线）
RotateR(parent->_right);
// 第二步：再对parent进行左单旋（恢复平衡）
RotateL(parent);
// 3. 根据bf调整平衡因子
// 旋转完成后，subRL成为新的根，其平衡因子一定为0
subRL->_bf = 0;
if (bf == -1)
{
// 新节点插入在subRL的左侧
parent->_bf = 0; // parent左右平衡
subR->_bf = 1; // subR右子树偏高
}
else if (bf == 1)
{
// 新节点插入在subRL的右侧
parent->_bf = -1; // parent左子树偏高
subR->_bf = 0; // subR左右平衡
}
else if (bf == 0)
{
// subRL本身就是新插入的节点
parent->_bf = 0;
subR->_bf = 0;
}
else
{
// 其他值说明出了问题
assert(false);
}
}AVL树旋转总结
当以
parent为根的子树失衡时，即parent的平衡因子为2或-2，根据具体情况采取以下旋转方式：
1.parent的平衡因子为2（右子树高）此时
parent的右子树根为subR，根据subR的平衡因子决定旋转方式：
subR的平衡因子为1→ 路径为直线（右右型） → 执行左单旋
subR的平衡因子为-1→ 路径为折线（右左型） → 执行右左双旋
2.parent的平衡因子为-2（左子树高）此时
parent的左子树根为subL，根据subL的平衡因子决定旋转方式：
subL的平衡因子为-1→ 路径为直线（左左型） → 执行右单旋
subL的平衡因子为1→ 路径为折线（左右型） → 执行左右双旋3.旋转完成后
经过旋转调整后，以
parent为根的子树恢复了平衡，整棵子树的高度相比插入前降低了一层，因此不需要继续向上更新平衡因子，旋转操作到此结束。
5.VL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性限制，因此验证一棵树是否为AVL树，需要从以下两个方面进行检查：
1.验证其为二叉搜索树
根据二叉搜索树的性质，其中序遍历序列一定是有序的（升序）。因此，对树进行中序遍历，如果得到的序列是严格升序的，则说明它满足二叉搜索树的性质。
2.验证其为平衡树
二叉搜索树只能保证有序，还需要进一步验证是否满足AVL树的平衡要求，主要检查以下两点：
平衡因子是否准确：每个节点的平衡因子 = 右子树高度 - 左子树高度，需要验证计算是否正确
高度差是否超标：每个节点左右子树的高度差绝对值不超过
1
（1）计算树的高度
// 计算当前树的高度
int Height(Node* root)
{
// 当前树为空，则高度为0
if (root == nullptr)
return 0;
// 当前树的高度 = 左右子树中高度最大的那个加1
return max(Height(root->_left), Height(root->_right)) + 1;
}（2）思路一：自顶向下的暴力解法
每次递归都重新计算子树高度，存在大量重复计算，效率较低。
bool IsBalance1()
{
return _IsBalance(_root);
}
bool _IsBalance1(Node* root)
{
// 当前树为空，说明是平衡的
if (root == nullptr)
return true;
// 当前树不为空，计算左右子树的高度
int leftHT = Height(root->_left);
int rightHT = Height(root->_right);
int diff = rightHT - leftHT;
if (diff != root->_bf) // 检查当前树的平衡因子是否计算正确
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
// 左右子树高度相减的绝对值小于2，说明当前树是平衡的，则继续往下判断其它子树
return abs(diff) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}（3）思路二：自底向上的高效解法（动态规划）
后序遍历，先判断子树是否平衡，同时返回子树高度供上一层使用，避免重复计算。
bool IsBalance2()
{
return _IsBalance2(_root) != -1;
}
int _IsBalance2(Node* root)
{
// 先判断当前树的左、右子树是否平衡，再判断当前树是否平衡
// 不平衡返回-1，平衡则返回当前树的高度
// 当前树为空，返回高度0
if (root == nullptr)
return 0;
// 当前树不为空，分别计算左右子树的高度
int leftHeight = _IsBalance2(root->_left);
int rightHeight = _IsBalance2(root->_right);
int diff = rightHeight - leftHeight;
if (diff != root->_bf) // 检查当前树的平衡因子是否计算正确
{
cout << "平衡因子异常:" << root->_kv.first << endl;
}
// 左子树高度等于-1、右子树高度等于-1、左右子树高度差的绝对值大于1，说明当前树不平衡
if (leftHeight == -1 || rightHeight == -1 || abs(diff) > 1)
return -1;
// 运行到这里来了，说明当前树是平衡的，返回当前树的高度
return max(leftHeight, rightHeight) + 1;
}（4）思路三：另一种自顶向下写法
与思路一逻辑类似，但将判断条件合并在一起。
bool _IsBalanceTree3(Node* root)
{
// 空树也是AVL树
if (nullptr == root)
return true;
// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;
// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者pRoot平衡因子的绝对值超过1，则一定不是AVL树
if (diff != root->_bf || (diff > 1 || diff < -1))
return false;
// pRoot的左和右如果都是AVL树，则该树一定是AVL树
return _IsBalanceTree3(root->_left) && _IsBalanceTree3(root->_right);
}#include <iostream>
using namespace std;
// AVL树节点
template<class K, class V>
struct AVLNode
{
pair<K, V> _kv;
AVLNode* _left;
AVLNode* _right;
AVLNode* _parent;
int _bf;
AVLNode(const pair<K, V>& kv)
: _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0)
{
}
};
// AVL树
template<class K, class V>
class AVLTree
{
typedef AVLNode<K, V> Node;
public:
AVLTree() : _root(nullptr) {}
// 插入
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 (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (kv.first > parent->_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;
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);
// 右旋
else if (parent->_bf == -2 && cur->_bf == -1)
RotateR(parent);
// 左右双旋
else if (parent->_bf == -2 && cur->_bf == 1)
RotateLR(parent);
// 右左双旋
else if (parent->_bf == 2 && cur->_bf == -1)
RotateRL(parent);
break;
}
}
return true;
}
// 中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
// 验证平衡
bool IsBalance()
{
return _IsBalance(_root) != -1;
}
private:
Node* _root;
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
int _IsBalance(Node* root)
{
if (root == nullptr)
return 0;
int leftH = _IsBalance(root->_left);
int rightH = _IsBalance(root->_right);
int diff = rightH - leftH;
if (diff != root->_bf || abs(diff) > 1)
return -1;
return max(leftH, rightH) + 1;
}
// 旋转
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
subR->_parent = ppNode;
}
parent->_bf = 0;
subR->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
ppNode->_left = subL;
else
ppNode->_right = subL;
subL->_parent = ppNode;
}
parent->_bf = 0;
subL->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
subLR->_bf = 0;
if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else
{
parent->_bf = 0;
subL->_bf = 0;
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
subRL->_bf = 0;
if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
}
else
{
parent->_bf = 0;
subR->_bf = 0;
}
}
};
int main()
{
cout << "常规场景 {16,3,7,11,9,26,18,14,15}" << endl;
AVLTree<int, int> t;
int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
for (int e : arr)
{
t.Insert({ e, e });
cout << "插入 " << e << " --> ";
t.InOrder();
}
cout << "\n是否平衡: " << (t.IsBalance() ? " 是" : " 否") << endl;
cout << "\n特殊场景 {4,2,6,1,3,5,15,7,16,14}" << endl;
AVLTree<int, int> t2;
int arr2[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (int e : arr2)
{
t2.Insert({ e, e });
cout << "插入 " << e << " --> ";
t2.InOrder();
}
cout << "\n是否平衡: " << (t2.IsBalance() ? " 是" : " 否") << endl;
return 0;
}
6.AVL树的删除（了解）
这里我们只是简单说一下大致过程，因为 AVL 树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与删除不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。
7.AVL 树的性能
AVL树是一棵绝对平衡的二叉搜索树，每个节点的左右子树高度差不超过1，所以查找效率很高，稳定在 O(logN)。
但它的缺点也很明显：维护平衡的成本太高。
插入数据时，可能需要多次旋转才能恢复平衡。删除数据时更麻烦，有时甚至需要一路旋转到根节点，性能开销比较大。
所以，AVL树适合读多写少的场景。如果数据是固定的，建好后只查不改，AVL树很合适。但如果是频繁插入删除的情况，就不太划算了，这时候可以考虑红黑树
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
35
0- 0
已为社区贡献1条内容
所有评论(0)