AVL树超详解上

前言

        学习过了二叉树以及二叉搜索树后（不了解二叉搜索树的朋友可以先看看这篇博客，二叉搜索树详解-CSDN博客），我们在一般情况下对于二叉搜索树的插入与查询时间复杂度都是O(lgN)，是十分快的，但是在一些特殊的情况下，二叉搜索树会退化成类似链表的存在，如下图。此时时间复杂度就恶化到了O(N)。

        为了解决二叉搜索树的恶化，伟大的科学家们发明了AVL树与红黑树，我们今天了解的就是其中一种解决方法AVL树。

AVL树定义

      两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。AVL树就是根据他们的名字来命名的。

        AVL树的定义与二叉搜索树类似。

       1.它的左右子树都是AVL树

        2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

        3. AVL树的左边所有非空结点值小于根结点， AVL树的右边所有非空结点值大于根结点

        在每次的插入或者删除后，都尽量保持二叉树的平衡，可以将AVL树看成一种平衡的二叉搜索树。为什么高度差的绝对值要不超过1，而不是等于0呢？原因也十分简单，假如有2个结点，我们不可能高度差为0，只能保持较为平衡的状态，如下图。

        只有当结点个数刚好为2^n+1时才可以完全平衡，如下图。所以为了通用性，不只在结点个数特殊的情况下使用，规定左右子树高度差最大可以为一。

 AVL树判断

        下面我们来看几个事例判断是否是AVL树。

        

        上图是AVL树么？我们首先判断他是不是二叉搜索树，其中序遍历为10 12 15 17，故为二叉搜索树，然后判断有没有平衡。此时就要依据平衡因子。

        为了后序论述的方便我们规定平衡因子为右子树的高度减去左子树的高度（左子树的高度减去右子树的高度也可以，只需要在旋转操作时改下判断）。我们便可以在上面的图上分别标出他们的平衡因子.如下图。

        通过上图我们可以发现以15为根结点的AVL树是平衡的，但以10为根结点的AVL树是不平衡的.其平衡因子的绝对值大于1.所以上面的二叉树不是AVL树。我们根据图像也可以明显的观察出右子树高度比左子树大很多，给人一种不平衡的感觉。

        下面我们再看一个事例

        上述的二叉树是AVL树么？首先依旧是看他的中序遍历结果4 9 10 12 15 17，有序所以为二叉搜索树，接下来看他是否平衡。

        通过标出他们的平衡因子我们发现他们的绝对值都不大于1，所以平衡为AVL树。

   二叉树中序遍历技巧

           第一步是描点，在所有结点下面描个点，如下图

        第二步是描边，用一条线，将二叉搜索树从根结点开始描一圈，如下图

         然后将线上的按照出现的顺序依次写出来1 3 4 6 7 8 10 13 14，这样就可以得到一个二叉树的中序遍历结果了，前序遍历就是在结点左边描点，后序遍历就是在结点右边描点，大家感兴趣可以尝试，在这里就不多赘述了。

AVL树实现

AVL树结点

        通过前面的定义，我们可以知道AVL树就是一种特殊的二叉树，我们就可以充分的利用之前的果实帮助我们完成AVL树。

template<class T>
struct BSTNode
{BSTNode(T k= T()):_left(nullptr), _right(nullptr), _key(k){}BSTNode* _left;BSTNode* _right;T _key;
};

        二叉搜索树的一个结点定义如上，我们定义了左右指针加上当前节点的值，但AVL树判断平衡要频繁使用平衡因子，我们就可以设置一个平衡因子变量，其次在后面旋转操作的时候，我们要经常访问当前结点的父亲结点，就可以再增加一个指针指向父亲结点。

        这样每一个结点就如下图，便于我们操作。

        于是我们便可以定义出如下结点，和AVL类。这里为了方便将AVLTNode<T>类型取了别名node。

