Re：从零开始的 C++ STL篇（八）深度解构AVL树自平衡机制：平衡维护与旋转调整背后的严密逻辑

Ne0inhk

26 Mar 2026 — 29 min read

◆ 博主名称：晓此方-ZEEKLOG博客大家好，欢迎来到晓此方的博客。⭐️C++系列个人专栏：主题曲:C++程序设计⭐️ 踏破千山志未空，拨开云雾见晴虹。人生何必叹萧瑟，心在凌霄第一峰

概要&序論

这里是此方，好久不见。 本文旨在深入剖析 AVL树 —— 一种自平衡的二叉搜索树。我们将从最核心的概念入手，包括平衡因子、节点高度、旋转操作，逐步展开对其算法逻辑、插入调整机制以及实际应用场景的全面解析。让我们现在开始吧！

本文代码示例及测试所需要的头文件：

#pragmaonce#include<iostream>#include<cassert>#include<vector>#include<ctime>usingnamespace std;

一，AVL树的概念：最早的自平衡二叉树

1.1什么是AVL树

AVL树是最先发明的自平衡二叉搜索树，AVL是一颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，他们在1962年的论文《An algorithm for the organization of information》 中发表了它。

1.2平衡因子的概念

AVL树实现这里我们引入一个平衡因子(balance factor)的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。

Tips：为什么高度差不超过1

思考一下为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差是0呢？0不是更好的平衡吗？画画图分析我们发现，不是不想这样设计，而是有些情况是做不到高度差是0的。 比如一棵树是2个结点，4个结点等情况下，高度差最好就是1，无法做到高度差是0。

1.3AVL树的优势

AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在 logN，那么增删查的效率也可以控制在 O(logN)，相比二叉搜索树有了本质的提升。

二，搭建总体结构：AVL树和二叉树的结构有何不同

还是和二叉搜索树一样，我们先写一个总的结构。

