【C++】平衡树优化实战：如何手搓一棵查找更快的 AVL 树？
🎬 个人主页：MSTcheng · ZEEKLOG
🌱 代码仓库 ：MSTcheng · Gitee
🔥 精选专栏: 《C语言》
《数据结构》
《C++由浅入深》
💬座右铭：路虽远行则将至，事虽难做则必成！
前言：前两篇文章我们已经向大家介绍了map和set这两个容器，他们的底层都是平衡二叉搜索树，而今天我们就来介绍一种平衡二叉搜索树——AVL树。
文章目录
一、AVL树的认识
1.1AVL树的概念
AVL树是由G. M. Adelson-Velsky和E. M. Landis两个前苏联的科学家所发明的，它的具体定义如下：
AVL树是最先发明的自平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
AVL树的特点：
- 平衡因子
AVL树的特点其实就是高度的平衡，所以这里引入一个平衡因子的概念（后面会用到）。每个结点都有⼀个平衡因子，任何结点的平衡因子=右子树高度-左子树高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个凤向标一样。
思考一下为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差是0呢？0不是更好的平衡吗？
画画图分析我们发现，不是不想这样设计，而是有些情况是做不到高度差是0的。比如⼀棵树是2个结点，4个结点等情况下，高度差最好就是1，无法做到高度差是0
AVL树的效率：
AVL树整体结点数量和分布和完全⼆叉树类似，高度可以控制在 ，那么增删查改的效率也可以控制在 ，相比二叉搜索树有了本质的提升。
二、AVL树的实现
2.1AVL树的基本框架
1、定义一个结点的结构
template<classK,classV>structAVLTreeNode{// 需要parent指针，后续更新平衡因子可以看到 pair<K, V> _kv;//存的是一个pair AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent;int _bf;// 定义一个平衡因子来控制树的平衡AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};与二叉搜索树的结点结构类似，但AVL树的不同点就是：AVL树结点存的是一个pair来管理key和value，且多了一个_parent指针指向父亲结点，那么这棵树就变成了一个三叉树。每个结点都有一个_parent指向其父亲。
2、AVL树的整体框架：
template<classk,classv>classAVLTree{typedef AVLTreeNode<k,v> Node;public:private: Node* _root =nullptr;};将结点的名字AVLTreeNode重命名为Node这样既方便更改模板参数，又能使得代码更简洁。私有成员就是一个根节点_root初始时为空。
2.2AVL树的插入
插入分为两个步骤：
1. 按照二叉搜索树的规则去插入
2.更新平衡因子：具体看插入的结点可能只影响父亲结点，也可能会影响祖先结点。
下面我们就按照这个步骤来写代码：
boolInsert(const pair<k, v>& kv){if(_root ==nullptr){ _root =newNode(kv);returntrue;} Node* cur = _root; Node* parent =nullptr;while(cur){if(cur->_kv.first > kv.first){//小于往左边走 parent = cur; cur = cur->_left;}elseif(cur->_kv.first < kv.first){//大于往右边走 parent = cur; cur = cur->_right;}else{returnfalse;}} cur =newNode(kv); cur->_bf =0;//新节点的平衡因子等于0！！！if(parent->_kv.first < kv.first){ parent->_right = cur;}else{ parent->_left = cur;}//相比之前的二叉树多了一个_parent指针 所以cur的parent要指向parent cur->_parent = parent;}第一步：插入的逻辑与二叉搜索树完全一样，但要注意AVL树使用的是pair，而比较逻辑永远都是比较key所以要取kv的first。
第二步：更新平衡因子
更新原则：
- 平衡因子=右子树高度-左子树高度
- 插入结点，会增加高度，所以新增结点在
parent的右⼦树，parent的平衡因⼦++，新增结点在parent的左子树，parent平衡因子--。 parent所在⼦树的高度是否变化决定了是否会继续往上更新。
平衡因子更新的几种情况：
第一种：更新过程种某一个结点的平衡因子变成了0
第二种情况：某棵子树不平衡需要旋转处理
注意：平衡因子变成了2说明：右子树-左子树>2说明左右子树的高度差大于2了，此时就要旋转处理。旋转的本质就是使得不平衡(平衡因子大于2或<-2)的那个根变成平衡。由于这里涉及旋转，旋转的平衡因子更新比较复杂在后续介绍。
第三种情况：最坏的情况，一直影响到根(第一个结点)
注意：为什么会层层影响？
因为插入一个结点影响的是一整棵子树使得根节点8的左子树增加或者右子树增加，而更不更新平衡因子是要看该结点的平衡因子在变化之后是否是处于-1/0/1的平衡状态，如果不是就要旋转调整，如果是就要往上更新，直到要更新的那个结点变成0说明平衡才停止更新。
总结：插入一个结点无论是在哪个结点下插入，只要是插入在这个结点的左边那么这个结点的平衡因子就--，如果是插入在这个结点的右边，那么这个结点的平衡因子就++，而这个结点既然++或--了就势必会影响上面的结点，所以要通过一个循环来判断。而这个循环结束（平衡因子停止更新）的条件就是更新到了某一个结点，该结点的平衡因子由1/-1变成了0即变化后当前结点的平衡因子bf为0，或者是一直更新更新，直到更新到根结点（第一个结点），由于根结点上面没有结点了更新自然就停止了。
代码示例：
//===========================//注意下面的代码是接在上面代码的下面的//这里为了方便分析所以将他们分离//===========================//插入要更新平衡因子while(parent){//平衡因子=右子树子树高度-左子树高度//对于插入的结点，插入到parent结点的右边平衡因子就++ 反之--if(cur==parent->_left){ parent->_bf--;}else{ parent->_bf++;}//平衡因子的更新停止条件//====================//平衡因子更新情况一://更新过程种某一个结点的平衡因子变成了0//====================if(parent->_bf ==0){//不需要更新 已经平衡直接breakbreak;}//======================//平衡因子更新情况三://最坏的情况，一直影响到根(第一个结点)//直到parent为空跳出循环//======================elseif(parent->_bf ==1|| parent->_bf ==-1){//继续往上更新 cur = parent; parent = parent->_parent;}//=====================//平衡因子更新情况二://某棵子树不平衡(平衡因子大于2或小于-2)需要旋转处理 //比较复杂，后面介绍//======================//更新后结点的平衡因子大于3或小于-3 肯定是有问题的了else{//高度差都大于3了 说明之前已经不平衡了assert(false);}}returntrue;旋转处理：
首先要搞懂一点，为什么需要旋转？
首先，AVL树是一颗高度平衡的二叉搜索树，而我们对于高度平衡的感知是通过平衡因子来感知的，所以我们在插入结点的时候才要去格外的注意每一个结点的平衡因子更新情况(这也是为什么要有平衡因子的原因)。而我们在更新平衡因子的途中，因为某一个结点在更新的过程种出现了平衡因子等于2或小于-2(说明这个根的左右子树的高度差大于1)的情况。所以我们需要旋转处理，将这个根的左右子树变成平衡（即让他们的高度差等于0），而前面我们也说过当某个结点在更新的途中变成了0那么平衡因子的更新就可以结束了，而旋转就是使得这个特殊结点的平衡因子变成0的方法。
需要旋转的几种情况：
第一种：当前根的左子树高度大于右子树高度->右单旋
通过上面的旋转我们发现，旋转之后该局部子树（也可能是整棵树）已经平衡，而旋转之后我们可以看到parent，subL的平衡因子都变成了0。
那到底是不是在所有满足右单旋旋的所有被情况下，右旋之后的结点subL，parent的平衡因子是不是都会变成0呢？ （subL，parent，subLR这三个指针是为了方便更改链接关系而定义的具体在代码部分会细说）
下面就再来看一些右单旋的情况：
第一种情形：subL为空 最简单的只有两个结点，在5结点处插入一个结点左右高度差大于2引发右单旋，旋转完之后subL和parent平衡因子为0.
第二种情形：subL不为空，且树的结构比情况一更加复杂，这次是由于a结点的插入导致了根节点5的平衡因子由1变成了-2所以引发了右单旋，但是旋转之后的结果还是一样parent，subL的平衡因子均为0。
第三种情况：不再是只插入一个结点，而是2个或多个结点，通过这个情况我们就发现插入的情况就明显变多了，但是我们还是以下面的抽象图来替代。
总结：
通过这几种情况，说明一点无论插入的是一个结点还是多个结点，无论插入的情况多么复杂我们都可以使用抽象图来代替。而我们从抽象图上得出的最终结论就是一个经过右单旋的树，旋转完后其parent和subL的平衡因子总是为0.
对于上面的插入情况可能还会有人由疑惑说，为什么上面的插入情况均是针对a结点去进行插入，为啥不插入到b结点？
因为目前讨论的是右单旋的情况，而右单旋的条件就是一个根的左子树高度大于右子树，如果在b插入就能造成外层左子树高，内部右子树高的情况（涉及到双旋）那就不是单单进行单选解决的了。（具体后面介绍。）
代码示例：
在insert函数中平衡因子更新情况二：
//=====================//平衡因子更新情况二://某棵子树不平衡(平衡因子大于2或小于-2)需要旋转处理 //======================elseif(parent->_bf ==2|| parent->_bf ==-2){//==========================//高度差大于1 需要旋转//旋转情况：左边高->右单旋 右边高->左单旋转// 子树右边高，根左边高->左右双旋 子树左边高，根右边高->右左双旋//==========================if(parent->_bf ==-2&& cur->_bf ==-1){//此时就是根的左边高 调用右单旋RotateR(parent);}}将右单旋封成私有：
private:voidRotateR(Node* parent)//右单旋{//旋转有四步 //第一步：标识要处理的结点 Node* subL = parent->_left; Node* subLR = subL->_right;//第二步：改变结点的链接关系 parent->_left = subLR;if(subLR)//subLR可能为空所以要判断一下 subLR->_parent = parent;//处理的结点可能是局部子树 或者是根节点所以要先保存原先parent的父亲结点//一定要注意parentParent对于parent的指向在改变链接关系这一步是没有发生改变的！！！！ Node* parentParent = parent->_parent; subL->_right = parent; parent->_parent = subL;//第三步：将新的根结点与原先根节点的父亲相连//=======================//我们算然改变了根结点：由原来的parent变成了subL//但是原本parent的_parent对于parent的指向没有发生变化 //所以下面的判断就是对这一指向的处理！！//=======================if(parent==_root)//如果parent本身就是_root说明parent原本就是根节点{ _root = subL;//将subL更新成根节点 subL->_parent =nullptr;}else{//parent是局部子树的根 还要判断该根是在其父亲的左还是右if(parent == parentParent->_left){ parentParent->_left = subL;}else{ parentParent->_right = subL;}//subL变成新的根结点以后//subL的_parent也要指向parentParent（与parentParent建立联系） subL->_parent = parentParent;}//第四步：更新平衡因子//旋转->将树变成平衡 所以平衡因子为0 parent->_bf = subL->_bf =0;}第二种情况：当前根的左子树高度小于右子树高度->左单旋
类似的左单旋我们也使用这个抽象图去分析：
与右单旋转一样同样是四个步骤：
1、标识要处理的结点
2、改变结点之间的链接关系
3、将根节点与原先根节点的父亲相连
4、更新平衡因子
在insert函数中：
elseif(parent->_bf ==2&& cur->_bf ==1){//此时就是根的右边高 调用左单旋RotateL(parent);}与右单旋一样封装成私有：
private:voidRotateL(Node* parent){//第一步：标识要处理的结点 Node* subR = parent->_right; Node* subRL = subR->_left;//第二步：改变结点间的链接关系 parent->_right = subRL;if(subRL)//subLR可能为空所以要判断一下 subRL->_parent = parent;//parent在变化之前先保存原先parent的父亲结点//一定要注意parentParent对于parent的指向在改变链接关系这一步是没有发生改变的！！！！ Node* parentParent = parent->_parent; subR->_left = parent; parent->_parent = subR;//第三步：处理新的根结点与原先根结点的父亲结点的链接if(parent==_root){ _root = subR; subR->_parent =nullptr;}else{//=======================//我们算然改变了根结点：由原来的parent->subR//但是原本parent的_parent对于parent的指向没有发生变化 //所以下面的判断就是对这一指向的处理！！//=======================if(parentParent->_left == parent){ parentParent->_left = subR;}else{ parentParent->_right = subR;}//subR的_parent也要指向parentParent subR->_parent = parentParent;}//第四步：更新平衡因子 parent->_bf = subR->_bf =0;}第三种情况：外部的左子树高，内部局部子树的右子树高->左右双旋
左右双旋的条件：
通过这两幅图可以看到，左边高时，如果插入位置不是在a子树，而是插入在b子树，b⼦树高度从h变成h+1，引发旋转，右单旋无法解决问题，右单旋后，我们的树依旧不平衡。 右单旋解决的纯粹的左边高，但是插入在子树中，10为跟的子树不再是单纯的左边高，对于10是左边高，但是对于5是右边高，需要用两次旋转才能解决，以5为旋转点进行⼀个左单旋，以10为旋转点进行⼀个右单旋，这棵树这棵树就平衡了。
上面两个图分别为左右双旋中h==0和h==1具体场景分析，下面我们将a/b/c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的细节进⼀步展开为8和左子树高度为h-1的e和f子树，因为我们要对b的父亲5为旋转点进行左单旋，左单旋需要动b树中的左⼦树。b子树中新增结点的位置不同，平衡因子更新的细节也不同，通过观察8的平衡因⼦不同，这里我们要分三个场景讨论。
- 场景1：
h >= 1时，新增结点插⼊在e⼦树，e⼦树高度从h-1并为h并不断更新8->5->10平衡因⼦，引发旋转，其中8的平衡因子为-1，旋转后8和5平衡因⼦为0，10平衡因⼦为1。 - 场景2：
h >= 1时，新增结点插入在f子树，f子树高度从h-1变为h并不断更新8->5->10平衡因子，引发旋转，其中8的平衡因子为1，旋转后8和10平衡因⼦为0，5平衡因⼦为-1。 - 场景3：
h == 0时，a/b/c都是空树，b自己就是一个新增结点，不断更新5->10平衡因子，引发旋转，其中8的平衡因⼦为0，旋转后8和10和5平衡因⼦均为0。
上面的解释看不懂没关系，上面的分析其实就是在分析平衡因子的更新，因为左单旋和右单选我们都已经实现了，双旋就是复用一下而已，重要的是旋转后平衡因子的更新！！！。 下面我们直接上图。（看不懂上面的分析可以直接看下面的图更加直观）
千万不要被这张图片吓到，我们只需要知道一点，分析在e点和在f结点插入的目的就是为了分析subLR的平衡因子，而左右双旋的本质其实就是将subLR旋到根结点，将subLR的左孩子分为subL，右孩子分为parent。 所以subLR的平衡因子会影响最后旋转完后subL，subLR，parent的平衡因子bf。
从上图我们可以总结出：
- 当
subLR的平衡因子为0时，左右双旋完后subL，subLR，parent的平衡因子均为0 - 当
subLR的平衡因子为1时，左右双旋完后subL平衡因子为-1，subLR，parent的平衡因子为0 - 当
subLR的平衡因子为-1时，左右双旋完后subL，subLR的平衡因子为0，parent的平衡因子为1
代码示例：
在insert函数中：
elseif(parent->_bf ==-2&& cur->_bf ==1){//此时就是子树右边高 根左边高 调用左右双旋RotateLR(parent);}将左右双旋封成私有：
private:voidRotateLR(Node* parent){//左右双旋直接复用前面的代码就好了 //第一步：标识需要处理的结点 Node* subL = parent->_left; Node* subLR = subL->_right;//记录subLR的平衡因子 这对于判断后面的插入情况有重大作用！！！ //最终双旋完后的平衡因子看的就是subLR的平衡因子 所以这里先记录下来int bf = subLR->_bf;//第二步：旋转RotateL(subL);//对子树进行左单旋RotateR(parent);//对根进行右单旋//第三步：更新平衡因子if(bf ==0){//说明subLR就是当前的插入结点 subL->_bf =0; subLR->_bf =0; parent->_bf =0;}elseif(bf ==1){ subL->_bf =-1; subLR->_bf =0; parent->_bf =0;}elseif(bf ==-1){ subLR->_bf =0; subL->_bf =0; parent->_bf =1;}else{assert(false);}}第四种情况：外部的右子树高，内部局部子树的左子树高->右左双旋
跟左右双旋类似，下面我们将a/b/c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的细节进⼀步展开为12和左子树=高度为h-1的e和f子树，因为我们要对b的父亲15为旋转点进行右单旋，右单旋需要动b树中的右子树。b子树中新增结点的位置不同，平衡因子更新的细节也不同，通过观察12的平衡因子不同，所以要分三个场景进行讨论。
这里直接上图，因为分析的方法思路均与左右双旋类似：
代码示例：
在insert函数中：
elseif(parent->_bf ==2&& cur->_bf ==-1){//此时就是子树左边高 根右边高 右左双旋RotateRL(parent);}还是一样，右左双旋封装成私有：
private:voidRotateRL(Node* parent){//第一步：标识要处理的结点 Node* subR = parent->_right; Node* subRL = subR->_left;//记录subRL的平衡因子方便后面平衡因子的更新int bf = subRL->_bf;//第二步：旋转//对子树右单旋RotateR(parent->_right);RotateL(parent);//对根左单旋//第三步更新平衡因子if(bf ==0){ subR->_bf =0; subRL->_bf =0; parent->_bf =0;}elseif(bf ==1){ subR->_bf =0; subRL->_bf =0; parent->_bf =-1;}elseif(bf ==-1){ subR->_bf =1; parent->_bf =0; subRL->_bf =0;}else{assert(false);}}以上就是所有插入逻辑的实现了啦，只要大家把握好插入的步骤，理解为什么要旋转？以及维护好平衡因子就不会觉得复杂了。
2.3AVL树的中序遍历
AVL树的中序遍历与二叉搜索树的逻辑一样，依然是去递归打印结点的值，只不过二叉搜索树key和value的值是分开存储的，而AVL树key和value是存在pair里的，仅此区别而已。
在公有部分提供一个接口调用：
voidInOrder(){_InOrder(_root); cout << endl;}实现部分封装成私有：
void_InOrder(Node* root){if(root ==NULL){return;}_InOrder(root->_left); cout << root->_kv.first <<":"<<root->_kv.second<<" ";_InOrder(root->_right);}2.4AVL树其他功能实现
1、查找
AVL树的查找逻辑与二叉搜索树一样，按照二叉搜索树的规则来进行查找。
Node*Find(const k & key){ Node* cur = _root;while(cur){if(cur->_kv.first < key){ cur = cur->_right;}elseif(cur->_kv.first > key){ cur = cur->_left;}else{return cur;}}returnnullptr;}注意： 返回值返回的是一个结点，有了结点那么就能取到该结点的pair就能拿到key和value的值了。
2、AVL树平衡检测
为什么还要进行平衡检测？平衡检测就是为了查看我们的AVL树在插入的过程中平衡因子的更新是否正确。
这时候就不能直接去看平衡因子了，而是要去计算树的高度差来反向的判断每个结点的平衡因子是否正确。
在公有部分提供接口便于调用：
boolIsBalanceTree(){return_IsBalanceTree(_root);}intHight(){return_Hight(_root);}实现部分封成私有：
private://平衡检测bool_IsBalanceTree(Node* root){if(root ==nullptr)//遍历到空结点递归返回{returntrue;}//检查平衡那么就要计算这棵树左右子树的高度int LeftHight =_Hight(root->_left);//计算子树的高度递归调用_Hight方法int RightHight =_Hight(root->_right);int bf = RightHight - LeftHight;if(abs(bf)>=2|| root->_bf != bf){//如果该结点的平衡因子大于或等于2 或者根节点的平衡因子不等于右子树-左子树的话就打印异常信息 cout << root->_kv.first <<"平衡因子异常"<< endl;returnfalse;}return_IsBalanceTree(root->_left)&&_IsBalanceTree(root->_right);}int_Hight(Node* root){if(root ==nullptr){return0;}int LeftHight =_Hight(root->_left);int RightHight =_Hight(root->_right);return LeftHight > RightHight ? LeftHight +1: RightHight +1;}3、AVL树的大小
intSize(){return_Size(_root);}int_Size(Node* root){return root ==nullptr?0:_Size(root->_left)+_Size(root->_right)+1;}以上就是AVL树所有的功能实现了，想要完整的代码请点击：AVL实现的完整代码
下面给出两段代码测试一下：
代码一：
voidTestAVLTree1(){ AVLTree<int,int> t;// 常规的测试用例int a[]={16,3,7,11,9,26,18,14,15};// 特殊的带有双旋场景的测试用例//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for(auto e : a){ t.Insert({ e, e }); t.InOrder(); cout <<"Insert:"<< e <<"->"<<"平衡因子:"<< t.IsBalanceTree()<< endl; cout << endl;}//t.InOrder();//cout << t.IsBalanceTree() << endl;}
代码二：
/ 插入一堆随机值，测试平衡，顺便测试一下高度和性能等 voidTestAVLTree2(){constint N =1000000; vector<int> v; v.reserve(N);srand(time(0));for(size_t i =0; i < N; i++){ v.push_back((rand()+ i));} size_t begin2 =clock(); AVLTree<int,int> t;for(auto e : v){ t.Insert(make_pair(e, e));} size_t end2 =clock(); cout <<"Insert:"<< end2 - begin2 << endl; cout << t.IsBalanceTree()<< endl; cout <<"Height:"<< t.Hight()<< endl; cout <<"Size:"<< t.Size()<< endl; size_t begin1 =clock();//// 确定在的值///*for (auto e : v)//{//t.Find(e);//}*/// 随机值for(size_t i =0; i < N; i++){ t.Find((rand()+ i));} size_t end1 =clock(); cout <<"Find:"<< end1 - begin1 << endl;}
三、总结
AVL 树通过"平衡因子"维持平衡，借助"旋转操作"修正失衡，确保增删查操作的时间复杂度稳定在 O(log N)，堪称自平衡二叉树的典范。其精妙之处在于：以高度差不超过 1 的简洁平衡规则配合精确的旋转策略，有效解决了普通二叉搜索树的退化问题。深入掌握 AVL 树的平衡传递机制和旋转细节，不仅能习得一种高效数据结构，更能建立"主动维护换取性能稳定"的设计思维，为学习更高级的数据结构奠定坚实基础。
MSTcheng 始终坚持用直观图解 + 实战代码，把复杂技术拆解得明明白白！ 👁️ 【关注】 看普通程序员如何用实用派思路搞定复杂需求 👍 【点赞】 给 “不搞虚的” 技术分享多份认可 🔖 【收藏】 把这些 “好用又好懂” 的干货技巧存进你的知识库 💬 【评论】 来唠唠 —— 你踩过最 “离谱” 的技术坑是啥？ 🔄 【转发】把实用技术干货分享给身边有需要的程序员伙伴 技术从无唯一解，让我们一起用最接地气的方式，写出最扎实的代码！ 🚀💻 能够看到这里的小伙伴已经打败95%的人了，为你点赞，休息一下吧！