template<class T>
struct AVLTNode
{AVLTNode(T k = T()):_left(nullptr), _right(nullptr), _key(k), _parent(nullptr),_bf(0){}AVLTNode* _left;//左子结点AVLTNode* _right;//右子结点AVLTNode* _parent;//父亲结点T _key;//有效值int _bf;//平衡因子  balance factor
};
template<class T>
class AVLTree
{
private:typedef AVLTNode<T> node;public:private:node* _root;
};

AVL树构造函数

        这里我们就写几个基础的构造函数，核心是后面的插入，删除操作。

AVLTree()
{_root = nullptr;
}
AVLTree(int k)
{_root = new node(k);
}

AVL树析构函数

        有了构造函数自然少不了析构函数了。AVL树的内存是用new在堆上开辟出来的，我们必须要些析构函数来主动的释放内存，否则会造成内存泄漏。

        由于AVL树也是二叉树，我们可以采用递归式的销毁，先释放左子树再释放右子树，最后释放当前结点。

        但是析构函数本身不支持传递参数，无法用于递归销毁，我们就可以重新定义个子函数帮助我们销毁。其中子函数最好放在private修饰符下，这样就只可以再类内访问该函数，类外面就使用不了。

	~AVLTree(){AVLTreeDestory(_root);_root = nullptr;}private:void AVLTreeDestory(node* _root){if (_root == nullptr)return;AVLTreeDestory(_root->_left);AVLTreeDestory(_root->_right);delete _root;}

AVL树插入

        一种数据结构，就是一种数据存储与管理的方式。我们实现这种数据结构必定离不开四大经典功能，增删查改，不过在AVL树种改边改变key基本不会用，就去掉这种功能。AVL树主要用于数据的查找，时间复杂度为O（lgN），效率十分快。

        接下来我们就来实现数据的插入。

        我们定义插入函数主体如下，返回bool值，如果插入成功就返回true，这次实现的AVL树是不支持相同数字插入的，所以如果插入元素在AVL树中就返回false。

bool insert(T k)
{}

        在插入前，我们首先要找到插入的位置在哪里。假如我们在下图中插入13

        我们可以将13与根结点的值比较大小，比他大就在根结点的右子树找，比他小就在根结点的左子树找，依次往下遍历找，我们可以发现13最后要插入到12的右子树上。如下图。

