【高阶数据结构】平衡二叉树(AVL)的插入（4种旋转方法+精美图解+完整代码）
🤡博客主页：醉竺
🥰本文专栏：《高阶数据结构》
😻欢迎关注：感谢大家的点赞评论+关注，祝您学有所成！
✨✨💜💛想要学习更多《高阶数据结构》点击专栏链接查看💛💜✨✨
目录
1. 平衡二叉树的概念
2. 最小不平衡子树
3. 插入操作后的平衡性调整
3.1 LL型插入
3.2 RR型插入
3.3 LR型插入
3.4 RL型插入
3.5 完整插入逻辑代码实现
4. AVLTree完整代码提供
5. 平衡二叉树(AVL)的删除和调整
上一篇文章中我们学习了《二叉搜索树的插入、删除和查找》，二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
为了提高查找效率，应该尽可能地让二叉查找树的高度变得最小。
解决方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。这就是“平衡二叉树”的由来。
平衡二叉树作为后续红黑树学习的铺垫，很容易被人忽略。这节课，我们就来捋清“达到平 衡”的思路，避免在写代码的时候手忙脚乱，也为后续的学习打好基础。
1. 平衡二叉树的概念
平衡二叉树也叫平衡二叉搜索树，英文名是Balanced Binary Tree，简称AVL树（平衡树）。AVL名字取自于发明平衡二叉树的两个人名字（Adelson-Velsky 以及 Landis）中的字母。平衡二叉树，首先是一棵二叉搜索树，在构建这棵二叉搜索树的过程中进行平衡化的处理形成平衡二叉树。
要理解平衡二叉树，就要先引入平衡因子BF（Balance Factor）的概念：该节点左子树的高度减去右子树的高度。有的资料上也会用右子树高度减去左子树高度，也是可以的。
平衡二叉树或者是空树，或者具有以下性质的平衡二叉树：
- 左右子树高度差的绝对值不超过 1（-1 / 0 / 1）；
- 左右子树也是平衡二叉树(AVL);
例如下图所示：
所以，一棵平衡二叉树上任一节点的平衡因子只能是-1、0、1三个值中的一个。观察上图左侧二叉查找树各个节点的平衡因子值，显然就是一棵平衡二叉树。而右侧就不是 。
2. 最小不平衡子树
目前，要解决的主要问题是 在插入一个新的节点后，保持原有二叉搜索树的平衡。比如下面第一个图中，当插入新节点（值为67）时，插入路线上所经过的所有节点的平衡因子都发生了改变，二叉树不再保持平衡，退化成了普通的二叉查找树。那么，为了提高查找效率，就要对二叉树进行平衡性调整。
在图2中，插入新节点67后，节点50、66、70的平衡因子因为不在-1到1之间，从而打破了这棵二叉树的平衡。那么就从插入的新节点67回溯，经过节点68，找到第一个不平衡的节点70，对以这个节点为根的子树（包含节点70、68、67）进行平衡性调整就可以了。
这里将以节点70为根的这棵需要进行平衡性调整的子树称为“最小不平衡子树”。之所以称为“最小”，是因为任何其他不平衡子树所包含的节点数量，比如以节点 50和66 为根的树中，都比这棵以70为根的“最小不平衡子树”包含的节点数量多。
只要将这棵“最小不平衡子树”调整平衡，其他不平衡节点的平衡因子都会恢复到原来的值。调整后的二叉平衡树如下图所示。
这里说一个结论：
只要将最小不平衡子树进行平衡性调整（高度复原），整个二叉搜索树就会恢复平衡。
为什么只需要对最小不平衡子树进行平衡性调整就可以恢复整个二叉搜索树？
- 局部性：平衡树的性质保证了树的高度是平衡的，即每个节点的左右子树高度差不超过1。当插入或删除一个节点时，可能会导致某个节点的平衡因子超出这个范围，但这种不平衡是局部的，只会影响到从插入或删除节点到根节点路径上的某些节点。
- 旋转操作的性质（后续会讲解）：旋转操作（如单旋转、双旋转）可以调整节点的相对位置，使得子树的高度重新平衡，同时保持二叉搜索树的性质（即左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值）。旋转操作只影响旋转节点及其子节点，不会影响其他部分的树结构。
- 平衡因子的传递性：在平衡树中，平衡因子的传递性保证了当一个节点变得不平衡时，其祖先节点的平衡因子也会受到影响。但是，通过旋转操作恢复最小不平衡子树的平衡后，其祖先节点的平衡因子也会相应地调整，从而保证整个树的平衡。
上述解释如果不明白也没事，观察图也能看出这个结论，无需证明。
3. 插入操作后的平衡性调整
平衡性调整是通过对该二叉树进行“旋转”操作来达成的。旋转被分为四种旋转方式，分别为左旋，右旋，先左后右旋转，先右后左旋转。其中前两个又叫做单旋转，后两个又叫做双旋转。每一次旋转，都会导致孩子节点变成父亲节点，父亲节点变成孩子节点，这一点印象通过后面的学习会进一步加深。
而对于最小不平衡子树（将该子树命名为A）的产生又分为以下四种情况。
在A的“左孩子的左子树”中插入节点导致A不平衡（简称LL：L代表左Left）。此时需要通过“右旋转”来调整平衡。
在A的“右孩子的右子树”中插入节点导致A不平衡（简称RR：R代表右Right）。此时需要通过“左旋转”来调整平衡。
在A的“左孩子的右子树”中插入节点导致A不平衡（简称LR）。此时需要通过“先左后右旋转”来调整平衡。
在A的“右孩子的左子树”中插入节点导致A不平衡（简称RL）。此时需要通过“先右后左旋转”来调整平衡。
下面先给出二叉平衡树节点的定义和AVL树类的整体框架，为后面具体的代码实现做铺垫：
AVLTreeNode:
相比于普通的二叉搜索树的节点，二叉平衡树节点的定义采用了三叉链表的方式，即多增加了一个指向父节点的指针，这对后续处理较为方便，STL模板中有关红黑树的源码实现也是三叉链表。节点中存储的数据是pair键值对，这也与源码相匹配，并且每个节点中还有一个平衡因子。
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;// 左子节点
AVLTreeNode<K, V>* _right;// 右子节点
AVLTreeNode<K, V>* _parent;// 父节点
pair<K, V> _kv;// 键值对
int _bf;// 平衡因子
// 构造函数，初始化节点
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};AVLTree类：
这里只给出了成员变量，具体的成员函数和实现这里暂时先不提供，后续学习会提供相关插入和相关平衡调整的方法，这里先了解一下大致框架。
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
private:
Node* _root = nullptr;
};3.1 LL型插入
在A的“左孩子的左子树”中插入节点导致A不平衡（简称LL）
将LL插入导致失衡的二叉排序树重新调整为平衡的结构如下图所示，请认真观察：
想一想，上图中的最小不平衡子树恢复平衡是怎么做呢？
答：通过右旋转的方式，可以理解为左边长了就向右转，使其变短(变矮)，用语言描述就是：
LL插入（向右单旋转）：
由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的最小平衡子树失去平衡，因此需要一次向右的旋转操作。
将失衡的A结点向右旋转，来作为B的右子树的根结点。此时，A原先的左孩子B就代替了A成为最小不平衡子树的根节点。再将B节点的右子树(nullpter也算)，作为A节点的左子树（在代码中这应是第一步）。
结构图较为抽象，我也给你列举了具体的例子参考：
针对上图LL型插入的具体例子中的三个二叉排序树，重新调整为平衡二叉树后如下图所示：
观察上面两图的调整结果，不难得到几个结论。
-
插入新节点导致失衡前这个子树有多高，调整平衡后这个树就会恢复为多高。
比如中间的这棵树，本来高度为3，增加新节点20后，高度变为4并失衡，重新调整平衡后树的高度又恢复为3。
-
将一棵最小不平衡子树进行平衡性调整平衡后，这棵调整后的子树的根的平衡因子变为0。
比如上图最右侧的这棵树，最小不平衡子树的根节点是95，失衡前该节点的平衡因子是1，失衡后该节点的平衡因子是2，进行平衡性调整后，这棵调整后的子树的根变成了节点60，同时这个根（节点60）的平衡因子为0（不用理会原来是多少）。
上面的结论同样适用于RR、LR、RL的情况，所以还是要好好理解。你可以多在纸上演练几遍平衡性调整的过程，理清思路。
接下来，我们就要说说平衡性调整的程序编写思路了。
首先，新插入的节点的平衡因子自然是0,因为新插入的节点肯定是叶子节点。
其次，沿着新插入的节点向上逐个找寻父节点并调整父节点的平衡因子。 虽然理论上来说，插入路线上经过的所有节点的平衡因子都会发生改变，但是一旦找到最小不平衡子树并对这个子树调整平衡后，其他不平衡的节点的平衡因子都会恢复到不平衡之前的原值。这意味着此时“插入路线上所经过的所有没调整平衡因子的节点的平衡因子”不需要再调整了，因为他们应该保持原值。这句话有点难，该怎么理解呢？我们可以结合下图进一步解释一下。
-
最左侧的这棵树，节点95和60的平衡因子是1，当插入新节点20时，导致这棵二叉排序树失衡，此时理论上来说节点95和节点60的平衡因子都应该变为2，如上图中间这棵树。
-
但写程序时会从下向上（用一个循环）修改节点的平衡因子——新插入的节点20为叶子节点，平衡因子自然为0，然后将节点40的平衡因子从0修改为1，接着将节点60的平衡因子从1修改为2，此时注意节点95的平衡因子还没有被修改，依然保持为1。因为节点60的平衡因子为2，显然节点60、40、20是一棵最小不平衡子树，要进行平衡性调整，调整后的新子树以节点40为根并且节点40的平衡因子变为0，节点60的平衡因子也变为0，如上图最右侧这棵树。
-
此时，整个二叉排序树就平衡了，平衡性调整结束，不再需要修改节点95的平衡因子，还是保持原值1（上图左侧这棵树中的就是原值）即可。
右旋：下面的注释非常详细，可以比对着右旋的操作过程和结构图阅读！这里我再放一下图
在旋转过程中，有以下几种情况需要考虑：
（1）在旋转的过程中B的右孩子可能存在，也可能不存在
（2）A可能是整个AVL树的根节点，也可能只是一个子树
- 如果是根节点，旋转完成后，要更新根节点
- 如果是子树，可能是某个节点的左子树，也可能是右子树
// 右旋转
void RotateR(Node* A) // A是最小不平衡子树的根节点
{
Node* B = A->_left; // B是A的左孩子
Node* BR = B->_right; //BR是B的右孩子
Node* gf = A->_parent; //这里记录A的父节点的gf，为后续旋转操作后的父节点更新做准备
A->_left = BR; // A的左孩子指向BR(B的右孩子BR也可能为nullptr,但是不影响此操作)
if (BR != nullptr)
BR->_parent = A; // 这里BR已经成为A的左孩子(若不为空)，所以需要更新BR的父节点为A
B->_right = A; // 由于A右旋，此时A成为了B的右孩子。B原本的右孩子BR已经成为A的左孩子
A->_parent = B; // 更新A的父节点为B
if (_root == A) // 如果A是整棵AVL树的根节点_root
{
_root = B; // 此时旋转后的B节点代替A成为新的根节点
B->_parent = nullptr;
}
else // 如果A不是整棵AVL树的根节点（只是最小不平衡子树的根节点），则A的之前的父节点gf需要指向B
{
if (gf->_left == A) // 若之前A是gf的左孩子，B代替了A，则gf的左孩子指向B
{
gf->_left = B;
}
else // 若之前A是gf的右孩子，B代替了A，则gf的右孩子指向B
{
gf->_right = B;
}
B->_parent = gf; // 同样需要更新B的父节点指向为gf
}
A->_bf = B->_bf = 0; // 更新最小不平衡子树右旋后部分节点的平衡因子
}3.2 RR型插入
在A的“右孩子的右子树”中插入节点导致A不平衡（简称RR）
结构图较为抽象，我也给你列举了一些具体的例子参考。
针对上图具体例子的三个二叉排序树，重新调整为平衡二叉树后如图所示。
那么如何通过左旋转（右边长了就向左转）让上图中的最小不平衡子树恢复平衡呢？用语言描述只需要一句话：
RR型插入（向左单旋转）：
将失衡的A节点向左侧旋转，来作为B的左子树的根节点。此时，A原先的右孩子B就代替了A成为最小不平衡子树的根节点。再将B节点的左子树(nullptr也算)，作为A节点的右子树(在代码中这应是第一步)。
RR型插入的调整需要左旋，实现逻辑跟LL型的右旋类似，代码实现如下：
左旋：
// 左旋转
void RotateL(Node* A)
{
Node* B = A->_right; // B是A的右孩子
Node* BL = B->_left; // BL是B的左孩子
Node* gf = A->_parent; // 记录A的父节点的gf，为后续旋转操作后的父节点更新做准备
A->_right = BL; // A的右孩子指向BL(B的左孩子BL也可能为nullptr,但是不影响此操作)
if (BL != nullptr)
BL->_parent = A; // 这里BL已经成为A的右孩子(若不为空)，所以需要更新BL的父节点为A
B->_left = A; // 由于A左旋，此时A成为了B的左孩子。B原本的左孩子BL已经成为A的右孩子
A->_parent = B; // 更新A的父节点为B
if (_root == A) // 如果A是整棵AVL树的根节点_root
{
_root = B; // 此时旋转后的B节点代替A成为新的根节点
B->_parent = nullptr;
}
else // 如果A不是整棵AVL树的根节点（只是最小不平衡子树的根节点），则A的之前的父节点gf需要指向B
{
if (gf->_left == A) // 若之前A是gf的左孩子，B代替了A，则gf的左孩子指向B
{
gf->_left = B;
}
else // 若之前A是gf的右孩子，B代替了A，则gf的右孩子指向B
{
gf->_right = B;
}
B->_parent = gf; // 同样需要更新B的父节点指向为gf
}
A->_bf = B->_bf = 0; // 更新最小不平衡子树左旋后部分节点的平衡因子
}3.3 LR型插入
在子树A的“左孩子的右子树”中插入节点导致A不平衡（LR）
下图所示的几棵二叉搜索树都属于在A的“左孩子的右子树”中插入节点导致失衡的情形。
针对图中的三个二叉排序树，重新调整为平衡二叉树后如下图所示。观察的时候注意对照上下两张图，一定要自己先认真观察一下，思考一下过程。其实就是上面已经学过的左旋和右旋进行组合。
那么如何通过先左后右旋转让上上图中的最小不平衡子树恢复平衡呢？简单来说，就是通过一次左旋转（前面已学）先让节点95、60、70处于一条直线上(斜着的直线)，然后再通过一次右旋转（前面已学）让失衡子树恢复平衡。
LR型插入 （先左后右双旋转）：
由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。
先将A节点的左孩子B进行左旋转，此时B节点原先的右孩子C就代替了B的位置；然后再将失衡的A节点进行右旋转，此时节点C就代替了原先A的位置，至此二叉搜索树达到平衡。
简而言之就是，先对A的左孩子B节点左旋，再对B的右孩子C节点右旋。
下面演示的是在C的右子树插入一个节点的具体调整过程：
LR型插入是在A左孩子的右子树（即B的右子树）上插入一个节点导致的失衡，由上上个图可知，这个节点的插入位置有3种情况：
- 插入的位置是A左孩子的右子树的根节点 （例如C节点）
- 插入的位置的是C的左子树（也属于A左孩子的右子树范畴）
- 同理，插入的位置是C的右子树（也属于A左孩子的右子树范畴）
上面提供的具体例子的图中就包含了这3种情况，为了方便阅读这里再次贴上，如下，
上图可以理解为，95就是A节点，60是A的左孩子即B节点，70是C节点。上图从左到右插入的位置，正好对应了上述的3种情况。 此时对应着有：
1. 70平衡因子bf为0，代表它就是新插入的节点；2. 70的平衡因子为1，代表在它的左子树新插入了节点；3. 70的平衡因子为-1，代表在它的右子树新插入了节点。
3种情况插入调整后，节点A(95), B(60), C(70)的平衡因子最终为：1. 0,0,0； 2. -1,0,0；3. 0,1,0
比对着LR旋转操作，以及上面的两张图的情况，下面是LR型插入后旋转调整的代码实现：
// LR型插入
// 先左旋，再右旋
void RotateLR(Node* A) // A为最小不平衡子树的根节点
{
Node* B = A->_left;
Node* C = B->_right;
int old_bf = C->_bf; // 记录C的原来的平衡因子，以判断新增节点插入的位置
RotateL(A->_left); // 等价于RotateL(B)
RotateR(A);
// 判断LR插入节点的位置
if (old_bf == 0) // C自己就是新增
{
A->_bf = B->_bf = C->_bf = 0; // LR旋转调整后，原最小不平衡子树上相关节点ABC的平衡因子更新
}
else if (old_bf == 1) // C的左子树为新增
{
A->_bf = -1;
B->_bf = 0;
C->_bf = 0;
}
else if (old_bf == -1 ) // C的右子树为新增
{
A->_bf = 0;
B->_bf = 1;
C->_bf = 0;
}
else
{
assert(false); // 平衡因子只能为-1、0、1
}
}3.4 RL型插入
在子树A的“右孩子的左子树”中插入节点导致A不平衡（RL）
这种情况与LR正好相反，先来看一下结构示意图。
下图所示的几棵二叉查找树都属于在A的“右孩子的左子树”中插入节点导致失衡的情形：
针对图中的三个二叉排序树，重新调整为平衡二叉树后如图所示。
那么如何通过先右后左旋转让上上图中的最小不平衡子树恢复平衡呢？简单说来就是通过一次右旋转（前面讲解过）先让节点60、120、95处于一条直线上（斜着的），然后再通过一次左旋转（前面讲解过）让失衡子树恢复平衡。
RL型插入（先右后左双旋转）：
由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡因子由 -1减至 -2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。
先将A节点的右孩子B进行右旋转，此时B节点原先的左孩子C就代替了B的位置；然后再将失衡的A节点进行左旋转，此时节点C就代替了原先A的位置，至此二叉搜索树达到平衡。
简而言之就是，先对A的右孩子B节点右旋，再对B的左孩子C节点左旋。
下面演示的是在C的左子树插入一个节点的具体调整过程：
RL型插入是在A右孩子的左子树（即B的左子树）上插入一个节点导致的失衡，由上上个图可知，这个节点的插入位置有3种情况：
- 插入的位置是A右孩子的左子树的根节点 （例如C节点）
- 插入的位置的是C的左子树（属于A右孩子的左子树的范畴）
- 同理，插入的位置是C的右子树（属于A右孩子的左子树的范畴）
上面提供的具体例子的图中就包含了这3种情况，为了方便阅读这里再次贴上，如下，
上图可以理解为，60就是A节点，120是A的右孩子即B节点，95是C节点。上图从左到右插入的位置，正好对应了上述的3种情况。 此时对应着有：
1. 95衡因子bf为0，代表它就是新插入的节点；2. 95的平衡因子为1，代表在它的左子树新插入了节点；3. 95的平衡因子为-1，代表在它的右子树新插入了节点。
3种情况插入调整后，节点A(60), B(120), C(95)的平衡因子最终为：1. 0,0,0； 2. 0,-1,0；3. 1,0,0
比对着LR旋转操作，以及上面的两张图的情况，下面是RL型插入旋转调整的代码实现：
// RL型插入
// 先右旋，再左旋
void RotateRL(Node* A) // A为最小不平衡子树的根节点
{
Node* B = A->_right;
Node* C = B->_left;
int old_bf = C->_bf; // 记录C的原来的平衡因子，以判断新增节点插入的位置
RotateR(A->_right); // 等价于RotateR(B)
RotateL(A);
if (old_bf == 0) // C自己就是新增
{
A->_bf = B->_bf = C->_bf = 0;
}
else if (old_bf == 1) // C的左子树为新增
{
A->_bf = 0;
B->_bf = -1;
C->_bf = 0;
}
else if (old_bf == -1) // C的右子树为新增
{
A->_bf = 1;
B->_bf = 0;
C->_bf = 0;
}
else
{
assert(false); // 平衡因子只能为-1、0、1
}
}3.5 完整插入逻辑代码实现
插入逻辑的完整代码实现如下，进行了详细注释：
bool Insert(const pair<K, V>& kv) // 插入kv节点
{
// 1、如果树为空，则插入一个节点作为根节点
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->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false; // 已经存在相同的键值，插入失败
}
}
cur = new Node(kv); // cur指向新待插入的节点
// 2、根据kv.first的大小决定插入左子树还是右子树
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
// 3、节点已经插入，从下往上更新每个节点的高度和平衡因子
// cur是新插入的节点，平衡因子为0；parent是其父节点，从parent开始向上更新平衡因子
while (parent)
{
if (cur == parent->_left)
{
parent->_bf++; // 平衡因子等于左-右，若插入左子树，则_bf++，
}
else
{
parent->_bf--; // 若插入右子树，则_bf--，
}
if (parent->_bf == 0) // 父节点的平衡因子为0，说明插入新节点后未影响父节点的高度,
{ // 更不会影响上面祖宗节点的高度，依然平衡无需调整，退出循环
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) // 父节点的平衡因子为1或-1，影响了父节点的高度
{ // 则也会影响上面祖宗节点的高度，需要继续向上更新节点的bf
cur = parent; // 看是否有失衡的节点
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 找到了最小不平衡子树的根节点，需要旋转调整
{
if (parent->_bf == 2 && cur->_bf == 1) // LL型插入
{
RotateR(parent); // 右旋
}
else if (parent->_bf == -2 && cur->_bf == -1) // RR型插入
{
RotateL(parent); // 左旋
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateLR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateRL(parent);
}
// 1、旋转让这颗子树平衡了
// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
break;
}
else
{
assert(false); // 平衡因子（包括失衡）只能为-1,0,1,-2,2
}
}// end while
return true;
}4. AVLTree完整代码提供
除了插入，其它成员函数的实现跟二叉搜索树一样，具体讲解感兴趣的点进本篇文章专栏，看二叉搜索树那篇文章~
AVLTree.h
#pragma once
#include<assert.h>
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;// 左子节点
AVLTreeNode<K, V>* _right;// 右子节点
AVLTreeNode<K, V>* _parent;// 父节点
pair<K, V> _kv;// 键值对
int _bf;// 平衡因子
// 构造函数，初始化节点
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(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) // 插入kv节点
{
// 1、如果树为空，则插入一个节点作为根节点
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->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false; // 已经存在相同的键值，插入失败
}
}
cur = new Node(kv); // cur指向新待插入的节点
// 2、根据kv.first的大小决定插入左子树还是右子树
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
// 节点已经插入，从下往上更新每个节点的高度和平衡因子
// cur是新插入的节点，平衡因子为0；parent是其父节点，从parent开始向上更新平衡因子
while (parent)
{
if (cur == parent->_left)
{
parent->_bf++; // 平衡因子等于左-右，若插入左子树，则_bf++，
}
else
{
parent->_bf--; // 若插入右子树，则_bf--，
}
if (parent->_bf == 0) // 父节点的平衡因子为0，说明插入新节点后未影响父节点的高度,
{ // 更不会影响上面祖宗节点的高度，依然平衡无需调整，退出循环
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) // 父节点的平衡因子为1或-1，影响了父节点的高度
{ // 则也会影响上面祖宗节点的高度，需要继续向上更新节点的bf
cur = parent; // 看是否有失衡的节点
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 找到了最小不平衡子树的根节点，需要旋转调整
{
if (parent->_bf == 2 && cur->_bf == 1) // LL型插入
{
RotateR(parent); // 右旋
}
else if (parent->_bf == -2 && cur->_bf == -1) // RR型插入
{
RotateL(parent); // 左旋
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateLR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateRL(parent);
}
// 1、旋转让这颗子树平衡了
// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
break;
}
else
{
assert(false); // 平衡因子（包括失衡）只能为-1,0,1,-2,2
}
}// end while
return true;
}
// LL型插入，右旋
void RotateR(Node* A) // A是最小不平衡子树的根节点
{
Node* B = A->_left; // B是A的左孩子
Node* BR = B->_right; //BR是B的右孩子
Node* gf = A->_parent; //这里记录A的父节点的gf，为后续旋转操作后的父节点更新做准备
A->_left = BR; // A的左孩子指向BR(B的右孩子BR也可能为nullptr,但是不影响此操作)
if (BR != nullptr)
BR->_parent = A; // 这里BR已经成为A的左孩子(若不为空)，所以需要更新BR的父节点为A
B->_right = A; // 由于A右旋，此时A成为了B的右孩子。B原本的右孩子BR已经成为A的左孩子
A->_parent = B; // 更新A的父节点为B
if (_root == A) // 如果A是整棵AVL树的根节点_root
{
_root = B; // 此时旋转后的B节点代替A成为新的根节点
B->_parent = nullptr;
}
else // 如果A不是整棵AVL树的根节点（只是最小不平衡子树的根节点），则A的之前的父节点gf需要指向B
{
if (gf->_left == A) // 若之前A是gf的左孩子，B代替了A，则gf的左孩子指向B
{
gf->_left = B;
}
else // 若之前A是gf的右孩子，B代替了A，则gf的右孩子指向B
{
gf->_right = B;
}
B->_parent = gf; // 同样需要更新B的父节点指向为gf
}
A->_bf = B->_bf = 0; // 更新最小不平衡子树右旋后部分节点的平衡因子
}
// RR型插入，左旋
void RotateL(Node* A)
{
Node* B = A->_right; // B是A的右孩子
Node* BL = B->_left; // BL是B的左孩子
Node* gf = A->_parent; // 记录A的父节点的gf，为后续旋转操作后的父节点更新做准备
A->_right = BL; // A的右孩子指向BL(B的左孩子BL也可能为nullptr,但是不影响此操作)
if (BL != nullptr)
BL->_parent = A; // 这里BL已经成为A的右孩子(若不为空)，所以需要更新BL的父节点为A
B->_left = A; // 由于A左旋，此时A成为了B的左孩子。B原本的左孩子BL已经成为A的右孩子
A->_parent = B; // 更新A的父节点为B
if (_root == A) // 如果A是整棵AVL树的根节点_root
{
_root = B; // 此时旋转后的B节点代替A成为新的根节点
B->_parent = nullptr;
}
else // 如果A不是整棵AVL树的根节点（只是最小不平衡子树的根节点），则A的之前的父节点gf需要指向B
{
if (gf->_left == A) // 若之前A是gf的左孩子，B代替了A，则gf的左孩子指向B
{
gf->_left = B;
}
else // 若之前A是gf的右孩子，B代替了A，则gf的右孩子指向B
{
gf->_right = B;
}
B->_parent = gf; // 同样需要更新B的父节点指向为gf
}
A->_bf = B->_bf = 0; // 更新最小不平衡子树左旋后部分节点的平衡因子
}
// LR型插入
// 先左旋，再右旋
void RotateLR(Node* A) // A为最小不平衡子树的根节点
{
Node* B = A->_left;
Node* C = B->_right;
int old_bf = C->_bf; // 记录C的原来的平衡因子，以判断新增节点插入的位置
RotateL(A->_left); // 等价于RotateL(B)
RotateR(A);
// 判断LR插入节点的位置
if (old_bf == 0) // C自己就是新增
{
A->_bf = B->_bf = C->_bf = 0; // LR旋转调整后，原最小不平衡子树上相关节点ABC的平衡因子更新
}
else if (old_bf == 1) // C的左子树为新增
{
A->_bf = -1;
B->_bf = 0;
C->_bf = 0;
}
else if (old_bf == -1) // C的右子树为新增
{
A->_bf = 0;
B->_bf = 1;
C->_bf = 0;
}
else
{
assert(false); // 平衡因子只能为-1、0、1
}
}
// RL型插入
// 先右旋，再左旋
void RotateRL(Node* A) // A为最小不平衡子树的根节点
{
Node* B = A->_right;
Node* C = B->_left;
int old_bf = C->_bf; // 记录C的原来的平衡因子，以判断新增节点插入的位置
RotateR(A->_right); // 等价于RotateR(B)
RotateL(A);
if (old_bf == 0) // C自己就是新增
{
A->_bf = B->_bf = C->_bf = 0;
}
else if (old_bf == 1) // C的左子树为新增
{
A->_bf = 0;
B->_bf = -1;
C->_bf = 0;
}
else if (old_bf == -1) // C的右子树为新增
{
A->_bf = 1;
B->_bf = 0;
C->_bf = 0;
}
else
{
assert(false); // 平衡因子只能为-1、0、1
}
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
int Height()
{
return _Height(_root);
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
size_t Size()
{
return _Size(_root);
}
size_t _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
Node* Find(const K& key)
{
return _Find(_root, key);
}
Node* _Find(Node* root, const K& key)
{
if (root == nullptr || root->_kv.first == key)
return root;
if (key < root->_kv.first)
return _Find(root->_left, key);
else
return _Find(root->_right, key);
}
bool IsBalance()
{
return _IsBalance(_root);
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
return true;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
if (leftHeight - rightHeight != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return abs(leftHeight - rightHeight) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
private:
Node* _root = nullptr;
};Test_AVLTree.cpp
#include<iostream>
#include<map>
#include<vector>
using namespace std;
#include"AVLTree.h"
void test1()
{
map<string, string> dict;
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("left", "剩余"));
dict.insert(make_pair("right", "右边"));
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
}
void test2()
{
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
AVLTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}
t.InOrder();
cout << t.IsBalance() << endl;
}
void test3()
{
const int N = 30;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand());
cout << v.back() << endl;
}
AVLTree<int, int> t;
for (auto e : v)
{
if (e == 14604)
{
int x = 0;
}
t.Insert(make_pair(e, e));
cout << "Insert:" << e << "->" << t.IsBalance() << endl;
}
cout << t.IsBalance() << endl;
}
int main()
{
//test1();
//test2();
test3();
return 0;
}5. 平衡二叉树(AVL)的删除和调整
《平衡二叉树(AVL)的删除和调整》
https://blog.csdn.net/weixin_43382136/article/details/140577239