一：AVL树定义：
AVL树（Balanced Binary Tree or Hight-Balanced Tree）
AVL树是空二叉树或者具有如下性质的BST树：
①根节点的左、右子树的高度之差的绝对值不超过1。
②且根节点的左子树和右子树仍然是AVL树
③AVL树的总共节点为N个，他的高度能搞保持在logN,插入、删除、查找等操作的时间复杂度也是logN。
节点的平衡因子BF（Balanced Factor），AVL树是一种特殊的二叉搜索树，相对于数据极端情况下，二叉搜索树会退化成单链表，AVL树定义了旋转操作，在平衡因子大于1时，AVL树会旋转来调整树的结构，来重新满足平衡因子，使得平衡因子的值趋向于0。
平衡条件：一个理想的的平衡条件是左右两个子树的高度完全相同，但是只有节点的数量为2^n-1的树才满足这个条件（n是层数，2层要三个，三层要7个）
AVL树不平衡的情况：
AVL大部分操作都和BST树相同，只有在插入删除节点时，有可能造成AVL树失去平衡，而且只有那些在被插入或删除节点到根节点的路径上的节点有可能出现失衡，因为只有那些节点的子树结构发生了变化。当插入新节点导致不平衡时，我们需要找到距离新结点最近的不平衡节点为轴来转动AVL树来达到平衡
1、AVL树的结构设计
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
typedef int KeyType;
typedef struct AVLNode
{
KeyType key;
AVLNode* leftchild;
AVLNode* rightchild;
AVLNode* parent;
int balance; // 平衡因子：-1，0，1
}AVLNode, * AVLTree;
2、创建一个节点
AVLNode* BuyNode(KeyType kx)
{
AVLNode* s = (AVLNode*)malloc(sizeof(AVLNode));
if (s == nullptr)
exit(1);
memset(s, 0, sizeof(AVLNode));
s->key = kx;
return s;
}
3、AVL树的插入：
如果在 一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。
平衡化旋转有两类:
①单旋转(左旋和右旋)
②双旋转(左平衡和右平衡
（1）每插入一个新结点时，AVL 树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子(左、右子树的高度差)。
（2）如果在某-一结点发现高度不平衡，停止回溯。
从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。
（3）如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按方向分为左单旋转或右单旋转
其中一个是另一个的镜像，其方向与不平衡的形状相关。
（4）如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。
3.1、插入点位于双亲结点的右子节点的右子树上（左单旋转）
思路：将原来根节点的右孩子作为新的根节点，新节点原来的左孩子作为原来根节点的右孩子，原来的根节点作为新根节点的左孩子。然后再处理节点之间的父子关系，最后再判断最终根节点。
AVLNode RotateLeft(AVLTree& root, AVLNode* ptr) //左单旋转
{
AVLNode* newroot = ptr->rightchild;
newroot->parent = ptr->parent;
ptr->rightchild = newroot->leftchild;
if (newroot->leftchild != nullptr)
{
newroot->leftchild->parent = ptr;//2
}
newroot->leftchild = ptr;
if (ptr->parent == nullptr)
{
root = newroot;
}
else
{
if (ptr->parent->leftchild == ptr)
{
ptr->parent->leftchild = newroot;
}
else
{
ptr->parent->rightchild = newroot;
}
}
ptr->parent = newroot;//3
}
3.2、插入点位于双亲结点的左子节点的左子树上（右单旋转）
思路：将原来根节点的左孩子作为新的根节点，新节点原来的右孩子作为原来根节点的左孩子，原来的根节点作为新根节点的右孩子。然后再处理节点之间的父子关系，最后再判断最终根节点。
void RotateRight(AVLTree& root, AVLNode* ptr)
{
AVLNode* newroot = ptr->leftchild;
newroot->parent = ptr->parent;
ptr->leftchild = newroot->rightchild;
if (newroot->rightchild != nullptr)
{
newroot->rightchild->parent = ptr;
}
newroot->rightchild = ptr;
if (ptr->parent == nullptr)
{
root = newroot;
}
else
{
if (ptr->parent->leftchild == ptr)
{
ptr->parent->leftchild = newroot;
}
else
{
ptr->parent->rightchild = newroot;
}
}
ptr->parent = newroot;
}
3.3、插入点位于双亲结点的右子节点的左子树上（右、左双旋转）
思路：先进行右单旋转，再进行左单旋转。
插入81，则78这个节点先失去平衡，必须先将89右旋转下去，再将78左旋转下来，
我们这里引入了平衡因子来实现，可分为1、0、-1三种情况。
void RightBalance(AVLTree& tree, AVLNode* ptr)
{
AVLNode* rightsub = ptr->rightchild, * leftsub = nullptr;
switch (rightsub->balance)
{
case 0: cout << "right balance \n"; break;
case 1:
ptr->balance = 0;
rightsub->balance = 0;
RotateLeft(tree, ptr);
break;
case -1:
leftsub = rightsub->leftchild;
switch (leftsub->balance)
{
case 1:
ptr->balance = -1;
rightsub->balance = 0;
break;
case 0:
ptr->balance = 0;
rightsub->balance = 0;
break;
case -1:
ptr->balance = 0;
rightsub->balance = 1;
break;
}
leftsub->balance = 0;
RotateRight(tree, rightsub);
RotateLeft(tree, ptr);
break;
}
}
3.4、插入点位于双亲结点的左子节点的右子树上（左、右双旋转）
思路：先进行左单旋转，再进行右单旋转。
插入40，则56这个节点先失去平衡，必须将56右旋转下去.
我们这里引入了平衡因子来实现，可分为1、0、-1三种情况。
void LeftBalance(AVLTree& tree, AVLNode* ptr)
{
AVLNode* leftsub = ptr->leftchild, * rightsub = nullptr;
switch (leftsub->balance)
{
case 0: cout << "Left balance \n"; break;
case -1:
ptr->balance = 0;
leftsub->balance = 0;
RotateRight(tree, ptr);
break;
case 1:
rightsub = leftsub->rightchild;
switch (rightsub->balance)
{
case 1:
ptr->balance = 0;
leftsub->balance = -1;
break;
case 0:
ptr->balance = 0;
leftsub->balance = 0;
break;
case -1:
ptr->balance = 1;
leftsub->balance = 0;
break;
}
rightsub->balance = 0;
RotateLeft(tree, leftsub);
RotateRight(tree, ptr);
break;
}
}
3.5、AVL树的插入调整
思路：该过程是调用前面四步的函数来实现的，通过平衡因子的选择来实现方法的调用。
void Adjust_AVL(AVLTree& tree, AVLNode* ptr)
{
AVLNode* pa = ptr->parent;
bool high = true;
while (high && pa != nullptr)
{
if (pa->rightchild == ptr)
{
switch (pa->balance)
{
case 0: pa->balance = 1; break;
case -1:
pa->balance = 0;
high = false;
break;
case 1:
RightBalance(tree, pa);
high = false;
break;
}
}
else // left
{
switch (pa->balance)
{
case 0: pa->balance = -1; break;
case 1:
pa->balance = 0;
high = false;
break;
case -1:
LeftBalance(tree, pa);
high = false;
break;
}
}
ptr = pa;
pa = ptr->parent;
}
}
转载：https://blog.csdn.net/qq_46615150/article/details/115617743