bool insert(T k)
{//二叉搜索树没有结点if (_root == nullptr){_root = new node(k);return true;}//找到合适的位置node* parent = nullptr;node* cur = _root;while (cur){//提前存下父节点parent = cur;//k大于结点值就去右边，小于就去左边if (cur->_key < k)cur = cur->_right;else if (cur->_key > k)cur = cur->_left;//一般的二叉搜索树不允许出现相同的数字elsereturn false;}//先判断再插入if (parent->_key > k){parent->_left = new node(k);	cur = parent->_left;cur->_parent = parent;}else{parent->_right = new node(k);cur = parent->_right;cur->_parent = parent;}return true;
}

   平衡因子变化

        由此我们便可以在AVL树中插入一个数，但此时还没有结束，当我们插入一个数的时候，AVL数种节点的平衡因子会发生改变，所以我们要修改平衡因子。变化如下图

        我们发现只有插入点13的父亲一族平衡因子会发生改变，其他的结点不会改变。于是在修改平衡因子的时候我们只需要不断遍历当前结点的父亲结点即可，不需要全部遍历一遍，此时我们在每一个结点中加的父亲指针就大大简化了代码。

        我们可以发现如果插入的结点在12的右边，那么12的平衡因子就加一，如果插入的结点在12的左边，那么12的平衡因子就减一。原因很简单，我们规定平衡因子等于右子树的高度减左子树的高度，在12的那边插入，那边子树的高度就加一，从而造成12的平衡因子变化。

        此时我们需要对于12的平衡因子进行判断

        1.平衡因子为0

        如果12的平衡因子为0，说明此时插入时原来较矮的一边子树，此时以12为根结点的AVL树平衡，就不需要继续往上更新父亲的平衡因子了。因为以12为根结点的AVL树高度无变化，不可能引起父亲的平衡因子变化。例如将上图在加个11结点。

        2.平衡因子为1或-1

        此时我们知道当前结点由原来的平衡，转变为了较不平衡的状态，高度发生了变化，一边高，一边低，此时就需要不断的向上更新父亲的平衡因子了.例如对于12的父亲结点15来说，12为根结点的AVL树高度发生了变化，那么15的平衡因子也需要发生变化。此时15的变化也就可以类似判断12是15的左节点还是右节点，我们规定平衡因子等于右子树的高度减左子树的高度，那么在左结点就减一，右节点就加一。

        上述两种情况实现的代码大致如下。

	//修改平衡因子//1.根节点的父亲结点为空，最坏情况走到根结点结束//2.插入完成后刚好parent,cur指向需要的位置while (parent){if (parent->_left == cur)parent->_bf--;elseparent->_bf++;//没有引起高度变化if (parent->_bf == 0)break;//引起可以接受的高度变化else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}}

        3.平衡因子为2或-2

        此时我们的结点插入在了原本就不平衡的树上，并且还插入到了原来较高的那一边子树上，使AVL树更加的不平衡，违背了AVL树的定义，此时我们就需要进行旋转来改变平衡因子。

        左单旋

        例如我们在下面左图的AVL树中加入18结点，对于17结点来说他是可以接受的不平衡就继续往上更新父亲结点的平衡因子。

        cur结点来自parent的右边，所以15的平衡因子较原来的加一，为1在可接受范围内，就继续往上更新。

        同理可以求的当前的parent的平衡因子为2，cur的平衡因子为1，即以10为根结点的AVL树不平衡。我们此时需要进行旋转操作。

        经过G.M.Adelson-Velskii 和E.M.Landis两位伟大的数学家研究发现，此时只需要将AVL树左旋即可。

        将根节点10从左边向下旋转，成为cur的左子树，将cur原来的左子树改为parent的右子树，此时旋转过后，parent与cur的平衡因子都为0.由此我们便通过一次旋转让原本不平衡的AVL树再次平衡起来。

        注意左单旋的条件是parent的平衡因子为2，cur的平衡因子为1.新结点插入在c子树上

        此时我们就可以，将上述图像抽象出来，更加的理解左单旋。如下图

        旋转之后我们还要判断他是否是AVL树，我们通过图片分析可以知道，a,b,c三个子树没变化，为AVL子树，parent，cur结点的左右子树高度相同，故他们的平衡因子都为0，符合要求。

        接着我们要判断旋转后的树是不是二叉搜索树。此时我们就可以根据定义来看。首先根据未旋转图像我们可以判断出  a<30,   30< b<60,  c>60.然后再旋转后b子树跑到了30节点的右子树上面，满足30右子树大于30条件，此时以30为根结点的二叉树是二叉搜索树，再以60为根结点来看， 以30为根结点的二叉搜索树 所有元素小于60，满足60的左子树所有值小于60，所以综上所述，旋转后的二叉树是AVL树。

        由上图分析我们就可以单独创建一个左旋函数，在这个函数里面对AVL树进行旋转。上述是以根节点为例画图理解，如果parent结点不是根结点，是某段子树与之分析一样，除了以parent为根结点AVL树变化，其他部分不变。在这里就不过多赘述了。（）

        最终分析完成后代码的结果如下。

