文章目录
前言
这一章将在BST(二叉查找树)的基础上,介绍AVL树。
AVL树
我们知道,二叉查找树满足:
- 若其左子树非空,则左子树上所有节点各自的值都小于根节点的值
- 若其右子树非空,则右子树上所有节点各自的值都大于根节点的值
- 其左右子树都是一棵二叉查找树。
但是我们在实现中很容易遇到其他的特殊情况,例如:
- 左右子树的高度差距太大;
- 高度决定因素比较单一...
这些不平衡的高度会影响到我们的时间复杂度和深度,于是我们就推出了AVL树解决这个问题。
既然AVL是一个带有条件的二叉查找树,那它的最理想情况就是完全平衡的,左右子树具有相同的高度,每个非树叶节点均有两个子节点。称为理想平衡树(perfectly balanced tree)。
但是这个条件太严格,难以使用,需要放宽条件。所以我们定义:
AVL树保证了,每一个节点的子树的高度差最多为1,这里以左子树比右子树高度大一来举例。
我们用Nh表示AVL树的节点数量,h为树叶的数量。我们来看AVL树节点的规律:
h从0~3的情况:
h=4时:
从N3、N4我们就发现了,Nh的值只与N(h-1)+N(h-2)+1 有关,归纳一下就是这样:
- N(0) = 1, N(1) = 2;
- N(h) = N(h-1)+N(h-2)+1. (h>1)
它的递推公式与斐波那契数列很像,即N(n) = F(n) + 1;
了解了AVL树的基本内容后,我们来看看AVL树的相关操作和BST的不同。创建等操作和其他树基本一致,但是我们发现插入操作会有特殊之处——可能破坏AVL 树的特性。
在介绍插入和删除前,我们同样也来简单地写AVL树的基本实现——定义、初始化、其他功能函数等。
定义以及初始化
像BST一样的,我们定义一个AVL树:
typedef int Type;
typedef struct AVLTree{
Type d;
int h;
struct AVLTree *left;
struct AVLTree *right;
}tree;
tree *create(Type d, tree *l, tree *r)
{
tree *node=(tree *)malloc(sizeof(tree));
if(node == NULL) return NULL;
node->d=d;
node->left=l;
node->right=r;
node->h=0; //初始化创建时为0,之后动态调整
return node;
}
AVL树的节点包括的几个组成对象:
(01) d:数据信息。
(02) left:左孩子。
(03) right:右孩子。
(04) h:高度。
其他函数
我们还需要计算树的高度的函数。如果我们这个树是空的,高度应该为-1,因为高度从0开始计算。同时加入一个比较大小的max函数,比较两节点的数据大小
int height(tree *node)
{
return (node!=NULL)?node->h:-1;
}
tree *max(tree *a, tree *b)
{
return (a->d > b->d)?a:b;
}
接下来就是我们的插入和删除啦。
旋转
我们在插入时,大多会破坏AVL树的性质,我们需要更新通向根节点路径上那些节点的所有平衡信息,并恢复AVL树的性质。
旋转的目的是减少高度,通过降低整棵树的高度来平衡。一般插入发生在“外边”的情况可以通过一次旋转解决,称为单旋转,插入发生在“内部” 的情况一般可以通过两次解决,称为双旋转。
单旋转
插入发生在外边的情况,一般可以使用单旋转解决。例如:
LL
在左子树的左子树处插入,LeftLeft,也称为"左左"。此时"根的左子树的高度"比"根的右子树的高度"大1。如图这两种情况,都是在左子树的左子树处插入:(图为根节点8处左右子树不平衡)
图中,根节点(8)的左子树(4)的左子树(2)还有非空子节点,根的左子树的高度为2,而根节点(8)的右子树(12)没有子节点,根的右子树的高度为0。此时高度差>1,平衡条件被破坏。
我们从简单的例子开始,例如:
我们插入一个节点在左树叶5上。
平衡被破坏,此时让它重新平衡需要进行右旋转,被破坏了平衡首先要找到是哪个子树被破坏了平衡,然后调整这个子树。然后继续往上一个一个的调整。
所以我们先找离新插入的节点最近的不平衡的树进行调整,上图中就是根节点为7的树. 7的左子树高度为1,右子树不存在,高度为-1,此时高度差为2,处于不平衡状态。
此时我们要满足AVL树的要求——左右子树高度差<=1,并且根节点的左侧大于右侧(BST要求),那我们就对它进行一次顺时针向右的旋转,即固定中间的被插入的节点5,以它为轴,向右旋转。此时7就掉到了5的右边,成为5的右子树了。然后5替代了原来7的位置(5代替7上位),如图:
经过这样的调整过后,我们就已经成功把不平衡的LL情况,恢复为平衡了。
那如果节点5本来就有了右子树呢?这个就会涉及到双旋转,在之后会涉及。
关于LL的图解:
我们看图说话,直接写出LL的函数:
static tree *LLspin(tree *root)
{
tree *k1=root->left;
tree *k2=root;
k2->left=k1->right;
k1->right=k2;
k2->h=maxheight(height(k2->left),height(k2->right))+1;
k1->h=maxheight(height(k1->left),height(k2))+1;
return k1;
}
RR
同理,和LL一样的,我们在在右子树的右子树处插入,RightRight,称为"右右"。此时"根的右子树的高度"比"根的左子树的高度"大2,导致AVL树失去了平衡。
图中,根节点(8)的右子树(12)的右子树(14)还有非空子节点,根的左子树的高度为2,而根节点(8)的左子树(4)没有子节点,根的右子树的高度为0。此时高度差>1,平衡条件被破坏。
和LL一样,在右子树的右子树上插入节点破坏的平衡需要左旋转来矫正。那么同样的,我们进行如下操作:
- 找到最近非平衡树;
- 固定有一个子节点的节点,以它为轴旋转;
- 逐级调整直到成为AVL树。
如图示例:
关于RR的图解:
同理,RR的函数为:
static tree *RRspin(tree *root)
{
tree *k1=root;
tree *k2=root->right;
k1->right=k2->left;
k2->left=k1;
k1->h=maxheight(height(k1->left),height(k1->right))+1;
k2->h=maxheight(height(k2->left),height(k2->right))+1;
return k2;
}
双旋转
我们之前讨论的情况是在左子树的左子树上插入节点(LL),或是在右子树的右子树上插入节点(RR),那如果是在左子树的右节点插入,或右子树的左节点插入呢?我们来讨论下一这两种情况。
LR
LeftRight,也称为"左右"。插入或删除一个节点后,根节点的左子树的右子树还有非空子节点,导致"根的左子树的高度"比"根的右子树的高度"大2,导致AVL树失去了平衡。
LR形如:
如果在LL的例子中不是向左插入3,而是向右插入6,平衡条件依然被破坏,如图:
我们的解决方法和之前相同,先找到最近的不平衡子树。这里依然是以7为根的树,于是我们尝试对它进行旋转。可能会得到下面这种情况:
但这是一种错误的旋转,因为我们发现左节点6居然比根节点5大,不满足BST的性质。要是插入的这个节点在左子树上就刚好可以这样旋转了。
所以我们可以先把插在右节点上的节点旋转到左边,即:
这里的旋转是针对根为5的子树的旋转,我们固定节点6,再向左旋转,就得到了如图的子树。
此时旋转了一次以后我们就得到了类似于LL的形式,我们就对其进行右旋转。
最后我们就得到了AVL树。全过程进行了一次左旋,再进行了一次右旋,如图:
知道LR双旋转后这时我们就可以解决之前在LL时提出的问题——如果插入的节点有兄弟节点,该如何旋转?
例如,我们插入的节点是3,原本就存在节点6:
我们同样的对它试着进行旋转。此时旋转过程中有阻碍,我们一般把原来的节点拿走,旋转新的节点,并把原来的节点接入旋转后的节点上。固定节点5向右旋转,此时旋转时为了让7落下来且不破坏BST性质,我们应该先判断一次右节点(6)与前节点的大小(7)。
若右节点小于前节点,则右节点成为旋转下来后的前节点的左节点;若右节点大于前节点,则右节点成为旋转下来后的前节点的右节点。
此时6<7,于是把节点7旋转下来,并把节点6作为节点7的左节点。
但是我们此时整体的树依然不是AVL树,我们发现这时候树满足,插入节点位于左子树的右子树上,满足LR的形式,此时对它进行LR的先左旋再右旋即可恢复。
关于LR先左旋再右旋的图解:
static tree *LRspin(tree *root)
{
root->left=RRspin(root->left);
return LLspin(root);
}
RL
RightLeft,称为"右左"。插入或删除一个节点后,根节点的右子树的左子树还有非空子节点,导致"根的右子树的高度"比"根的左子树的高度"大1,导致AVL树失去了平衡。
RL形如:
当破坏平衡的节点是这个树的右子树的左子树时,要进行先右旋转再左旋转来矫正。
与LR类似的过程就不再描述,例子与图例:
关于RL先右旋再左旋的图解:
static tree *RLspin(tree *root)
{
root->right=LL(root->right);
return RRspin(root);
}
旋转总结
总结一下旋转:
- 旋转的目的就是减少高度,通过降低整棵树的高度来平衡。哪边的树高,就把那边的树向上旋转;
- 旋转保证的仍然是中序遍历的序列(BST性质);
- 每次旋转基本都是同一个节点,那个节点一般是子树中深度为1的,大多数情况是这样的。
插入
我们已经了解了旋转的方法,接下来就是在插入节点时进行旋转操作的实现:
tree *insert(tree *node, Type d)
{
if(node == NULL)
{
node=create(d, NULL, NULL);
if(!node)
{
printf("Error, no space.\n");
return NULL;
}
}
if(d == node->d)
{
printf("Error, cannot add same node\n");
return NULL;
}
else if(d < node->d) //往左边插入
{
node->left=insert(node->left,d);
if(height(node->left) - height(node->right) > 1) // 插入节点后,若AVL树失去平衡,则进行相应的调节。
{
if(dleft->d)
LLspin(node);
else LRspin(node);
}
}
else if(d > node->d) //往右边插入
{
node->right=insert(node->right,d);
if(height(node->right) - height(node->left) > 1) // 插入节点后,若AVL树失去平衡,则进行相应的调节。
{
if(d > node->right->d)
RRspin(node);
else RLspin(node);
}
}
node->h=max(height(node->left),height(node->right))+1;
//取左右子树的最大高度,并且+1表示当前根节点的高度
return node;
}
删除
删除节点也可能破坏AVL树的结构,一般来说会有下面几种情况:
- 根为空或者没有要删除的节点,直接返回NULL。
- 待删除的节点在左子树中,删除节点后,若AVL树失去平衡,需要旋转。(因为删除节点满足BST删除的性质,需要进行一些调整,可能导致失去平衡)
- 待删除的节点在右子树中,删除节点后,若AVL树失去平衡,需要旋转。
- 待删除的节点为当前根节点
- 根节点左右子树均非空
- 根节点左右子树有空
我们在删除当前节点的时候,因为不是插入,我们可以直接让该节点的值替换为其左/孩子节点的值,然后删除左/右孩子节点。
我们分情况来看,先从底下的树叶或左右树叶情况来看:
此时不需要通过旋转来平衡AVL树。也会出现需要旋转调整的情况:
当需要删除的结点是非叶子节点,该节点的值替换为该节点的前驱节点(或者后继节点),然后删除前驱节点(或者后继节点)。
于是我们的代码部分:
tree *delete(tree *root, tree *node) //返回根节点,删除node
{
if(!root || !node) //case1
return NULL;
if(node->d < root->d) //case2:待删除的节点在左子树
{
root->left=delete(root->left,node);
//删除节点后,若AVL树失去平衡,则进行相应的调节。
if(height(root->right) - height(root->left) == 2)
{
tree *p=root->right;
if(height(p->right) > height(p->left)) //检查它的右边,因为删除后可能右边高
root=RRspin(root); //相当于在右侧的左边插入了一个
else root=RLspin(root);
}
}
if(node->d > root->d) //case3:待删除的节点在右子树
{
root->right=delete(root->right,node);
//删除节点后,若AVL树失去平衡,则进行相应的调节。
if(height(root->right) - height(root->left) == 2)
{
tree *p=root->left;
if(height(p->left) > height(p->right)) //检查它的左边
root=LLspin(root); //相当于在左侧的左边插入了一个
else root=LRspin(root);
}
}
else //case4: 待删除的节点为当前根节点
{
if(root->left && root->right) //左右孩子都非空
{
if(height(root->left) > height(root->right)) //如果左子树比右子树高;
{
//(1)找到左子树中最大的——左子树根的最右节点
tree *maxima=root->left;
while(maxima->right)
{
maxima=maxima->right;
}
//(2)将它的值赋给当前的根
root->d=maxima->d;
//(3)把最大值的那个位置删了
root->left=delete(root->left,maxima); //删除并连接
}
if(height(root->left) <= height(root->right)) //如果左子树比右子树低或相等;
{
//(1)找到右子树中最小的——右子树根的最左节点
tree *minima=root->right;
while(minima->left)
{
minima=minima->left;
}
//(2)将它的值赋给当前的根
root->d=minima->d;
//(3)把最小值的那个位置删了
root->right=delete(root->right,minima);
}
}
else //此时为树叶或只有左树叶或右树叶
{
tree *t=root;
if(root->left)
{
root=root->left;
}
else if (root->right)
{
root=root->right;
}
//删除之前节点
free(t);
}
}
return root;
}
后记
AVL树的旋转是平衡是它的特点,并且还满足BST的性质。建议是把旋转的图像理解记忆,根据图像即可写出代码。
Comments NOTHING