参考原视频：https://www.icourse163.org/learn/ZJU-93001?tid=1003013004#/learn/content?type=detail&id=1004242207
AVL树，又名平衡二叉树，是一种计算机科学中最先发明的自平衡二叉树。
emmm，要知道什么是平衡二叉树，先说说二叉搜索树吧，
那二叉搜索树是什么呢？
我们先定义一个树节点：
struct node{
int data;
node *left;
node *right;
};
先看图1说明，当把5作为中心节点时，2是5的左分叉，那么2小于5；同时8是5的右分叉，而8大于5，所有的中心节点和左右分叉的关系都是这样的。
这就是所谓的二叉搜索树。
而AVL树就是二叉树的升级，可以看到右图是一棵普通的二叉树，树的左右分叉不是很平衡，左边密集右边稀疏，这样会导致搜索的效率降低，所有就诞生了AVL树！
AVL树为什么叫AVL呢，因为它的发明者的名字叫Adelson Velsky和E. M. Landis。
那么让我们着重来探讨以下AVL树是如何实现自平衡的吧。
原理很简单：
每次插入一个新的节点时，如果存在某个节点的平衡被破坏（左子树与右子树的树高之差大于1），那么就检测被破坏时，插入点（麻烦制造者）的位置与该节点（被破坏者）的位置关系，进行相应的自选方式。
因此，AVL树的节点需要新加一个树高参数。
故新的node如下：
struct node{
int data;
node *left;
node *right;
int height;
node(){};
node(int x):data(x),left(NULL),right(NULL),height(1){}
};
typedef node* AVLtree 真正定义了AVL树
如何更新树高呢？
int GetHeight(AVLtree a){
if(a==NULL)return 0;
a->height=max(GetHeight(a->left),GetHeight(a->right))+1;
return a->height;
}
如果在外面使用
GetHeight(t)
就可以把AVL树 t 的所有节点的树高都更新一遍。
所以，如何检验节点（node *）t是否平衡呢？
if（abs(GetHeight（t->left）-GetHeight(t->right）)>1)
只需这么一个简单的if条件判断即可。
现在我们来到了最难的部分，自旋方式吧。
先说说LL旋转（左单旋），
条件：麻烦制造者位于被破坏者的左子树的左分叉部分
如图2所示，那么我们所要做的就是把三者的中间节点70提起来，让70成为老大！
原来的88变成了70的右儿子了。
让我们看一看更复杂的情况
如图3所示，我们将新节点插入于BL部分，导致A被破坏了，所以我们进行了LL旋转，可以看到，当我们对A进行LL旋转时，其实是将BL----B-----A进行了向右的拉扯，或者更像是顺时针的旋转，那这个旋转的名字却叫左单旋！左是根据麻烦制造者BL相对A的位置命名的！
那么如何用代码实现呢？
AVLtree L_rotation(AVLtree t){
AVLtree root=t->left;
t->left=root->right;
root->right=t;
return root;
}
RR旋转（右单旋）与左单旋十分类似，只不过麻烦制造者位于被破坏者右子树的右分叉部分罢了。代码就不给大家了，给两张图感受感受
下面来说说更复杂的旋转
RL旋转，
条件：麻烦制作者位于被破坏者的右子树的左分叉部分
如图6，插入了90之后，70的平衡被破坏了，所以让我们聚焦70，96，88这三点（被破坏者，被破坏者的右子树的根节点，右子树的左子树的根节点），需要把三个节点的中间值，也就是88提起来做老大，如何70做88的左儿子，96做右儿子。而88原来的左子树，成了70的右子树，88原来的右子树，成了96的左子树。
如果用代码实现，则更简单了（前提是已经实现了LL旋转和RR旋转）
如果是RL旋转某一棵树t，只需先对t的右子树进行一次LL旋转，再对t进行一次RR旋转，大家自己画个草图看看是不是这么一回事！
所以两行代码就好了
AVLtree RL_rotation(AVLtree t){
t->right=L_rotation(t->right);
return R_rotation(t);
}
好了，讲完了RL旋转，LR旋转也就都会了吧（大概吧。。。
所以，我们可以看到，AVL树在插入的过程会不断地旋转，导致其根节点不停改变？？？好像还没讲插入，下面给出插入的代码，根据插入的代码，自行写出删除的代码，完结！！
AVLtree insert(AVLtree t,int x){
if(t==NULL){ t=new node(x); return t; }
if(x<t->data){//左树
t->left=insert(t->left,x);
GetHeight(t);
if(GetHeight(t->left)-GetHeight(t->right)>1){//not balance
if(x<t->left->data){ t=L_rotation(t); }
else if(x>t->left->data){ t=LR_rotation(t); }
}
} else if(x>t->data){
t->right=insert(t->right,x);
GetHeight(t);
if(GetHeight(t->right)-GetHeight(t->left)>1){
if(x>t->right->data){ t=R_rotation(t); }
else if (x<t->right->data){ t=RL_rotation(t); }
}
}
return t;
}