void RotateL(node* parent)
{node* subR = parent->_right;node* subRL = parent->_right->_left;node* parentparent = parent->_parent;//parent为根节点特殊处理if (parentparent == nullptr){subR->_parent = nullptr;_root = subR;}else{//parent为某段子树if (parentparent->_left == parent)parentparent->_left = subR;elseparentparent->_right = subR;subR->_parent = parent->_parent;}parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;parent->_bf = 0;subR->_bf = 0;
}

        于是我们就可以将上面，上面的代码修改如下。直接调用封装好的函数。

	//修改平衡因子//1.根节点的父亲结点为空，最坏情况走到根结点结束//2.插入完成后刚好parent,cur指向需要的位置while (parent){if (parent->_left == cur)parent->_bf--;elseparent->_bf++;//没有引起高度变化if (parent->_bf == 0)break;else if (parent->_bf == 1 || parent->_bf == -1){//引起可以接受的高度变化cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}}else{assert(false);}}

        右单旋

        右单旋与左单旋十分的类似，我们采用左单旋是因为右子树看起来偏大，高度高，同理当左子树高度高时，我们就可以考虑用右单旋。

        下面我们同样看个示例，与上个示例类似，只不过此时我们插入3

        然后不断向上循环判断平衡因子。

        当我们再向上遍历时，此时的parent的平衡因子为-2，我们此时就要对他进行旋转，只有将他旋转为正常的AVL树才可以继续向上遍历。

        我们就可以以9为parent结点开始右旋，如下图。

        将结点9从右边向下旋转，成为cur的右子树，将cur原来的左子树改为parent的左子树（没有就指向空），此时旋转过后，parent与cur的平衡因子都为0.由此我们便通过一次旋转让原本不平衡的AVL树再次平衡起来。

        同样注意右单旋的条件是parent的平衡因子为-2，cur的平衡因子为-1.新结点插入在a子树上

        旋转后4结点的平衡因子为0，9的平衡因子为0.我们可以抽象为如下图（为了方便同样假定parent结点为根结点，像本例parent为某段子树根节点的分析与整个树根结点分析基本相同）

        

        与左旋相同，我们要判断旋转之后他是否是AVL树，我们通过图片分析可以知道，a,b,c三个子树没变化，为AVL子树，parent，cur结点的左右子树高度相同，故他们的平衡因子都为0，符合要求。

        接着我们要判断旋转后的树是不是二叉搜索树。此时我们就可以根据定义来看。首先根据未旋转图像我们可以判断出  a<15,   15< b<30,  c>30.然后再旋转后b子树跑到了30节点的左子树上面，满足30左子树小于30条件，此时以30为根结点的二叉树是二叉搜索树，再以15为根结点来看， 以30为根结点的二叉搜索树 所有元素大于15，满足60的右子树所有值大于15，所以综上所述，旋转后的二叉树是AVL树。

         由上图分析我们就可以单独创建一个右旋函数，在这个函数里面对AVL树进行旋转。经过上述的分析，最终分析完成后代码的结果如下。

void RotateR(node* parent)
{node* parentparent = parent->_parent;node* subL = parent->_left;node* subLR = subL->_right;subL->_right = parent;if (parentparent == nullptr){subL->_parent = nullptr;_root = subL;}else{subL->_parent = parentparent;if (parentparent->_left == parent)parentparent->_left = subL;elseparentparent->_right = subL;}parent->_left = subLR;if (subLR)subLR->_parent = parent;parent->_parent = subL;parent->_bf = 0;subL->_bf = 0;
}

        那么我们根据平衡因子判断就可以扩充为如下代码。注意我们最后加了个else断言，这是用来测试的，一旦我们的平衡因子出现不是0 1 -1 2 -2的值说明我们之前的处理是有问题的，可以提醒我们修改。

