【C++】AVL树实现
目录
前言
一、AVL树的概念
二、AVL树的实现
1.基本框架
2.AVL树的插入
三、旋转
1.右单旋
2.左单旋
3.左右双旋
4.右左双旋
四、AVL树的查找
五、AVL树的平衡检测
六、AVL树的删除
总结
前言
本文主要讲解AVL树的插入，AVL树是在二叉搜索树的基础上，更加实用的一种数据结构，它拥有自平衡的特性，来保证它的搜索效率，本文就来探究它是如何实现自平衡的。
温馨提醒：本文所有代码中父节点我拼写成了perent，正确拼写应该是parent，不好意思，望周知(✪ω✪)。
一、AVL树的概念
- AVL 树是最先发明的自平衡二叉查找树，AVL是一颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索二叉树， 通过控制高度差去控制平衡。
- AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家，他们在1962 年的论文《Analgorithmfortheorganizationofinformation》中发表了它。
- AVL树实现这里我们引入一个平衡因子(balancefactor)的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1， AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡， 就像一个风向标一样。
- 思考一下为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差是0呢？0不是更好的平衡吗？画画图分析我们发现，不是不想这样设计，而是有些情况是做不到高度差是0的。比如一棵树是2个结点，4个结点等情况下，高度差最好就是1，无法做到高度差是0。如下图一棵AVL树，它的平衡因子绝对值不超过1.
- 反之，如果平衡因子绝对值大于1，就不是AVL树，如下图：
- AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在logN，那么增删查改的效率也可以控制在O(logN)，相比二叉搜索树有了本质的提升。效率计算如下图：
温馨提醒：本章节需要有二叉搜索树的基础，主页有哦，AVL树就是在二叉搜索树上增加了自平衡机制，调整子树高度差，保证查找效率。
二、AVL树的实现
1.基本框架
#pragma once #include template struct AVLTreeNode { pair _kv;//k:v结构 AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _perent; int _bf;//平衡因子 AVLTreeNode(const pair& kv)//构造 :_kv(kv) , _left(nullptr) , _right(nullptr) , _perent(nullptr) , _bf(0) {} }; template class AVLTree { typedef AVLTreeNode Node;//重命名 public: private: Node* _root = nullptr;//根节点 };- AVL树的基本框架与搜索二叉树有点不同，主要是节点定义的区别：
- 节点的数据结构采用 key:value 结构，也就是使用pair保存数据。
- 节点采用三叉链结构，即有左孩子节点指针、右孩子节点指针、父节点指针。
- 增加成员变量 _bf，也就是平衡因子，用于检测每一个节点是否符合AVL树的特征（左右子树高度差不超过1）。
- 然后，AVL树的模版参数K,V，分别控制数据key:value的数据类型。类只有一个变量_root，也就是根节点。
温馨提醒：不要忘记了搜索二叉树的特性：对于不支持相等值的搜索二叉树，每个节点的左子树的数据全小于根节点，右子树的数据全大于根节点。
2.AVL树的插入
AVL树插入一个值的大概过程：
- 插入一个值按二叉搜索树规则进行插入。
- 新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点 -> 根结点路径上的平衡因子，实际中最坏情况下要更新到根节点，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。
- 更新平衡因子过程中没有出现问题，则插入结束。
- 更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后调平衡的同时，本质降低了子树的高度，不会再影响上⼀层，所以插入结束。
我们先不管更新平衡因子和旋转，先把前面的代码写出来：
//插入 bool Insert(const pair& kv) { //树为空 if (_root == nullptr) { _root = new Node(kv); return true; } //树不为空 Node* cur = _root; Node* perent = nullptr; while (cur) { if (kv.first > cur->_kv.first) { perent = cur; cur = cur->_right; } else if (kv.first _kv.first) { perent = cur; cur = cur->_left; } else { return false; } } //插入 cur = new Node(kv); if (kv.first > perent->_kv.first) { perent->_right = cur; } else { perent->_left = cur; } cur->_perent = perent; //更新平衡因子 //... return true; }- 这些就基本和搜索二叉树一致，这里就不赘述了。
- 需要注意的是插入新节点后记得更新新节点的父节点指针，毕竟是三叉链。
1.平衡因子更新：
更新原则：
- 平衡因子=右子树⾼度-左子树高度
- 只有子树高度变化才会影响当前结点平衡因子。
- 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，parent平衡因子--。
- parent所在子树的高度是否变化决定了是否会继续往上更新。
我们先看一些实际情况：来了解什么时候可以停止向上更新平衡因子
（1）
- 如上图，新增节点13，在节点14的左边，所以14的平衡因子--，14的平衡因子变化就可能会引起其父节点平衡因子变化。因为14节点的平衡因子是由0变化到-1，所以它高度一定是加1，14的父节点是节点10，14在10的右边，所以14的平衡因子要++，此时对于节点10来说，平衡因子绝对值大于1了，需要旋转处理。（先不管如何旋转）
- 我们继续观察节点14，它的平衡因子原来是0，现在变成-1，说明它原来的子树高度差为0，插入一个节点后导致它高度差变化，所以，在插入节点操作中如果平衡因子变为-1，说明它一定是由0变化过来的，并且需要继续向上更新父节点的平衡因子。同理我们也能得出，如果插入操作导致平衡因子变为-1，说明它一定是从0变过来的，而且也需要继续向上更新平衡因子。
- 得出一条结论：更新后parent的平衡因子等于1或-1，更新前更新中parent的平衡因子变化为 0->1 或者 0->-1，说明更新前 parent 子树两边⼀样高，新增的插入结点后，parent所在的子树一边高一边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新。
- 我们继续观察节点10，它的平衡因子变化是因为右子树新增一个节点，导致它的平衡因子从1变为2，此时它已经不满足AVL树了，需要进行旋转操作，我们先不管怎么旋转，我们先了解旋转的结果，旋转的目标有两个：1、把 parent子树旋转平衡。2、降低parent子树的高度，恢复到插入结点以前的高度。这样一来，相当于节点10的平衡因子没有发生变化，所以此时不需要向上更新平衡因子。同理当平衡因子从-1变为-2，我们也不需要向上更新父节点的平衡因子。
- 得出第二条结论：更新后parent的平衡因子等于2或-2，更新前更新中parent的平衡因子变化为1->2或者-1->-2，说明更新前parent子树一边高一边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：1、把 parent子树旋转平衡。2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。
（2）
- 如上图，这次插入节点-1，位于父节点1的左子树，所以父节点1的平衡因子--，此时因为节点1的平衡因子发生变化，所以需要继续向上更新，节点1的父节点3的平衡因子此时从1变为0，这说明新增节点导致节点3的左右子树高度平衡了，这时我们还需要继续向上更新平衡因子吗？答案是不用了，因为平衡因子变为0说明它一定是从-1或者1变过来的，变化前高度差为1，变化后高度差为0，这对于其父节点来说高度没变化，所以不需要继续向上更新平衡因子了。
- 得出结论：更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0或者1->0，说明更新前 parent 子树一边高一边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会影响parent的父亲结点的平衡因子，更新结束。
（3）
- 插入节点7，节点6的平衡因子加1，节点3的平衡因子加1，根节点8的平衡因子也要加1。所以这就是最后一种情况也是最坏的情况，需要我们一路向上更新的根节点。
- 总结：如果平衡因子变为1或者-1，继续向上更新，如果一直到根节点平衡因子还是1或者-1，则停止更新。
2.总结：平衡因子更新停止条件
- 更新后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所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：1、把 parent子树旋转平衡。2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。
- 如果平衡因子变为1或者-1，继续向上更新，如果一直到根节点平衡因子还是1或者-1，则停止更新。（最坏情况）
更新平衡因子代码：
//插入 bool Insert(const pair& kv) { //树为空 if (_root == nullptr) { _root = new Node(kv); return true; } //树不为空 Node* cur = _root; Node* perent = nullptr; while (cur) { if (kv.first > cur->_kv.first) { perent = cur; cur = cur->_right; } else if (kv.first _kv.first) { perent = cur; cur = cur->_left; } else { return false; } } //插入 cur = new Node(kv); if (kv.first > perent->_kv.first) { perent->_right = cur; } else { perent->_left = cur; } cur->_perent = perent; //更新平衡因子 while (perent) { if (cur == perent->_left)//插入节点位于左边 { --perent->_bf;//平衡因子-- } else//插入节点位于右边 { ++perent->_bf;//平衡因子++ } if (perent->_bf == 0)//平衡因子等于0 { break;//直接结束 } else if (perent->_bf == -1 || perent->_bf == 1)//平衡因子需要继续向上更新 { cur = perent;//更新cur为父节点 perent = perent->_perent;//更新父节点为父父节点 } else if (perent->_bf == -2 || perent->_bf == 2)//不满足AVL树，需要旋转处理 { //旋转 //... break;//旋转完直接结束 } else//平衡因子出现其它值，说明存在bug { assert(false);//说明出现bug，报错处理 } } return true; }- 以上就是插入节点时关于平衡因子更新的代码，应该不难理解。
- 接下来就是关于旋转怎么操作的问题了。
三、旋转
旋转的原则：
- 保持搜索树的规则
- 让旋转的树从不满足平衡变平衡，其次降低旋转树的高度，恢复到以前的高度（注意不是平衡因子）
旋转总共分为四种：左单旋/右单旋/左右双旋/右左双旋。
1.右单旋
- 以上就是一个完整的右单旋过程，看不懂没关系，我们一步一步来。
- 上图展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。这里a/b/c是高度为h的子树， 是一种概括抽象表示，他代表了所有右单旋的场景，实际右单旋形态有很多种。
- 这里首先的问题就是为啥 a，b，c 要抽象成三个子树，而不是具体的节点，我们通过下面几个案例就会明白了。
（1）h=0
- 当 a，b，c 为h=0的三颗子树时，那么就只有两个节点，此时在 a 位置插入节点1，这时，根节点10的平衡因子变为-2，然后进行旋转操作，平衡了高度差。
- 所以当h=0时，右单旋只有一种情况。
（2）h=1
- h=1时，a,b,c就是一个节点的子树，此时也只有一种情况。
- 我们先不管如何旋转，先观察插入位置，插入位置都是最左边最高处。
（3）h=2
- h=2，h=2的子树有3种情况，如上图中的 X，Y，Z。
- 这里需要注意，子树a只能是X这一种情况，子树b,c可以是这三种任意一种，为什么呢？因为是在子树a插入新节点，然后需要保证影响到根节点10以此触发旋转操作，如果a树为Y,Z一种，那么新插入节点后a要么平衡要么不平衡，a平衡不会影响到根节点的平衡因子，a不平衡则自身会触发旋转操作，最终也不会影响根节点的平衡因子。所以a只能是X。
- 通过计算，h=2时，一共有36种情况，而这些情况都可以经过右单旋恢复平衡。
（4）h=3
- h=3时，高度为3的子树就有非常多的情况了，可以分为上图中X和y-C，y-C表示最后一层四个叶子结点保留任意1个/任意2个/任意3个的子树。
- 同h=2，这里a子树也只能是X这种情况，计算下来，一共有5400种情况，以至于画图时不得不使用抽象的子树a,b,c来表示。
- 所以你应该明白了为什么a,b,c要使用抽象的子树表示吧，就是因为有无数种情况，无数种情况都可以抽象成a,b,c来表示。
理解了a,b,c的含义，我们接下来观察旋转如何实现：
- 如图，在a子树中插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从-1变成-2，10为根的树左右高度差超过1，违反平衡规则。10为根的树左边太高了，需要往右边旋转，控制两棵树的平衡。
- 旋转核心步骤，因为5
- 简单点说，为什么可以这样旋转，因为b和10节点都大于节点5，所以b和10节点都能作为5的右子树。因为b一开始是10的左边，所以让b直接成为10的左子树。最后整棵树的高度恢复了到了h+1，这样就平衡了高度差。
- 我们通过观察上面h=0,1,2,3的案例，就能发现，只要出现根节点的左孩子平衡因子变为-1，导致根节点平衡因子变为-2，就可以使用右单旋进行调整了。
（1）右单旋的代码实现：
//右单旋 void RotateR(Node* perent) { Node* subL = perent->_left;//左孩子 Node* subLR = subL->_right;//左孩子的右孩子 //旋转过去 perent->_left = subLR; subL->_right = perent; Node* ppNode = perent->_perent;//记录父父节点 //更新父节点指针 if (subLR) subLR->_perent = perent; perent->_perent = subL; if (perent == _root)//判断根节点 { _root = subL; subL->_perent = nullptr; } else { if (ppNode->_left == perent) { ppNode->_left = subL; } else { ppNode->_right = subL; } subL->_perent = ppNode; } //更新平衡因子 subL->_bf = perent->_bf = 0; }代码解释：
- 因为右单旋受影响的节点有根节点、根节点的左孩子、左孩子的右子树。所以如上图，我们将根节点命名parent，左孩子命名subL，左孩子右子树命名subLR
- 首先第一步就是将b（subLR）旋转过去作为根节点（parent）的左子树，然后将parent点作为左孩子（subL）的右孩子。
- 然后因为是三叉链，所以我们还需要更新subLR和parent的父节点指针，这里需要注意的是subLR可能为0，如h=0时，所以我们需要if判断一下。
- 其次就是根节点的更新，因为可能是局部子树也可能是整棵树，所以在更新父节点指针前，先保存parent的父节点指针ppNode。我们先判断parent是不是根节点，是：我们就更新subL为新根节点然后令subL的父节点指针为空，因为根节点没有父节点。否：说明是局部子树，所以我们先判断parent是ppNode的哪个孩子节点，然后调整ppNode的该孩子节点指向subL，最后令subL的父节点指针指向ppNode。这样就完成了根节点的更新。
- 最后就是更新平衡因子了。我们根据上面和上上面的图就能得知，平衡因子受影响的只有parent和subL，a,b,c子树是作为整体不受影响，并且，parent和subL的平衡因子经过旋转后就一定为0，这一点通过图就能直观的得出来。
完成右单旋代码后，我们就可以更新一下插入函数了：
//插入 bool Insert(const pair& kv) { //树为空 if (_root == nullptr) { _root = new Node(kv); return true; } //树不为空 Node* cur = _root; Node* perent = nullptr; while (cur) { if (kv.first > cur->_kv.first) { perent = cur; cur = cur->_right; } else if (kv.first _kv.first) { perent = cur; cur = cur->_left; } else { return false; } } //插入 cur = new Node(kv); if (kv.first > perent->_kv.first) { perent->_right = cur; } else { perent->_left = cur; } cur->_perent = perent; //更新平衡因子 while (perent) { if (cur == perent->_left)//插入节点位于左边 { --perent->_bf;//平衡因子-- } else//插入节点位于右边 { ++perent->_bf;//平衡因子++ } if (perent->_bf == 0)//平衡因子等于0 { break;//直接结束 } else if (perent->_bf == -1 || perent->_bf == 1)//平衡因子需要继续向上更新 { cur = perent;//更新cur为父节点 perent = perent->_perent;//更新父节点为父父节点 } else if (perent->_bf == -2 || perent->_bf == 2)//不满足AVL树，需要旋转处理 { //旋转 if (perent->_bf == -2 && cur->_bf == -1)//左边高 { RotateR(perent);//右单旋 } //剩余情况 //... break;//旋转完直接结束 } else { assert(false);//说明出现bug，报错处理 } } return true; }- 右旋转，顾名思义就是朝右边旋转。
- 条件：纯粹的左边高，观察上面的图，也就是根节点（parent）的左孩子节点（cur）的左子树高（a），导致根节点平衡因子超了。
- 注意：根节点的左孩子节点的左子树，也就是a，a的形状是不确定的，所以只关注cur的平衡因子。
- 所以右旋转条件写成代码就是：perent->_bf == -2 && cur->_bf == -1
2.左单旋
理解了右单旋，左单旋就好说了。
- 如上图展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。这里a/b/c是高度为h的子树， 是一种概括抽象表示，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体跟上面左旋类似。
- 在a子树中插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从1变成2，10为根的树左右高度差超过1，违反平衡规则。10为根的树右边太高了，需要往左边旋转，控制两棵树的平衡。
- 旋转核心步骤，因为10 _left;
//旋转过去
perent->_right = subRL;
subR->_left = perent;
Node* ppNode = perent->_perent;//父父节点
//更新父节点指针
if (subRL)
subRL->_perent = perent;
perent->_perent = subR;
//判断父父节点
if (perent == _root)
{
_root = subR;
subR->_perent = nullptr;
}
else
{
if (ppNode->_left == perent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_perent = ppNode;
}
subR->_bf = perent->_bf = 0;
}
- 和右单旋一样，先将b旋转过去，将subRL变成parent的右子树，将parent变为subR的左孩子，随后更新父节点指针，然后更新根节点，最后更新parent和subR的平衡因子。
完成左单旋后可以更新一下插入函数：
//插入 bool Insert(const pair& kv) { //树为空 if (_root == nullptr) { _root = new Node(kv); return true; } //树不为空 Node* cur = _root; Node* perent = nullptr; while (cur) { if (kv.first > cur->_kv.first) { perent = cur; cur = cur->_right; } else if (kv.first _kv.first) { perent = cur; cur = cur->_left; } else { return false; } } //插入 cur = new Node(kv); if (kv.first > perent->_kv.first) { perent->_right = cur; } else { perent->_left = cur; } cur->_perent = perent; //更新平衡因子 while (perent) { if (cur == perent->_left)//插入节点位于左边 { --perent->_bf;//平衡因子-- } else//插入节点位于右边 { ++perent->_bf;//平衡因子++ } if (perent->_bf == 0)//平衡因子等于0 { break;//直接结束 } else if (perent->_bf == -1 || perent->_bf == 1)//平衡因子需要继续向上更新 { cur = perent;//更新cur为父节点 perent = perent->_perent;//更新父节点为父父节点 } else if (perent->_bf == -2 || perent->_bf == 2)//不满足AVL树，需要旋转处理 { //旋转 if (perent->_bf == -2 && cur->_bf == -1)//左边高 { RotateR(perent);//右单旋 } else if (perent->_bf == 2 && cur->_bf == 1)//右边高 { RotateL(perent);//左单旋 } //其他情况... break;//旋转完直接结束 } else { assert(false);//说明出现bug，报错处理 } } return true; }- perent->_bf == 2 && cur->_bf == 1，也就是只有parent平衡因子为2并且subR（cur）平衡因子为1的情况，也就是纯粹的右边高，这时使用左单旋。
3.左右双旋
（1）问题引入
- 通过上面两图可以看到，左边高时，如果插入位置不是在a子树，而是插入在b子树，b子树高度从h变成h+1，引发旋转，右单旋无法解决问题，右单旋后，我们的树依旧不平衡。右单旋解决的是纯粹的左边高，但是插入在b子树中，10为跟的子树不再是单纯的左边高，对于10是左边高，但是对于5是右边高，这时需要用两次旋转才能解决。
- 判断是不是纯粹的左边高或者右边高，根据图，从新插入节点出发到根节点，如果是一条直线那么就是纯粹的一边高，如果是折线就不是。
（2）解决方法
首先我们子树的表示就直接用抽象图，前面已经解释过了，其实抽象子树最好一点就是其平衡因子不会发生变化，因为是当成一个整体移动。
- 第一步：将子树b拆分，拆分成一个具体节点（比5大比10小）和两棵抽象子树e和f
- 第二步：节点5为首的左子树，单独对这个左子树进行左单旋，将整棵树变为纯粹的左边高。
- 第三步：对整棵树进行右单旋，注意此时需要将上图中节点5的子树和子树f视为两颗抽象子树
因为先进行左单旋，后进行右单旋，所以取名左右双旋
（3）平衡因子更新
其实旋转过程很简单，只需要调用上面已经写好的单旋函数即可。真正难点是更新平衡因子，因为子树b被拆分成了e和f，那么新插入节点就有可能位于e也可能位于f，根据上图，e和f最终成为了根节点的左右孩子节点的右左子树。所以就会影响到根节点和左右孩子节点的平衡因子。
- 第一种：插入在e
- 此时parent=1，subL=0，subLR=0
- 第二种：插入在f
- 此时parent=0，subL=-1，subLR=0
- 其实还有第三种：b子树高度h=0，也就是b就是新插入节点
- 此时parent=0，subL=0，subLR=0
- 现在问题是如何判断插入位置？我们可以根据subLR的平衡因子进行判断，subLR=-1说明左边插入，subLR=1说明右边插入，subLR=0说明自己就是新增节点。
（5）左右双旋代码实现
//左右双旋 void RotateLR(Node* perent) { Node* subL = perent->_left; Node* subLR = subL->_right; int bf = subLR->_bf;//单旋前先记录平衡因子 RotateL(perent->_left);//先对左子树进行左单旋 RotateR(perent);//对整体进行右单旋 if (bf == -1)//左边高 { perent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 1)//右边高 { perent->_bf = 0; subL->_bf = -1; subLR = 0; } else if (bf == 0)//自己就是新增节点 { perent->_bf = 0; subL->_bf = 0; subLR = 0; } else//如果真走到这里说明有bug { assert(false); } }- 首先需要注意的是，调用单旋会把平衡因子更新为0，所以需要提前记录subLR的平衡因子。
- 然后，既然调用单旋会把平衡因子更新为0，那为什么还需要写bf==0的情况，这其实是一个好习惯，因为写了bf==0的情况那么无论单旋函数会不会将平衡因子变为0，都不会影响双旋函数更新平衡因子，这就是降低耦合性。
最后，我们继续完善一下插入函数代码中的旋转条件：
//插入 bool Insert(const pair& kv) { //树为空 if (_root == nullptr) { _root = new Node(kv); return true; } //树不为空 Node* cur = _root; Node* perent = nullptr; while (cur) { if (kv.first > cur->_kv.first) { perent = cur; cur = cur->_right; } else if (kv.first _kv.first) { perent = cur; cur = cur->_left; } else { return false; } } //插入 cur = new Node(kv); if (kv.first > perent->_kv.first) { perent->_right = cur; } else { perent->_left = cur; } cur->_perent = perent; //更新平衡因子 while (perent) { if (cur == perent->_left)//插入节点位于左边 { --perent->_bf;//平衡因子-- } else//插入节点位于右边 { ++perent->_bf;//平衡因子++ } if (perent->_bf == 0)//平衡因子等于0 { break;//直接结束 } else if (perent->_bf == -1 || perent->_bf == 1)//平衡因子需要继续向上更新 { cur = perent;//更新cur为父节点 perent = perent->_perent;//更新父节点为父父节点 } else if (perent->_bf == -2 || perent->_bf == 2)//不满足AVL树，需要旋转处理 { //旋转 if (perent->_bf == -2 && cur->_bf == -1)//左边高 { RotateR(perent);//右单旋 } else if (perent->_bf == 2 && cur->_bf == 1)//右边高 { RotateL(perent);//左单旋 } else if (perent->_bf == -2 && cur->_bf == 1)//左的中间高 { RotateLR(perent);//左右双旋 } //剩余情况... break;//旋转完直接结束 } else { assert(false);//说明出现bug，报错处理 } } return true; }
- 根据图就能发现，需要左右双旋的条件就是，subL的平衡因子=1.
- 也就是：perent->_bf == -2 && cur->_bf == 1
4.右左双旋
同理，我们先对右子树进行右单旋，再对整树进行左单旋。然后分三种情况讨论平衡因子的更新
- 跟左右双旋类似，下面我们将a/b/c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的细节进⼀步展开为12和左子树高度为h-1的e和f子树，因为我们要对b的父亲15为旋转点进行右单旋，右单旋需要动b树中的右子树。b子树中新增结点的位置不同，平衡因子更新的细节也不同，通过观察12的平衡因子不同，这里我们要分三个场景讨论。
- 场景1：h>=1时，新增结点插入在e子树，e子树高度从h-1变为h并不断更新12->15->10平衡因子，引发旋转，其中12的平衡因子为-1，旋转后10和12平衡因子为0，15平衡因子为1。
- 场景2：h>=1时，新增结点插入在f子树，f子树高度从h-1变为h并不断更新12->15->10平衡因子， 引发旋转，其中12的平衡因子为1，旋转后15和12平衡因子为0，10平衡因子为-1。
- 场景3：h==0时，a/b/c都是空树，b自己就是⼀个新增结点，不断更新15->10平衡因子，引发旋转，其中12的平衡因子为0，旋转后10和12和15平衡因子均为0
（1）右左双旋代码实现
//右左双旋 void RotateRL(Node* perent) { Node* subR = perent->_right; Node* subRL = subR->_left; int bf = subRL->_bf;//先记录平衡因子 RotateR(perent->_right);//先右单旋 RotateL(perent);//再左单旋 if (bf == -1) { perent->_bf = 0; subR->_bf = 1; subRL->_bf = 0; } else if (bf == 1) { perent->_bf = -1; subR->_bf = 0; subRL->_bf = 0; } else if (bf == 0) { perent->_bf = 0; subR->_bf = 0; subRL->_bf = 0; } else { assert(false); } }（2）插入函数最终版
//插入 bool Insert(const pair& kv) { //树为空 if (_root == nullptr) { _root = new Node(kv); return true; } //树不为空 Node* cur = _root; Node* perent = nullptr; while (cur) { if (kv.first > cur->_kv.first) { perent = cur; cur = cur->_right; } else if (kv.first _kv.first) { perent = cur; cur = cur->_left; } else { return false; } } //插入 cur = new Node(kv); if (kv.first > perent->_kv.first) { perent->_right = cur; } else { perent->_left = cur; } cur->_perent = perent; //更新平衡因子 while (perent) { if (cur == perent->_left)//插入节点位于左边 { --perent->_bf;//平衡因子-- } else//插入节点位于右边 { ++perent->_bf;//平衡因子++ } if (perent->_bf == 0)//平衡因子等于0 { break;//直接结束 } else if (perent->_bf == -1 || perent->_bf == 1)//平衡因子需要继续向上更新 { cur = perent;//更新cur为父节点 perent = perent->_perent;//更新父节点为父父节点 } else if (perent->_bf == -2 || perent->_bf == 2)//不满足AVL树，需要旋转处理 { //旋转 if (perent->_bf == -2 && cur->_bf == -1)//左边高 { RotateR(perent);//右单旋 } else if (perent->_bf == 2 && cur->_bf == 1)//右边高 { RotateL(perent);//左单旋 } else if (perent->_bf == -2 && cur->_bf == 1)//左的中间高 { RotateLR(perent);//左右双旋 } else if (perent->_bf == 2 && cur->_bf == -1)//右的中间高 { RotateRL(perent);//右左双旋 } else { assert(false); } break;//旋转完直接结束 } else { assert(false);//说明出现bug，报错处理 } } return true; }最后稍微总结一下双旋的思想：
- 由于插入位置不是纯粹的一边高，所以先针对插入节点的那棵子树，使用单旋将其调整为纯粹的一边高，最终对整体再进行一次单旋即可。
四、AVL树的查找
查找逻辑和普通的二叉搜索树一样，这里不再赘述
//查找 Node* Find(const K& key) { Node* cur = _root; while (cur) { if (key > cur->_kv.first) { cur = cur->_right; } else if (key _kv.first) { cur = cur->_left; } else { return cur; } } return nullptr; }五、AVL树的平衡检测
主要是检查我们写的代码有没有bug
- 为此，我们需要实现中序遍历：
void _InOrder(Node* root)//中序遍历 { if (root == nullptr) return; _InOrder(root->_left); cout _kv.first _left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; }- 然后就是判断平衡的IsBalanceTree函数，这个就是通过计算的左右子树高度，递归来判断树是否平衡，很好理解。比较好的一点就是可以指出出现异常的节点。
bool _IsBalanceTree(Node* root)//判断是否为AVL树 { //空树也是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 (abs(diff) >= 2) { cout _kv.first
- 然后就是判断平衡的IsBalanceTree函数，这个就是通过计算的左右子树高度，递归来判断树是否平衡，很好理解。比较好的一点就是可以指出出现异常的节点。
- 为此，我们需要实现中序遍历：
- 由于插入位置不是纯粹的一边高，所以先针对插入节点的那棵子树，使用单旋将其调整为纯粹的一边高，最终对整体再进行一次单旋即可。
- 第一种：插入在e
- 第三步：对整棵树进行右单旋，注意此时需要将上图中节点5的子树和子树f视为两颗抽象子树
- 第二步：节点5为首的左子树，单独对这个左子树进行左单旋，将整棵树变为纯粹的左边高。
- 第一步：将子树b拆分，拆分成一个具体节点（比5大比10小）和两棵抽象子树e和f
- perent->_bf == 2 && cur->_bf == 1，也就是只有parent平衡因子为2并且subR（cur）平衡因子为1的情况，也就是纯粹的右边高，这时使用左单旋。
- 和右单旋一样，先将b旋转过去，将subRL变成parent的右子树，将parent变为subR的左孩子，随后更新父节点指针，然后更新根节点，最后更新parent和subR的平衡因子。
- AVL树的基本框架与搜索二叉树有点不同，主要是节点定义的区别：
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。
