【高阶数据结构】AVL树详解
<font color = "#000066">前面对map/multimap/set/multiset进行了简单的介绍，在其文档介绍中发现。 这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。
那这篇文章我们就重点来学习一种平衡搜索二叉树——AVL树
1. AVL树的概念
<font color = blue>二叉搜索树虽可以提升查找的效率，但如果数据有序或接近有序时二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
因此，两位俄罗斯的数学家G.M.==A==delson-==V==elskii和E.M.==L==andis在1962年发明了一种解决上述问题的方法：
<font color = blue>当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，使整棵搜索树达到一个相对平衡的状态，从而减少平均搜索长度。
那大家思考一个问题：为什么是每个结点左右子树高度之差的绝对值不超过1，为什么不能是两边一样高，高度差为0呢？
<font color = "#000066">🆗，如果能达到左右子树完全一样高固然是最好的，但是关键在于有些情况不可能实现两边绝对平衡！ 比如
两个结点、4个结点的情况，当然肯定不止这些。大家看这种情况能实现两边完全平衡吗？ 是不行的，无法达到完全平衡。
所以，什么是平衡二叉树呢？
<font color = blue>一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
<font color = blue>它的左右子树都是AVL树
<font color = blue>左右子树高度之差(简称平衡因子，一般是右子树-左子树的高度差，当然左-右也可以)的绝对值不超过1（-1/0/1） ps：图中每个结点旁边的数字就是其对应的平衡因子
2. AVL树结构的定义
那我们这里以KV模型的结构来讲解，当然本质都是一样的
首先我们来写一下结点的结构
template <class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K,V>* _right;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;
int _bf;//balance factor（平衡因子）
AVLTreeNode(const pair<K,V>& kv)
:_right(nullptr)
,_left(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)
{}
};<font color = "#000066">这里我们给结点增加一个parent指针指向它的父亲结点，方便我们后续进行某些操作，当然带来方便的同时我们也需要去维护每个结点的parent指针，相应也带来了一些麻烦。 这个后面我们实现的时候大家就会体会到。
然后AVL树的结构
template <class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
//成员函数
private:
Node* _root = nullptr;
};那然后我们来写一下插入吧
3. 插入（仅仅是插入过程）
AVL树就是在二叉搜索树的基础上引入了平衡因子来控制树的相对平衡，因此AVL树也可以看成是二叉搜索树。
所以插入的逻辑其实跟搜索二叉树是一样的，不同的地方在于平衡二叉树插入之后如果整棵二叉树或者其中某些子树不平衡了我们要对插入的结点进行调整使得它重新变的平衡，那这个我们后面单独讲。
由于插入的逻辑我们之前已经讲过了，所以这里我就直接上代码了（这里我们选择非递归）
<font color = "#000066">不过需要注意的是我们这里插入新结点之后还要链接_parent指针。
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;
ccur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//链接父亲指针
cur->_parent = parent;
//更新平衡因子
//...
return true;
}大家看着代码再过一遍这个插入的过程。
那现在我问大家，AVL树的插入写到这里就完了吗？ 🆗，如果是普通的搜索树，这就完事了，但是，对于平衡搜索二叉树来说，还远远没有结束。
4. 平衡因子的更新
为了实现平衡二叉树，我们引入了一个新的概念，不知道大家还记不记得是啥？
<font color = "#000066">🆗，就是我们上面提到的平衡因子。 再来回顾一下什么是平衡因子？ 一个结点的平衡因子就是它的左右子树的高度差，一般是右子树减左子树的高度（我们这里的讲解也统一以右子树-左子树的高度作为平衡因子）。
4.1 为什么要更新平衡因子？
那大家想一下：我们在AVL树中插入了一个新结点之后，会不会影响到树中结点的平衡因子？
<font color = "#000066">毋庸置疑，这当然是会的！ 因为一旦插入了新的结点，整棵树的高度或者某些子树的高度必然会发生变化，那树的高度发生变化，必然会影响与之关联的结点的平衡因子。
<font color = blue>所以，插入了新结点之后，导致某些树的高度发生变化，我们要更新平衡因子。
🆗，那平衡因子会变化，这没啥说的，但是为啥变化了我就得更新呢？不更新行不行？
<font color = "#000066">答案是不行。 为什么呢？ 因为上面我们说了，如果一棵二叉搜索树是AVL树，那么它必须满足任何一个结点的平衡因子都在[-1, 0, 1]这个范围内。 而现在插入新结点会导致平衡因子变化，那么更新之后，某些结点的平衡因子可能就不在[-1, 0, 1]这个正常范围内了。 那他就不是一棵AVL树了，所以我们才要更新平衡因子，以此来判断这个树还是否是一棵AVL树。 如果不是了，即有结点的平衡因子不在正常范围内了，那这棵树的平衡就受到影响了，那我们就需要对新插入的结点进行调整，使他变回AVL树。 当然如果插入之后平衡没有受到影响，就不需要调整了。
那调整结点的事，我们后面再说，现在先谈一谈，插入新结点后，如何更新平衡因子！
4.2 如何更新平衡因子？
那首先大家思考一个问题，插入一个新结点之后，可能会影响到哪些结点的平衡因子？
<font color = "#000066">是不是影响的肯定是它的祖先啊。 因为新插入的结点在它祖先的子树上，那它祖先的子树高度发生变化，平衡因子必然也会发生变化。 但是会影响所有的祖先吗？ 不一定！可能只影响一部分。 比如：
那既然要更新，我就来研究一下更新的规律：
<font color = "#000066">那这个规律呢，其实也很容易得出： 因为平衡因子的计算是右子树高度-左子树高度嘛。 所以，对于新结点的父亲来说：
<font color = blue>如果插入在了右子树，那么父亲的平衡因子就要++
<font color = blue>如果插入在了左子树，那么父亲的平衡因子就要- -
<font color = "#000066">即
4.3 parent更新后，是否需要继续往上更新？
那父亲结点的平衡因子更新完之后，还要不要继续往上更新呢？
<font color = "#000066">首先parent肯定要更新，因为插入之后它的子树的高度变了。 所以大家先想一下，什么情况下parent更新完之后还要继续往上更新parent的祖先？ 🆗，是不是取决于parent所在的这棵子树的高度有没有发生变化啊。
<font color = blue>如果插入之后parent这棵子树的高度没有变化，那就不会影响parent再往上结点（即parent的祖先）的平衡因子，就不需要往上继续更新了
<font color = blue>如果插入之后parent这棵子树的高度发生了变化，那parent的平衡因子更新完成后就需要继续往上更新
那我们分析一下其实分为这三种情况：
-
<font color = blue>如果parent的平衡因子更新之后为1或-1，则parent这棵树的高度发生变化，需要继续向上更新
为什么呢？为什么parent的平衡因子变成1或-1，它的高度就变了呢？
<font color = "#000066">我们刚才是不是分析过，插入一个新结点，它的parent的平衡因子是怎么变化的，是不是要么-1，要么+1啊。 那它现在更新之后变成了1或者-1，能够说明什么？ 是不是说明它更新之前的平衡因子一定是0啊，0的话说明他两边高度是平衡的，而现在插入之后变为1或-1，说明右边或者左边高了，因此高度肯定是变化了，那就要继续往上更新。 那继续往上更新是不是又是同样的逻辑啊（我们只需将结点往上走，下次循环自然会进行同样的处理，后面代码实现出来大家会更清晰）。
那可能是-2或者2加一减一之后变成-1或1啊？
<font color = black>不可能，因为AVL树的平衡因子的范围都是在[-1, 0, 1]内的。
-
<font color = blue>parent的平衡因子更新之后为2或-2
如果是2或-2呢？要继续往上更新吗？
<font color = "#000066">🆗，如果是2或-2，那已经不在平衡因子的正常范围内了，那就说明当前parent所在的这棵子树已经不平衡了！！！（通常把这棵树叫做最小不平衡子树） 那还往上更新个屁啊，是不是就要去调整结点是这棵最小不平衡子树重变平衡。 那怎么调整呢，要进行旋转，具体怎么做后面再讲。 那旋转之后它的高度其实就恢复到插入之前了，也就不需要再继续往上更新了。
-
<font color = blue>parent的平衡因子更新之后为0
那为0的话需要继续更新吗？
<font color = "#000066">为0当然就不需要了。 为什么呢？ 大家想，更新之后为0的话，是不是说明插入之前它的平衡因子为1或者-1啊，然后我们在左边插入了一个结点或者是右边，然后它的平衡因子就变成了0
4.4 平衡因子更新代码实现
我们来写一下代码：
<font color = black>因为不知道要向上更新几次，所以肯定是一个循环。 那循环什么时候结束？ 通过我们上面的分析，它可能向上更新几次就停止了，但是不排除有可能一直更新直到根结点 比如这种情况
//更新平衡因子
while (parent)
{
//更新parent的平衡因子
if (cur == parent->_right)
{
parent->_bf++;
}
else
{
parent->_bf--;
}
//判断是否需要继续向上更新，需要就往上走等待下次循环更新，
//如果不平衡了就进行处理，不需要处理不需要调整就break
if (parent->_bf == 1 || parent->_bf == -1)
{
parent = parent->_parent;
cur = cur->_parent;
}
else if(parent->_bf == 2 || parent->_bf == -2)
{
//进行旋转调整
//...
break;
}
else if (parent->_bf == 0)
{
break;
}
else
{
//非正常情况
assert(false);
}
}那接下来我们就来重点讲一下对于不平衡的情况如何进行调整，即AVL树的旋转
5. AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。
根据节点插入位置的不同，AVL树的旋转分为四种，接下来我们将一 一进行学习
5.1 新节点插入较高右子树的右侧---右右：左单旋
我们先来学习第一种旋转——左单旋。
什么情况要进行左单旋
那什么样的情况要进行左单旋呢？
<font color = "#000066">
大家对照着图，我们来分析一下：
首先大家可能有疑问
<font color = "#000066">
那我们看这个图
<font color = "#000066">原本30这棵AVL树（当然实际中他也可能是一棵子树，子树的话上面就还有结点）处在平衡的状态，右子树比左子树高1，然后现在我们在它的右子树的右侧c这里插入新结点，然后它的高度变成h+1。 注意我们讨论的情况是插入之后它的高度+1，如果高度不变的话也不需要调整了
如何进行左单旋
那左单旋处理是怎么做呢？
<font color = "#000066">现在我们插入之后是这样的
左单旋代码实现
那然后我们来写一下左单旋的代码：
<font color = "#000066">
subtree （子树）的缩写 对照着图，大家看一下这样写对不对。
🆗，这样写是有问题的：
<font color = "#000066">==第一个问题==——没有处理结点的
_parent指针 我们上面实现的时候给结点增加了一个指向其父亲的指针parent，方便我们更新平衡因子的时候往上走，但是代价就是需要我们去维护这个指针。 所以，旋转之后要更新parent指针subRL可能为空 为什么？
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if(subRL)
subRL->_parent = parent;
//先保存一下parent->_parent，因为下面会改它
Node* pparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
//若pparent为空则证明旋转的是一整棵树，因为根结点的_parent为空
if (pparent == nullptr)
{
//subR是新的根
_root = subR;
_root->_parent == nullptr;
}
//若pparent不为空，则证明旋转的是子树，parent上面还有结点
else
{
//让pparent指向子树旋转之后新的根
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
//同时也让新的根指向pparent
subR->_parent = pparent;
}
//旋转完更新平衡因子
parent->_bf = subR->_bf = 0;
}什么时候调用左单旋
那我们代码写好了，什么时候调用呢？
<font color = blue>我们观察图会发现
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}5.2 新节点插入较高左子树的左侧---左左：右单旋
接着我们看第二种旋转——右单旋
什么情况要进行右单旋
那右单旋又适用于哪些情况呢呢？
<font color = "#000066">
如何进行右单旋
那右单旋又该如何操作呢？
<font color = "#000066">也是两步
右单旋代码实现
那我们来写一下右单旋的代码
<font color = "#000066">那写了上面左单旋的代码，再写右单旋的话应该就比较轻松了，需要注意的点还是那几个
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = parent->_right;
//旋转并更新_parent指针
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
//先保存一下parent->_parent，因为下面会改它
Node* pparent = parent->_parent;
//旋转并更新_parent指针
subL->_right = parent;
parent->_parent = subL;
//若parent等于_root则证明旋转的是一整棵树（这也是一种判断方法）
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
//让pparent指向子树旋转之后新的根
if (parent == pparent->_left)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
//同时也让新的根指向pparent
subL->_parent = pparent;
}
subL->_bf = parent->_bf = 0;
}什么时候调用右单旋
那右单旋什么时候调用呢？
<font color = blue>来看图
5.3 新节点插入较高左子树的右侧---左右：先左单旋再右单旋（左右双旋）
再来看第三种旋转——左右双旋
什么情况进行左右双旋
<font color = "#000066">看这张图
如何进行左右双旋
首先要知道对于这种情况，我们如果只进行左或者右的单旋是解决不了问题的
<font color = "#000066">
那要进行双旋，怎么做呢？
<font color = blue>上面已经说了针对这种情况要进行的是左右双旋，那顾名思义就是先进行一个左单旋（对根的左子树），再进行一个右单旋（对根）
左右双旋代码实现
那左右双旋的代码怎么写？是不是直接复用左右单旋的代码就行了
<font color = "#000066">那就先调用左旋，再调用右旋就行了
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
//更新平衡因子
if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}什么时候调用左右双旋
看图
<font color = black>
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}5.4 新节点插入较高右子树的左侧---右左：先右单旋再左单旋（右左双旋）
什么情况进行右左双旋
那我们来看一下右左双旋适用于哪些情况？
<font color = "#000066">
如何进行右左双旋
那就还是两次单旋嘛：
<font color = blue>这里就是首先进行一次右单旋（对根的右子树），然后再进行一次左单旋（对根）
右左双旋代码实现
那右左单旋的话我们可以是可以直接复用左单旋和右单旋的，但是，同样的道理，我们还是需要对双旋之后的平衡因子分不同的情况进行更新处理：
<font color = "#000066">与左右双旋一样，还是三种情况，不同情况平衡因子的更新不同，通过插入之后subRL的平衡因子区分三种情况
<font color = blue>就是我们上面分析的，在c插入
<font color = blue>在b插入
<font color = blue>h等于0情况下的插入
<font color = black>那对应的代码就是
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
//更新平衡因子
if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}什么时候调用右左双旋
很容易看出来：
<font color = black>
5.5 总结
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
<font color = blue>pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为SubR 当SubR的平衡因子为1时，执行左单旋 当SubR的平衡因子为-1时，执行右左双旋
<font color = blue>pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为SubL 当SubL的平衡因子为-1是，执行右单旋 当SubL的平衡因子为1时，执行左右双旋
6. AVL树的测试
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要测试AVL树，可以分两步：
6.1 验证其为二叉搜索树
我们插入一些数据，如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
<font color = "#000066">
6.2 验证其为平衡树
那如何验证它是否平衡呢？
<font color = "#000066">我们可以去计算高度，如果每一个结点左右子树的高度差的绝对值不超过1，就证明它是平衡的。 为什么不用平衡因子判断呢？ 首先，不是所有的AVL树的实现里面都有平衡因子的，只是我们这里采用了平衡因子，这是AVL树的一种实现方法而已。 其次，我们不敢保证我们自己写到代码计算出来的平衡因子一定是正确的。
所以，我们来写一个通过高度差来判断是否平衡的函数
<font color = black>
然后我们测试一下
<font color = black>先判断一下刚才的那棵树
{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}
然后呢，我们还可以做一件事情
6.3 判断平衡因子的更新是否正确
怎么判断：
<font color = "#000066">很简单，计算一下高度差，看他和平衡因子相不相等就行了
6.4 大量随机数构建AVL树进行测试
上面的测试数据量比较小，且不够随机
下面我们生成一些随机数来构建AVL树，测试一下
<font color = black>
7. 查找
然后AVL树的查找那就跟搜索二叉树是一样的，我们这里就不讲了，大家可以看之前搜索二叉树的文章。
8. AVL树的删除(了解)
AVL树的删除操作我们不做重点讲解，大家了解一下即可，因为这个不是特别重要，面试一般也不会考到。
AVL树的删除操作主要分为以下几个步骤：
<font color = "#000066">执行二叉搜索树的删除操作
<font color = "#000066">更新平衡因子：如果删除之后影响到了上面结点的平衡因子，就要从被删除节点的父节点向上更新受影响的平衡因子。
<font color = "#000066">检查所有的平衡因子，如果存在不正常的平衡因子，则要对相应的树进行调整，使它恢复平衡。
<font color = "#000066">重复步骤2和步骤3，直至到达根节点或不需要进一步调整为止。
9. AVL树的性能
<font color = blue>AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即$log_2 (N)$。 但是如果要对AVL树做一些结构修改的操作，性能非常低下。 比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。 因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
10. 源码
10.1 AVLTree.h
#pragma once
#include <assert.h>
template <class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K,V>* _right;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;
int _bf;//balance factor
AVLTreeNode(const pair<K,V>& kv)
:_right(nullptr)
,_left(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)
{}
};
template <class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
//cout << "root:"<<_root->_kv.first << endl;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//链接父亲指针
cur->_parent = parent;
//更新平衡因子
while (parent)
{
//更新parent的平衡因子
if (cur == parent->_right)
{
parent->_bf++;
}
else
{
parent->_bf--;
}
//判断是否需要继续向上更新，需要就往上走等待下次循环更新，
//如果不平衡了就进行处理，不需要处理不需要调整就break
if (parent->_bf == 1 || parent->_bf == -1)
{
parent = parent->_parent;
cur = cur->_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);
}
else
{
assert(false);
}
//旋转完结束，就不需要再往上更新了
break;
}
else if (parent->_bf == 0)
{
break;
}
else
{
//非正常情况
assert(false);
}
}
//cout << "root:" << _root->_kv.first << endl;
return true;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBalance()
{
return _IsBalance(_root);
}
int TreeHeight()
{
return _TreeHeight(_root);
}
private:
bool _IsBalance(Node* root)
{
if (root == nullptr)
return true;
int rightH = _TreeHeight(root->_right);
int leftH = _TreeHeight(root->_left);
if (rightH - leftH != root->_bf)
{
cout << root->_kv.first << "结点平衡因子更新错误" << endl;
return false;
}
return abs(rightH - leftH) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
int _TreeHeight(Node* root)
{
if (root == nullptr)
return 0;
int RightH = _TreeHeight(root->_left);
int leftH = _TreeHeight(root->_right);
return RightH > leftH ? RightH + 1 : leftH + 1;
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//旋转并更新_parent指针
parent->_right = subRL;
if(subRL)
subRL->_parent = parent;
//先保存一下parent->_parent，因为下面会改它
Node* pparent = parent->_parent;
//旋转并更新_parent指针
subR->_left = parent;
parent->_parent = subR;
//若pparent为空则证明旋转的是一整棵树，因为根结点的_parent为空
if (pparent == nullptr)
{
//subR是新的根
_root = subR;
_root->_parent = nullptr;
}
//若pparent不为空，则证明旋转的是子树，parent上面还有结点
else
{
//让pparent指向子树旋转之后新的根
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
//同时也让新的根指向pparent
subR->_parent = pparent;
}
//旋转完更新平衡因子
parent->_bf = subR->_bf = 0;
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//旋转并更新_parent指针
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
//先保存一下parent->_parent，因为下面会改它
Node* pparent = parent->_parent;
//旋转并更新_parent指针
subL->_right = parent;
parent->_parent = subL;
//若parent等于_root则证明旋转的是一整棵树（这也是一种判断方法）
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
//让pparent指向子树旋转之后新的根
if (parent == pparent->_left)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
//同时也让新的根指向pparent
subL->_parent = pparent;
}
subL->_bf = parent->_bf = 0;
}
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
//更新平衡因子
if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
//更新平衡因子
if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
10.2 Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include "AVLTree.h"
#include <time.h>
void AVLTest1()
{
//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//int arr[] = { 1,2,3,4,5,6,7,8,9,1 };
int arr[] = { 95,47,32,29,7,7,2,50,74,30 };
AVLTree<int, int> t1;
for (auto e : arr)
{
//cout << e << endl;
t1.Insert(make_pair(e, e));
t1.InOrder();
if (!t1.IsBalance())
{
break;
}
}
//t1.InOrder();
/*if (t1.IsBalance())
{
cout << "平衡" << endl;
}
else
{
cout << "不平衡" << endl;
}*/
}
void AVLTest2()
{
srand(time(nullptr));
const int N = 1000000;
AVLTree<int, int> t;
for (int i = 0; i < N; ++i)
{
int x = rand();
t.Insert(make_pair(x, x));
}
if (t.IsBalance())
{
cout << "平衡" << endl;
}
else
{
cout << "不平衡" << endl;
}
}
int main()
{
AVLTest2();
return 0;
}
- 点赞
- 收藏
- 关注作者
评论（0）