//没有引起高度变化
if (parent->_bf == 0)break;
else if (parent->_bf == 1 || parent->_bf == -1)
{//引起可以接受的高度变化cur = parent;parent = parent->_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
{assert(false);
}

        右左旋转

        光有上面两个是不够的，我们在实际的插入中还会有其他的情况。

        例如在下图中插入12结点就会导致原本较为平衡的AVL树失去平衡，10结点的平衡因子为2，就需要调整AVL树使其保持平衡。

        此时我们对10进行左旋是解决不了问题的，如下图。旋转后二叉树任然不平衡，此时我们就需要多次旋转，进行右左双旋。

        右左双旋。就是先以15为根结点进行右旋如下图，此时AVL树就变为第一种左单旋的情况，再以10为根结点进行左旋即可。

          同样注意右左双旋的条件是parent的平衡因子为2，cur的平衡因子为-1.新结点插入在b或c子树上

        与上述一样我们可以画出抽象图理解。不过此时相较于之前有些特殊，如下图我们只能推断出a，d子树的高度为h，我们只知道以40为根结点的二叉树高度为h+1，但对于具体b，c的子树高度是不知道的，我们此时就需要分类讨论了。

        假如b的高度为h-1，c的高度为h，则他们的变化如下图（不熟悉旋转操作的可以先看下左右单旋，双旋只不过进行两次单旋罢了。）

        此时我们根据左右子树的高度再更新他们的平衡因子，如下图

         假如b的高度为h，c的高度为h-1，经过上述相同的变化如下图.

        注意此时的平衡因子发生了变化，待会写代码时要额外注意。

         假如b的高度为h，c的高度为h，经过上述相同的变化如下图.此时就为刚开始举得示例情况，b，c为空子树

        此时的平衡因子都为0.由此我们便认识完了右左双旋的所有情况，就可以同样封装的函数写了，我们注意到右左双旋实际上就是之前的左单旋和右单旋的组合，就可以复用之前的代码，不过最后要注意平衡因子会发生变化。

        最后代码如下

	void RotateRL(node* parent){node* subR = parent->_right;node* subRL = subR->_left;int bf = subRL->_bf;//先右旋RotateR(subR);//再左旋RotateL(parent);//更新平衡因子,b，c 子树的高度不同，就可以通过，subRL的平衡因子反应if (bf == 0){parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = subRL->_bf = 0;}else if (bf == -1){parent->_bf = subRL->_bf = 0;subR->_bf = 1;}else{assert(false);}}

左右旋转

        有右左双旋，自然也有左右双旋， 例如在下图中插入9结点就会导致原本较为平衡的AVL树失去平衡，10结点的平衡因子为-2，就需要调整AVL树使其保持平衡。

        同样我们对他进行右旋是解决不了问题的。

        我们要对他进行两次旋转，第一次以8为根结点左旋，第二次以10为根结点右旋

        

        同样注意左右双旋的条件是parent的平衡因子为-2，cur的平衡因子为1.新结点插入在b或c子树上

        与上述一样我们可以画出抽象图理解。不过此时相较于之前有些特殊，如下图我们只能推断出a，d子树的高度为h，我们只知道以40为根结点的二叉树高度为h+1，但对于具体b，c的子树高度是不知道的，我们此时就需要分类讨论了。与右左双旋的情况十分相似。

         假如b的高度为h，c的高度为h-1，经过上述的变化如下图.

        此时要注意的是平衡因子发生变化。根据左右子树的高度即可求出

          假如b的高度为h，c的高度为h，经过上述相同的变化如下图.同时再求出平衡因子，此时就为刚开始举得示例情况，b，c为空子树

         假如b的高度为h-1，c的高度为h，经过上述相同的变化如下图..同时再求出平衡因子

        有了上面的分析，我们就可以写出左右旋转的函数了。

void RotateLR(node* parent){node* subL = parent->_left;node* subLR = subL->_right;int bf = subLR->_bf;//先左旋RotateL(subL);//再右旋RotateR(parent);//更新平衡因子,b，c 子树的高度不同，就可以通过，subRL的平衡因子反应if (bf == 0){parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = subLR->_bf = 0;}else{assert(false);}}

       插入函数的全部代码如下。

bool insert(T k)
{//二叉搜索树没有结点if (_root == nullptr){_root = new node(k);return true;}//找到合适的位置node* parent = nullptr;node* cur = _root;while (cur){//提前存下父节点parent = cur;//k大于结点值就去右边，小于就去左边if (cur->_key < k)cur = cur->_right;else if (cur->_key > k)cur = cur->_left;//一般的二叉搜索树不允许出现相同的数字elsereturn false;}//先判断再插入if (parent->_key > k){parent->_left = new node(k);	cur = parent->_left;cur->_parent = parent;}else{parent->_right = new node(k);cur = parent->_right;cur->_parent = parent;}//修改平衡因子//1.根节点的父亲结点为空，最坏情况走到根结点结束//2.插入完成后刚好parent,cur指向需要的位置while (parent){if (parent->_left == cur)parent->_bf--;elseparent->_bf++;//没有引起高度变化if (parent->_bf == 0)break;else if (parent->_bf == 1 || parent->_bf == -1){//引起可以接受的高度变化cur = parent;parent = parent->_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){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}}

        注意在我们旋转后就将循环结束了，不需要再向上更新平衡因子了。这是因为旋转后子树的高度与我们插入前的高度一样，所以不会引起父亲结点平衡因子的变化。

        到此我们的插入函数就讲完了!!真的十分不容易，感谢你能看到这。也请点点赞和关注。

AVL树测试

        到这里我们就完成了AVL树的插入，构造和析构函数，当然还有删除，删除我打算放在下一篇文章再开始写，我们写完了插入必定少不了测试，尤其是这么复杂的AVL树插入，写错某个小点就会导致代码错误，我们就可以针对刚才写的代码进行测试，检验我们代码是否正确，错了就修改。

        首先我们写的主要代码是插入，我们就可以检测插入后的二叉树是不是AVL树，如果不是就改BUG。虽然改BUG十分的烦人，但我们还是要静下心，慢慢改。

判断中序是否有序

        我们可以先判断中序遍历结果，判断是不是二叉搜索树，再判断高度差。

        与前面的问题一样，我们无法在类外部访问根结点，就需要再设置个子函数。采用先遍历左子树，根，然后遍历右子树就可以得到中序遍历结果了。

	void Inorder(){_Inorder(_root);}private:void _Inorder(node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);}

        于是我们就可以写出第一个测试用例，结果如下是正确的

void test1()
{//vector<int> a= { 16, 3, 7, 11, 9, 26, 18, 14, 15 };vector<int> a = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int> t;for (int i = 0; i < a.size(); i++){t.insert(a[i]);}t.Inorder();}

        我们可以在测试一组，结果也是没有问题的

        上述测试用例基本可以说明我们的中序是没有问题的了，接下来就是判断左右子树高度了。

平衡因子判断

        判断平衡因子我们要经常求子树的高度，我们就可以先写求树高度的函数。如下

int height(node* root)
{if (root == nullptr)return 0;int left = height(root->_left);int right = height(root->_right);return left > right ? left + 1 : right + 1;
}

        接着我们就可以递归的判断AVL树是否平衡，先求出当前结点平衡因子，判断是否合规，然后判断左子树和右子树。

void IsBalance(){if(_IsBalance(_root))cout << "是AVL树" << endl;elsecout << "不是AVL树" << endl;}private:bool _IsBalance(node* root){if (root == nullptr)return true;int left = height(root->_left);int right = height(root->_right);int bf = right - left;if (bf != root->_bf || bf > 1 || bf < -1)return false;return _IsBalance(root->_left) && _IsBalance(root->_right);}

        于是我们就可以写出以下测试代码

void test2()
{vector<int> a= { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//vector<int> a = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int> t;for (int i = 0; i < a.size(); i++){if (a[i] == 7){int c = 0;}t.insert(a[i]);cout << a[i] << "当前状态：";t.IsBalance();}//t.IsBalance();
}

        运行结果如下,说明我们的代码基本正确。

        到处就可以确定我们的程序基本没有问题了，是正确的。如有错误欢迎大家指正（最终的代码大家以附录为准，前面复制过程中可能会出现错误。）

        今天的代码到这里就结束了，欢迎大家指出错误。

        

附录代码

        头文件代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;template<class T>
struct AVLTNode
{AVLTNode(T k = T()):_left(nullptr), _right(nullptr), _key(k), _parent(nullptr),_bf(0){}AVLTNode* _left;//左子结点AVLTNode* _right;//右子结点AVLTNode* _parent;//父亲结点T _key;//有效值int _bf;//平衡因子  balance factor
};template<class T>
class AVLTree
{typedef AVLTNode<T> node;
public:AVLTree(){_root = nullptr;}AVLTree(int k){_root = new node(k);}~AVLTree(){AVLTreeDestory(_root);_root = nullptr;}bool insert(T k){//二叉搜索树没有结点if (_root == nullptr){_root = new node(k);return true;}//找到合适的位置node* parent = nullptr;node* cur = _root;while (cur){//提前存下父节点parent = cur;//k大于结点值就去右边，小于就去左边if (cur->_key < k)cur = cur->_right;else if (cur->_key > k)cur = cur->_left;//一般的二叉搜索树不允许出现相同的数字elsereturn false;}//先判断再插入if (parent->_key > k){parent->_left = new node(k);	cur = parent->_left;cur->_parent = parent;}else{parent->_right = new node(k);cur = parent->_right;cur->_parent = parent;}//修改平衡因子//1.根节点的父亲结点为空，最坏情况走到根结点结束//2.插入完成后刚好parent,cur指向需要的位置while (parent){if (parent->_left == cur)parent->_bf--;elseparent->_bf++;//没有引起高度变化if (parent->_bf == 0)break;else if (parent->_bf == 1 || parent->_bf == -1){//引起可以接受的高度变化cur = parent;parent = parent->_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){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}}return true;}void Inorder(){_Inorder(_root);}void IsBalance(){if(_IsBalance(_root))cout << "是AVL树" << endl;elsecout << "不是AVL树" << endl;}private:int height(node* root){if (root == nullptr)return 0;int left = height(root->_left);int right = height(root->_right);return left > right ? left + 1 : right + 1;}bool _IsBalance(node* root){if (root == nullptr)return true;int left = height(root->_left);int right = height(root->_right);int bf = right - left;if (bf != root->_bf || bf > 1 || bf < -1)return false;return _IsBalance(root->_left) && _IsBalance(root->_right);}void _Inorder(node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);}void AVLTreeDestory(node* _root){if (_root == nullptr)return;AVLTreeDestory(_root->_left);AVLTreeDestory(_root->_right);delete _root;}void RotateL(node* parent){node* subR = parent->_right;node* subRL = parent->_right->_left;node* parentparent = parent->_parent;//parent为根节点特殊处理if (parentparent == nullptr){subR->_parent = nullptr;_root = subR;}else{//parent为某段子树if (parentparent->_left == parent)parentparent->_left = subR;elseparentparent->_right = subR;subR->_parent = parent->_parent;}parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;parent->_bf = 0;subR->_bf = 0;}void RotateR(node* parent){node* parentparent = parent->_parent;node* subL = parent->_left;node* subLR = subL->_right;subL->_right = parent;if (parentparent == nullptr){subL->_parent = nullptr;_root = subL;}else{subL->_parent = parentparent;if (parentparent->_left == parent)parentparent->_left = subL;elseparentparent->_right = subL;}parent->_left = subLR;if (subLR)subLR->_parent = parent;parent->_parent = subL;parent->_bf = 0;subL->_bf = 0;}void RotateRL(node* parent){node* subR = parent->_right;node* subRL = subR->_left;int bf = subRL->_bf;//先右旋RotateR(subR);//再左旋RotateL(parent);//更新平衡因子,b，c 子树的高度不同，就可以通过，subRL的平衡因子反应if (bf == 0){parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = subRL->_bf = 0;}else if (bf == -1){parent->_bf = subRL->_bf = 0;subR->_bf = 1;}else{assert(false);}}void RotateLR(node* parent){node* subL = parent->_left;node* subLR = subL->_right;int bf = subLR->_bf;//先左旋RotateL(subL);//再右旋RotateR(parent);//更新平衡因子,b，c 子树的高度不同，就可以通过，subRL的平衡因子反应if (bf == 0){parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = subLR->_bf = 0;}else{assert(false);}}node* _root;
};

        源文件代码

#include"AVLTree.h"
#include<vector>void test1()
{//vector<int> a= { 16, 3, 7, 11, 9, 26, 18, 14, 15 };vector<int> a = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int> t;for (int i = 0; i < a.size(); i++){t.insert(a[i]);}t.Inorder();}void test2()
{//vector<int> a= { 16, 3, 7, 11, 9, 26, 18, 14, 15 };vector<int> a = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int> t;for (int i = 0; i < a.size(); i++){if (a[i] == 14){int c = 0;}t.insert(a[i]);cout << a[i] << "当前状态：";t.IsBalance();}//t.IsBalance();
}int main()
{test2();return 0;
}