如果BST树插入的顺序是有序的，那么BST树就会退化成一个双链表结构，查询的速率就会很慢，
所以有了AVL树的意义。
AVL树的定义：
是具有下列性质的二叉搜索树
1、它的左子树和右子树都是AVL树
2、左子树和右子树的高度之差的绝对值不超过1
结点的平衡因子：每一个结点都有一个平衡因子，代表着右子树（左子树）高度减去左子树（右子树）高度的高度差，AVL树任一结点的平衡因子只能取-1，0，1。
AVL树的插入：
向一棵本来是平衡的AVL树插入时，出现了不平衡，则需要做平衡话处理，使其平衡
平衡化旋转
1、如单旋转（左旋和右旋）
2、双旋转（左平衡和右平衡）
3、每插入一个新结点时，AVL树中相关结点的平衡状态会发生改变，因此，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子（左、右子树的高度差）。
如果在某一结点发现高度不平衡，停止回溯。
1、从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点
2、如果这三个结点处于一条直线上，则采用单旋转进行平衡化，单旋转可按其方向分为左单旋和右单旋，其中一个是另一个的镜像，其方向与不平衡的形状相关
3、如果这三个结点处于一条折现上，则采用双旋转进行平衡化，双旋转也分两种。
左单旋转
void RotateLeft(AVLTree* ptree, AVLNode* ptr)//左单旋
{
assert(ptree != nullptr && ptr != nullptr);
AVLNode* newroot = ptr->rightchild;
newroot->parent = ptr->parent;
ptr->rightchild = newroot->leftchild;
if (newroot->leftchild != nullptr)
{
newroot->leftchild->parent = ptr;
}
newroot->leftchild = ptr;
AVLNode* pa = ptr->parent;
if (pa == nullptr)
{
ptree->root = newroot;
}
if (pa->leftchild = ptr)
{
pa->leftchild = newroot;
}
else
{
pa->rightchild = newroot;
}
ptr->parent = newroot;
}右单旋
void RotateRight(AVLTree* ptree, AVLNode* ptr)//右单旋
{
assert(ptree != nullptr && ptr != nullptr);
AVLNode* newroot = ptr->leftchild;
newroot->parent = ptr->parent;
ptr->leftchild = newroot->rightchild;
if (newroot->rightchild != nullptr)
{
ptr->leftchild->parent = ptr;
}
newroot->rightchild = ptr;
AVLNode* pa = ptr->parent;
if (pa == nullptr)
{
ptree->root = newroot;
}else
{
if (pa->leftchild == ptr)
{
pa->leftchild = newroot;
}
else
{
pa->rightchild = newroot;
}
ptr->parent = newroot;
}
}双旋转
//双旋转 分为两次单旋转
void LeftBalance(AVLTree* ptree, AVLNode* ptr)//左平衡
{
assert(ptree != nullptr && ptr != nullptr);
AVLNode* leftsub = ptr->leftchild, * rightsub = nullptr;
switch (leftsub -> balance)
{
case 0:
cout << "left banlance!" << endl;
break;
case -1:
ptr->balance = 0;
leftsub->balance = 0;
RotateRight(ptree, ptr);
break;
case 1:
rightsub = leftsub->rightchild;
switch (rightsub->balance)
{
case 0:
ptr->balance = 0;
leftsub->balance = 0;
break;
case 1:
ptr->balance = 0;
leftsub->balance = -1;
break;
case -1:
ptr->balance = 1;
leftsub->balance = 0;
break;
}
rightsub->balance = 0;
RotateLeft(ptree, leftsub);
RotateRight(ptree, ptr);
break;
}
}
void RightBalance(AVLTree* ptree, AVLNode* ptr)//右平衡
{
assert(ptree != nullptr && ptr != nullptr);
AVLNode* rightsub = ptr->rightchild, * leftsub = nullptr;
switch (rightsub->balance)
{
case 0:
cout << "avl tree right balance" << endl;
break;
case 1:
ptr->balance = 0;
rightsub->balance = 0;
RotateLeft(ptree, ptr);
break;
case -1:
leftsub = rightsub->leftchild;
switch (leftsub->balance)
{
case 0:
ptr->balance = 0;
rightsub->balance = 0;
break;
case 1:
ptr->balance = -1;
rightsub->balance = 0;
break;
case -1:
ptr->balance = 0;
rightsub->balance = 1;
break;
}
leftsub->balance = 0;
RotateRight(ptree, rightsub);
RotateLeft(ptree, ptr);
break;
}
}插入和调整
void Adjust_Insert_Item(AVLTree* ptree, AVLNode* ptr)
{
assert(ptree != nullptr && ptr != nullptr);
bool taller = true;
AVLNode* pa = ptr->parent;
while (pa != nullptr && taller)
{
if (pa->leftchild == ptr)
{
switch (pa->balance)
{
case 0: pa->balance = -1; break;
case 1: pa->balance = 0;
taller = false;
break;
case -1:
LeftBalance(ptree, pa);
taller = false;
break;
}
}
else
{ // ptr pa->rightchild
switch (pa->balance)
{
case 0: pa->balance = 1; break;
case -1: pa->balance = 0;
taller = false;
break;
case 1:
RightBalance(ptree, pa);
taller = false;
break;
}
}
ptr = pa;
pa = ptr->parent;
}
}
bool Insert_Item(AVLTree* ptree, const KeyType kx)
{
assert(ptree != nullptr);
AVLNode* ptr = ptree->root, * pa = nullptr;
while (ptr != nullptr && ptr->key != kx)
{
pa = ptr;
ptr = kx > ptr->key ? ptr->rightchild : ptr->leftchild;
}
if (ptr != nullptr && ptr->key == kx) return false;
ptr = Buynode();
ptr->key = kx;
ptr->parent = pa; //
if (pa != nullptr)
{
if (ptr->key > pa->key)
{
pa->rightchild = ptr;
}
else
{
pa->leftchild = ptr;
}
}
else
{
ptree->root = ptr;
}
Adjust_Insert_Item(ptree, ptr);
ptree->cursize += 1;
}删除
和删除BST树结点思路相同，如果是双分支，则删除中序遍历的下一个结点
