如果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;
}
}
双旋转
文章来源:https://www.toymoban.com/news/detail-448423.html
//双旋转 分为两次单旋转
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树结点思路相同,如果是双分支,则删除中序遍历的下一个结点文章来源地址https://www.toymoban.com/news/detail-448423.html
到了这里,关于AVL树(平衡二叉搜索树)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!