template<classK,classV>structAVLTreeNode{ pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent;int _bf;// balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<classK,classV>classAVLTree{typedef AVLTreeNode<K, V> Node;public://...

我们看看相比二叉搜索树，AVL树的结点结构多了什么？首先是平衡因子，我们上面讲过了。然后是parent指针，没错，AVL树最适合的结构不是二叉链而是三叉链。为什么这么设计我们先卖一个关子。

三，实现AVL树的插入：在二叉树的基础上维护平衡因子

3.1首先按照二叉搜索树的规则进行插入

AVL树，他首先是一颗二叉搜索树，那么插入一个值就应该按二叉搜索树规则进行插入。我这里直接CV一下上一篇文章的代码，没有搞明白的小伙伴可以去看我的上一篇博文哦。注意一下插入后要多一步链接父亲结点。

boolInsert(const K& key,const V& value){if(_root ==nullptr){ _root =newNode(key, value);returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}elseif(cur->_key == key)returnfalse;} cur=newNode(key, value);if(parent->_key > cur->_key) parent->_left = cur;elseif(parent->_key < cur->_key) parent->_right = cur; cur->_parent = parent;//..........returntrue;}

3.2平衡因子的更新

新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。

3.2.1更新平衡因子的原则

平衡因子 = 右子树高度 - 左子树高度(可以是左-右，但是一般都是右-左)只有当前结点子树高度变化才会影响当前结点平衡因子。插入结点，会增加高度所以：
新增结点在 parent 的右子树，parent 的平衡因子 ++，新增结点在 parent 的左子树，parent 平衡因子 --parent 所在子树的高度是否变化决定了是否会继续往上更新。

收回伏笔：向上查找更新平衡因子。所以需要三叉链结构，这样方便一点。有的牛逼的人会选择不去存这个 parent，而是用一个容器（栈或队列）来存储这个插入结点的所有祖先，然后按照一个指定的顺序来查找修改平衡因子。

3.2.2更新停止条件

根据平衡因子的更新结果，有三种情况：

3.2.2.1情况一：更新后 parent 的平衡因子等于 0

这种情况怎么来的？ 必然是更新中 parent 的平衡因子从 -1->0 或者 +1->0。
更新前平衡因子是+1/-1，说明更新前 parent 子树一边高一边低，新增的结点插入在低的那边，插入后 parent 所在的子树高度不变 ，不会影响 parent 的父亲结点的平衡因子，更新结束。
防止没有听明白，我找个图给大家看看：

如图，parent结点（3）的平衡因子从1变成0，插入后 parent 所在的子树高度不变，不会影响 parent 的父亲结点的平衡因子，更新结束。

3.2.2.2情况二：更新后 parent 的平衡因子等于 1 或 -1

更新前更新中 parent 的平衡因子变化为 0->1 或者 0->-1。

为什么不可能是从+2/-2更新到+1/-1？ 因为插入新的结点才会引发更新，而插入新的结点的大前提是在插入之前你插入的是一颗AVL树。而存在某一个结点的平衡因子是+2/-2，这就tm不是一颗AVL树。

说明更新前 parent 子树两边一样高，新增的插入结点后，parent 所在的子树一边高一边低，parent 所在的子树符合平衡要求，但是高度增加了 1，会影响 parent 的父亲结点的平衡因子，所以要继续向上更新。
还是找一张图来解释：

如图，插入结点后，parent（6）从0->1,所在子树高度发生变化，继续向上更新；parent（3）从0->1，所在子树高度发生变化，继续向上更新，以此类推直到更新到根节点，再不可向上继续更新，更新方才结束。

3.2.2.3情况三：更新后 parent 的平衡因子等于 2 或 -2

更新前更新中 parent 的平衡因子变化为 1->2 或者 -1->-2，说明更新前 parent 子树一边高一边低。新增的插入结点在高的那边，parent 所在的子树高的那边更高了，破坏了平衡。平衡因子异常

如上图，parent（14）平衡因子从0->-1，所在子树高度发生变化，继续向上调整，parent（10）平衡因子从1->2，平衡因子出现异常。
parent 所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：1、把 parent 子树旋转平衡。2、降低 parent 子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。

3.2.3更新平衡因子代码

我们直接接着上面的代码继续写了（文章结尾有完整代码）

while(parent){if(parent->_left == cur) parent->_bf--;elseif(parent->_right == cur) parent->_bf++;if(parent->_bf ==0)break;elseif(parent->_bf ==1|| parent->_bf ==-1){ cur = parent; parent = parent->_parent;}elseif(parent->_bf ==-2|| parent->_bf ==2){//旋转break;}elseassert(false);}

首先第一步： 更新平衡因子：如果插入的结点在父亲结点的左边，就–，在右边就++。
然后第二步：根据更新后的平衡因子做出判断（符合我们上面说的思路）
补充一点：“防御性编程技巧”：在最后加上else assert。为什么？因为这种情况在预料种不可能发生，如果发生了一定是前面哪一部分的代码出现了问题，这个时候根据assert报错位置向上debug即可。（省的在海量的代码中摸索半天）

万事大吉，来到本文最麻烦的部分——旋转逻辑

四，旋转逻辑与实现：AVL树的四种旋转操作详解

在上面我们了解到，在更新完平衡因子后由+1/-1->+2/-2时，AVL树不再平衡，这个时候就需要对不平衡结点进行旋转。

4.1旋转的原则

旋转有两大重要原则，只有满足这两大原则，旋转才是有意义的：

保持搜索树的规则让旋转的树从不平衡变平衡，其次降低旋转树的高度

旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。，接下来我们一一讲解。（说明：下面的图中，有些结点我们给的是具体值，如10和5等结点，这里是为了方便讲解，实际中是什么值都可以，只要大小关系符合搜索树的性质即可。）

4.2右单旋原理：从抽象到具体详解

4.2.1发生右单旋的抽象场景

如下图，展示的是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为根的树左边太高了，需要往右边旋转。

4.2.2如何进行右单旋

旋转核心步骤：

因为5 < b子树根的值 < 10，将b变成10的左子树。5要转上去，所以10变成5的右子树。5变成这棵树新的根。

完成这三步之后，①符合搜索树的规则，②控制了平衡，③以10为根的这棵的高度恢复到了插入之前的h+2（左右高度差抹平，如图），符合旋转原则。如果插入之前10是整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。

4.2.3发生右单旋的具体场景

看完上面的抽象旋转场景，肯定还有很多人云里雾里，接下来我们拆开每一颗抽象的子树内部的具体情况来分析。

4.2.3.1场景一：a/b/c三颗子树的高度都为0

这是最简单的一种情况，a、b、c 都只是空节点。当在 a 子树中插入新节点后，a所在是子树的高度从 0 变为 1，不断向上调整平衡因子，导致 10 的平衡因子从 -1 变成 -2，树失去平衡。
此时对 10 进行一次右旋，5 上升为新的根节点，b 挂到 10 的左子树位置，树重新恢复平衡。

4.2.3.2场景二：a/b/c三颗子树的高度都为1

当三棵子树高度为 1 时，内部结构会稍微复杂一些，但整体逻辑完全一致。如果在 a 子树中继续插入节点，a 的高度增加，最终使 10 的平衡因子变为 -2。
此时同样通过一次右旋，将 5 提升为根节点，恢复 AVL 树的平衡。

4.2.3.3场景三：a/b/c三颗子树的高度都为2

从现在开始，场景急剧复杂化。思考一个问题：当a/b/c子树高度为2时，子树的形状有多少种可能？给出答案如下图：一共有三种，我们标记为x,y，z。

b和c子树可以是xyz 三种情况中的任意一种，但是a就不一样了，先说结论：a子树的情况只有可能是x。怎么证明？ 先看我们要做的事是在a子树插入一个结点。

细分情况一： 如果a子树是y情况，那么在左子树插入后，a子树就不平衡了，如下图，当平衡因子更新到a子树的根节点就引发了不平衡，于是直接以a子树的根为旋转结点进行右旋转，旋转后不再继续向上更新。即：在到达10之前提前结束。

细分情况二： 如果a子树是z情况，那么在左子树插入后，a子树高度不变，如下图，当平衡因子更新到a子树的根节点，a子树根节点平衡因子从1->0，于是以a为根的子树高度不变，不再继续向上更新。即：同样在到达10之前提前结束。

所以，a子树必须是x情况。在a子树插入结点的情况有4种，b和c子树各有3种情况，总计4x3x3=36种。

4.2.3.4场景四~无穷：a/b/c三颗子树的高度都为3乃至更高

当子树高度继续增大时,场景开始逐渐超出枚举范畴。还是思考一个问题：当a/b/c子树高度为3时，子树的形状有多少种可能？

如图，x：为高度为3的满二叉树的AVL树。y-C：代表一个组合，下面四个叶子节点保留任意1个/任意两个/任意3个，都满足高度3的AVL树。合计：C(4,1)+C(4,2)+C(4,3) = 4+6+4 = 14种形状。

b和c可以是x/y-C中任意一种，组合：15*15，a的情况跟场景三类似，要满a必须插入新结点后，a自身不旋转，a高度+1不段向上更新，引发10结点旋转。

a如果是x，插入位置可以是4个叶子的任意孩子位置，有8个。a如果是y-C中4个叶子节点保留3个有4种形状，插入位置在有两个结点那边任意孩子位置，有4个。

组合一下：这里合计1515(8+4) = 5400种场景,由此可见，当子树的高度达到3的时候，情况种数就达到了如此高的水平（这就是前文为什么采用抽象图来解释原理的原因）。

科普一下

子树高度达到 4 时情况种数：31255875
子树高度达到 5 时的情况种数：1283479530046875
子树高度达到 6 时，理论结构组合已经达到 10³⁰ 级别，远远超过任何可以枚举的规模，因此 AVL 分析必须使用抽象子树模型。

4.2.3.5总结结论

可以看到，无论 a / b / c 子树的高度是多少，只要满足抽象模型中的结构关系，发生失衡时都可以通过一次右旋恢复平衡。因此，前面的抽象模型实际上已经涵盖了所有可能的具体情况。

4.3右单旋代码：复杂细节精密处理

直接看代码，我们在注释中详细介绍每一步的意义。，为了方便大家理解，我把抽象图再搬过来一份：

voidRotateR(Node* parent){//第一步：标记，结合上图，命名和图中一致 Node* pParent = parent->_parent; Node* SubL = parent->_left; Node* SubLR = SubL->_right;//进行旋转 SubL->_right = parent;//10结点转下来挂在5结点的右边 parent->_left = SubLR;//5结点的左子树给10结点当左孩子//旋转后的细节调整 SubL->_parent = pParent;//5结点变成新的根if(SubLR) SubLR->_parent = parent;//父亲指针指向调整 parent->_parent = SubL;//父亲指针指向调整//如果10结点原来是整棵树的根if(parent == _root){ _root = SubL;//根得到重定义 SubL->_parent =nullptr;}//如果10结点原来不是整颗数的根elseif(pParent){//原来10结点的父亲调整孩子指针if(pParent->_left == parent) pParent->_left = SubL;else pParent->_right = SubL;}//平衡因子调整 parent->_bf =0; SubL->_bf =0;}

4.4左单旋代码：逻辑完全一致的复现

左单旋的原理和右单旋完全一致，只是方向完全相反。原理不再解释，以下我们直接给出代码：

voidRotateL(Node* parent){//第一步：标记，结合上图，命名和图中一致 Node* pParent = parent->_parent; Node* SubR = parent->_right; Node* SubRL = SubR->_left;//进行旋转 SubR->_left = parent;//10结点转下来挂在15结点的左边 parent->_right = SubRL;//15结点的左子树给10结点当右孩子//旋转后的细节调整 SubR->_parent = pParent;//15结点变成新的根if(SubRL) SubRL->_parent = parent;//父亲指针指向调整 parent->_parent = SubR;//父亲指针指向调整//如果10结点原来是整棵树的根if(parent == _root){ _root = SubR;//根得到重定义 SubR->_parent =nullptr;}//如果10结点原来不是整颗树的根elseif(pParent){//原来10结点的父亲调整孩子指针if(pParent->_left == parent) pParent->_left = SubR;else pParent->_right = SubR;}//平衡因子调整 parent->_bf =0; SubR->_bf =0;}

4.5左右双旋原理：当单旋不再有效

4.5.1从具体案例引入

如图，上面我们在a子树插入结点的时候，进行右单旋解决了AVL树失衡的问题。此时我们将目光转移到左子树，如果在左子树插入，如下图：
b子树高度从h变成h+1，引发旋转，右单旋无法解决问题，右单旋后，我们的树依旧不平衡。

为什么呢？右单旋解决的纯粹的左边高，但是插入在b子树中，10为跟的子树不再是单纯的左边高，对于10是左边高，但是对于5是右边高，于是需要用两次旋转才能解决。以5为旋转点进行一个左单旋，以10为旋转点进行一个右单旋，这棵树就平衡了，如下图，我们以上面的后者情况为例：

4.5.2发生左右双旋的抽象场景

下面我们还是将a/b/c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的细节进一步展开为b子树根和高度为h-1的e和f子树，因为我们要对b的父亲5为旋转点进行左单旋，左单旋需要动b树中的左子树。
b子树中新增结点的位置不同，平衡因子更新的细节也不同，通过观察b子树根的平衡因子不同，这里我们要分三个场景讨论。
————————b子树根的平衡因子是旋转后平衡因子调整的根本

4.5.2.1情况一

h >= 1时，新增结点插入在e子树，e子树高度从h-1变为h并不断更新8->5->10平衡因子，引发旋转，其中8的平衡因子为-1，旋转后8和5平衡因子为0，10平衡因子为1。

4.5.2.2情况二

h >= 1时，新增结点插入在f子树，f子树高度从h-1变为h并不断更新8->5->10平衡因子，引发旋转，其中8的平衡因子为1，旋转后8和10平衡因子为0，5平衡因子为-1。

4.5.2.3情况三

h == 0时，a/b/c都是空树，b自己就是一个新增结点，不断更新5->10平衡因子，引发旋转，其中8的平衡因子为0，旋转后8和10和5平衡因子均为0。

我们可以在其中总结出一个结论：左右双旋的本质是将SubLR变成新的根，让SubL和parent分别变成SubLR的右左子树，让SubLR的左右子树分别变成SubL和parent的右子树和左子树。

4.6左右双旋代码

voidRotateLR(Node* parent){//标记结点名称 Node* cur = parent->_left; Node* SubL = cur; Node* SubLR = cur->_right;//保存SubLR的平衡因子，后面维护平衡因子可以根据结论+bf直接得出int bf = SubLR->_bf;//旋转RotateL(SubL);RotateR(parent);//维护平衡因子if(bf ==1){ parent->_bf =0;//防御性编程需要： SubLR->_bf =0;//如果旋转函数写错了，没有在函数/数内部调整好平衡因子时候采取的补救措施。 SubL->_bf =-1;//SubLR子树中高为h的那一颗给了parent，h-1的那一颗给了SubL}elseif(bf ==-1){ SubL->_bf =0; SubLR->_bf =0; parent->_bf =1;//SubLR子树中高为h的那一颗给了SubL，h-1的那一颗给了parent}elseif(bf ==0){ SubLR->_bf =0; SubL->_bf =0; parent->_bf =0;}elseassert(false);//防御性编程需要：不可能发生的情况}

4.7右左双旋代码

右左双旋的代码和左右双旋的代码逻辑几乎一致，只是方向完全相反，以下直接给出代码和情况图解。

voidRotateRL(Node* parent){//标记结点名称 Node* cur = parent->_right; Node* SubR = cur; Node* SubRL = cur->_left;//保存SubLR的平衡因子，后面维护平衡因子可以根据结论+bf直接得出int bf = SubRL->_bf;//旋转RotateR(SubR);RotateL(parent);//维护平衡因子if(bf ==1){ SubRL->_bf =0;//防御性编程需要： SubR->_bf =0;//如果旋转函数写错了，没有在函数/数内部调整好平衡因子时候采取的补救措施。 parent->_bf =-1;//SubLR子树中高为h的那一颗给了SubL，h-1的那一颗给了parent}elseif(bf ==-1){ SubRL->_bf =0; parent->_bf =0; SubR->_bf =1;//SubLR子树中高为h的那一颗给了parent，h-1的那一颗给了SubL}elseif(bf ==0){ SubR->_bf =0; SubRL->_bf =0; parent->_bf =0;}elseassert(false);//防御性编程需要}

以上，我们实现了所有的旋转代码，现在将这些代码接入插入接口的实现中，代码如下：

elseif(parent->_bf ==-2|| parent->_bf ==2){if(parent->_bf ==2&& cur->_bf ==1)//左单RotateL(parent);elseif(parent->_bf ==-2&& cur->_bf ==-1)//右单RotateR(parent);elseif(parent->_bf ==-2&& cur->_bf ==1)//左右RotateLR(parent);elseif(parent->_bf ==2&& cur->_bf ==-1)//右左RotateRL(parent);elseassert(false);break;}

五，AVL树的判定

如何去检查我这棵树是不是AVL树，很多人第一时间会想到：直接检查平衡因子？看似可行，但是在工业中是严格不允许的。

有没有可能我这个平衡因子可能是对的，但是因为一种出乎意料的错误导致AVL树是错的.有没有一种可能我的树是对的，但是在更新平衡因子的时候因为一些意想不到的错误出了问题。

所以我们必须对AVL树的每一个结点挨个儿去检查左右子树高度差才行。

// 对外接口：用于判断整棵树是否为AVL树// 从根节点开始递归检查boolIsBalanceTree(){returnJudgeAVLTree(_root);}// 递归检查AVL树是否合法boolJudgeAVLTree(Node* root){// 递归终止条件：// 如果当前节点为空，说明已经走到叶子节点之后// 空树天然满足AVL树性质if(root ==nullptr)returntrue;// 重新计算当前节点左右子树的真实高度// 注意：这里不相信节点中维护的bf，而是通过height函数重新计算int leftheight =height(root->_left);int rightheight =height(root->_right);// 根据高度计算当前节点的真实平衡因子// 平衡因子 = 右子树高度 - 左子树高度int Bf = rightheight - leftheight;// 第一层检查：AVL树的基本性质// 任意节点左右子树高度差不能超过1if(abs(Bf)>=2){// 如果高度差>=2，说明树结构已经失衡 cout << root->_key <<" height error"<< endl;returnfalse;}// 第二层检查：节点中存储的平衡因子是否正确// 在AVL树实现中，节点通常会维护一个_bf成员// 如果旋转或更新过程中出现错误，就可能导致_bf与真实值不一致if(root->_bf != Bf){// 说明平衡因子维护出现问题 cout << root->_key <<"balance factor error"<< endl;returnfalse;}// 递归检查左右子树// 只有当前节点、左子树、右子树全部满足AVL条件，整棵树才是AVL树returnJudgeAVLTree(root->_left)&&JudgeAVLTree(root->_right);}

六，剩余简单杂项接口与完整代码参考

注意：AVL树的删除代码这里没有写，原因有二：①面试很少涉及到这种难度，②难度太大了。 有兴趣的大佬可以去看《殷人昆数据结构：用面向对象方法与C++语言描述》，其中有详细讲解。

#pragmaonce#include<iostream>#include<cassert>#include<vector>#include<ctime>usingnamespace std;template<classK,classV>structAVLTreeNode{ AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent;int _bf;//Balance Factor K _key; V _value;AVLTreeNode(const K& key,const V& value):_key(key),_value(value),_bf(0),_left(nullptr),_right(nullptr),_parent(nullptr){}};template<classK,classV>classAVLTree{using Node = AVLTreeNode<K, V>;public:voidRotateL(Node* parent){ Node* pParent = parent->_parent; Node* cur = parent->_right; Node* nodeC = cur->_left; cur->_left = parent; parent->_parent = cur; parent->_right = nodeC;if(nodeC) nodeC->_parent = parent; cur->_parent = pParent;if(parent == _root){ _root = cur; cur->_parent =nullptr;}if(pParent){if(pParent->_key < cur->_key) pParent->_right = cur;elseif(pParent->_key > cur->_key) pParent->_left = cur;} cur->_bf =0; parent->_bf =0;}voidRotateR(Node* parent){ Node* pParent = parent->_parent; Node* cur = parent->_left; Node* nodeC = cur->_right; cur->_right = parent; parent->_left = nodeC; parent->_parent = cur; cur->_parent = pParent;if(nodeC) nodeC->_parent = parent;if(parent == _root){ _root = cur; cur->_parent =nullptr;}if(pParent){if(pParent->_key > cur->_key) pParent->_left = cur;elseif(pParent->_key < cur->_key) pParent->_right = cur;} cur->_bf =0; parent->_bf =0;}voidRotateLR(Node* parent){ Node* cur = parent->_left; Node* SubL = cur; Node* SubLR = cur->_right;int bf = SubLR->_bf;RotateL(SubL);RotateR(parent);if(bf ==1){ parent->_bf =0; SubLR->_bf =0; SubL->_bf =-1;}elseif(bf ==-1){ parent->_bf =1; SubL->_bf =0; SubLR->_bf =0;}elseif(bf ==0){ SubLR->_bf =0; SubL->_bf =0; parent->_bf =0;}elseassert(false);}voidRotateRL(Node* parent){ Node* cur = parent->_right; Node* SubR = cur; Node* SubRL = cur->_left;int bf = SubRL->_bf;RotateR(SubR);RotateL(parent);if(bf ==1){ SubRL->_bf =0; SubR->_bf =0; parent->_bf =-1;}elseif(bf ==-1){ SubRL->_bf =0; SubR->_bf =1; parent->_bf =0;}elseif(bf ==0){ SubR->_bf =0; SubRL->_bf =0; parent->_bf =0;}elseassert(false);}boolInsert(const K& key,const V& value){if(_root ==nullptr){ _root =newNode(key, value);returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_key > key){ parent = cur; cur = cur->_left;}elseif(cur->_key < key){ parent = cur; cur = cur->_right;}elseif(cur->_key == key)returnfalse;} cur=newNode(key, value);if(parent->_key > cur->_key) parent->_left = cur;elseif(parent->_key < cur->_key) parent->_right = cur; cur->_parent = parent;while(parent){if(parent->_left == cur) parent->_bf--;elseif(parent->_right == cur) parent->_bf++;elseassert(false);if(parent->_bf ==0)break;elseif(parent->_bf ==1|| parent->_bf ==-1){ cur = parent; parent = parent->_parent;}elseif(parent->_bf ==-2|| parent->_bf ==2){if(parent->_bf ==2&& cur->_bf ==1)//左单RotateL(parent);elseif(parent->_bf ==-2&& cur->_bf ==-1)//右单RotateR(parent);elseif(parent->_bf ==-2&& cur->_bf ==1)//左右RotateLR(parent);elseif(parent->_bf ==2&& cur->_bf ==-1)//右左RotateRL(parent);elseassert(false);break;}elseassert(false);}returntrue;} Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_key > key) cur = cur->_left;elseif(cur->_key < key) cur = cur->_right;elsereturn cur;}returnnullptr;}intSize(){returnsize(_root);}intHeight(){returnheight(_root);}voidInorder(){inorder(_root); cout << endl;}boolIsBalanceTree(){returnJudgeAVLTree(_root);}private:boolJudgeAVLTree(Node* root){if(root ==nullptr)returntrue;int leftheight =height(root->_left);int rightheight =height(root->_right);int Bf = rightheight - leftheight;if(abs(Bf)>=2){ cout << root->_key <<" height error"<< endl;returnfalse;}if(root->_bf != Bf){ cout << root->_key <<"balance factor error"<< endl;returnfalse;}returnJudgeAVLTree(root->_left)&&JudgeAVLTree(root->_right);}intsize(Node* root){if(root ==nullptr)return0;int leftsize =size(root->_left);int rightsize =size(root->_right);return leftsize + rightsize +1;}intheight(Node* root){if(root ==nullptr)return0;int leftheight=height(root->_left);int rightheight=height(root->_right);return leftheight > rightheight ? leftheight +1: rightheight +1;}voidinorder(Node* root){if(root ==nullptr)return;inorder(root->_left); cout << root->_key <<":"<< root->_value << endl;inorder(root->_right);}private: Node* _root=nullptr;};

好了，本期内容到此结束，我是此方，我们下期再见。バイバイ！