环境：C++ 11 + win10

IDE：Clion 2018.3

AVL平衡树是在BST二叉查找树的基础上添加了平衡机制。

我们把平衡的BST认为是任一节点的左子树和右子树的高度差为-1,0,1中的一种情况，即不存在相差两层及以上。

所谓平衡机制就是BST在理想情况下搜索复杂度是o(logn)

但是如果在（存在某一节点，该节点的左子树的高度与右子树的高度差>1）这种状况下，复杂度会超过o(logn)

举个极端的例子如加入1,2,3,4，BST就退化为一个线性的链表，复杂度变成了o(n)

为了避免这种情况，我们在BST中引入平衡操作（旋转操作），使得BST始终不存在左右子树超过1高度差的节点。

本次代码基于我的另一篇博客的基础之上，有需要可以翻看 upload/201812191532107041.png" alt="" width="1296" style="margin: 0px; padding: 0px; border: 0px; max-width: 660px; height: auto;" />

 接下来我们以LL、LR、RR、RL四种情况讨论。

1、LL：

通俗的讲就是把K2从K1那扯下来，然后把Y移到K2的左子树，最后把K2移到K1的右子树。

2、RR：

与LL同理，把K1先扯下来，再把Y接到K1的右侧，再把K1作为左子树接到K2。

 3、LR：

LR需要先做一次RR再做一次LL：

先把K1从K2那扯下来，让K2和K3连，然后把B作为K1的右子树，再把K1连到K2的左子树上。

然后再做LL，把K3从K2上面扯下来，让C作为K3的左子树，再把K3连到K2的右子树。

4、RL：

先LL再RR，与LR同理。

以上是主要思想的分析，除了旋转操作，我们还需要添加新的方法：

1、求树的高度：height方法

2、求某节点的左子树和右子树的高度差 ：Diff方法      

3、一个对整个树进行判断，对里面的X节点进行对应操作：Balance方法

同时AVL中的Insert（插入某一节点）的方法与BST中也略有不同，需要注意的是AVL种的__Insert（PS：带"__"的表示私有内部接口）的参数中第一个为bstNode<T> * & root （需要&引用）

具体代码如下：（此代码为完整代码，可以直接复制进自己的项目查看效果）

myBST.h

#ifndef TEST1_MYBST_H #define TEST1_MYBST_H  #include <iomanip> #include "bstNode.h" #include <vector> #include <deque> #include <iostream> #include <algorithm>using namespace std;  template <typename T>class myBST{ private:     bstNode<T> * root = nullptr;     bstNode<T> * __search(bstNode<T> * root , const T &key){         if (nullptr == root)             return nullptr;         if (key == root->data)             return root;         else if (key < root->data)             return __search(root->left, key);         else            return __search(root->right, key);     } //查找关键字是否存在    bstNode<T> * __treeMin(bstNode<T> * root , bstNode<T> * &parent){         bstNode<T> * curr = root;         while(curr->left!= nullptr){             parent = curr;             curr = curr->left;         }         return  curr;     } //返回最小节点（一路向左）    bstNode<T> * __Insert(bstN