AVL树本质上是一颗二叉查找树,但是它又具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为平衡二叉树。下面是平衡二叉树和非平衡二叉树对比的例图:
![[数据结构] 平衡二叉查找树 (AVL树)插图 [数据结构] 平衡二叉查找树 (AVL树)插图](https://www.titan6.cn/wp-content/uploads/2020/03/311739112822613-1.png)
平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1<=bf<=1;
AVL树的作用:
由上图可知,同样的结点,由于插入方式不同导致树的高度也有所不同。特别是在带插入结点个数很多且正序的情况下,会导致二叉树的高度是O(N),而AVL树就不会出现这种情况,树的高度始终是O(lgN).高度越小,对树的一些基本操作的时间复杂度就会越小。这也就是我们引入AVL树的原因。
AVL树的基本操作:
AVL树的操作基本和二叉查找树一样,这里我们关注的是两个变化很大的操作:插入和删除!
我们知道,AVL树不仅是一颗二叉查找树,它还有其他的性质。如果我们按照一般的二叉查找树的插入方式可能会破坏AVL树的平衡性。同理,在删除的时候也有可能会破坏树的平衡性,所以我们要做一些特殊的处理,包括:单旋转和双旋转!
由上图可知:在插入之前树是一颗AVL树,而插入之后结点T的左右子树高度差的绝对值不再 < 1,此时AVL树的平衡性被破坏,我们要对其进行旋转。由上图可知我们是在结点T的左结点的左子树上做了插入元素的操作,我们称这种情况为左左情况,我们应该进行右旋转(只需旋转一次,故是单旋转)。具体旋转步骤是:
T向右旋转成为L的右结点,同时,Y放到T的左孩子上。这样即可得到一颗新的AVL树,旋转过程图如下:
左左情况的右旋举例:
由上图可知:在插入之前树是一颗AVL树,而插入之后结点T的左右子树高度差的绝对值不再 < 1,此时AVL树的平衡性被破坏,我们要对其进行旋转。由上图可知我们是在结点T的右结点的右子树上做了插入元素的操作,我们称这种情况为右右情况,我们应该进行左旋转(只需旋转一次,故事单旋转)。具体旋转步骤是:
T向右旋转成为R的左结点,同时,Y放到T的左孩子上。这样即可得到一颗新的AVL树,旋转过程图如下:
右右情况的左旋举例:
以上就是插入操作时的单旋转情况!我们要注意的是:谁是T谁是L,谁是R还有谁是X,Y,Z!T始终是开始不平衡的左右子树的根节点。显然L是T的左结点,R是T的右节点。X、Y、Y是子树当然也可以为NULL.NULL归NULL,但不能破坏插入时我上面所说的左左情况或者右右情况。
由上图可知,我们在T结点的左结点的右子树上插入一个元素时,会使得根为T的树的左右子树高度差的绝对值不再 < 1,如果只是进行简单的右旋,得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转:
左右情况的左右旋转实例:
由上图可知,我们在T结点的右结点的左子树上插入一个元素时,会使得根为T的树的左右子树高度差的绝对值不再 < 1,如果只是进行简单的左旋,得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转:
右左情况的右左旋转实例:
以上关于二叉树的介绍转载自 https://www.cnblogs.com/zhuwbox/p/3636783.html ,很具体,便于理解。
下面提供我所写的插入(建树)操作代码以供参考
#include<stdio.h> #include<stdlib.h> //平衡二叉树 AVL树的实现 By Titan typedef struct AVLNode *Position; typedef Position AVLTree; struct AVLNode{ int Data; Position Left; Position Right; int Height; }; int Max(int a,int b){ return a > b ? a : b; } int getHeight(AVLTree T){ if(!T){ return -1; }else{ return T->Height; } } int getMaxHeight(AVLTree A,AVLTree B){ return Max(getHeight(A),getHeight(B)); } //定义右单旋 AVLTree S_RR(AVLTree A){ AVLTree B = A->Left; A->Left = B->Right; B->Right = A; A->Height = getMaxHeight(A->Right,A->Left)+1; B->Height = getMaxHeight(A->Right,A->Left)+1; return B; } //定义左单旋 AVLTree S_LR(AVLTree A){ AVLTree B=A->Right; A->Right=B->Left; B->Left=A; A->Height = getMaxHeight(A->Right,A->Left)+1; B->Height = getMaxHeight(A->Right,A->Left)+1; return B; } //定义左右双旋(先左旋后右旋) AVLTree D_LR(AVLTree A){ A->Left=S_LR(A->Left); AVLTree B=S_RR(A); return B; } //定义右左双旋(先右旋后左旋) AVLTree D_RL(AVLTree A){ A->Right=S_RR(A->Right); AVLTree B=S_LR(A); return B; } AVLTree Insert(AVLTree T,int X){ //树空的话直接建树 if(!T){ T=(AVLTree)malloc(sizeof(struct AVLNode)); T->Data=X; T->Left=T->Right=NULL; T->Height=0; } //插入到左子树 else if(T->Data>X){ T->Left=Insert(T->Left,X); //判断是否要平衡 if(getHeight(T->Left)-getHeight(T->Right)==2){ // X插入到左树的左边,右单旋转 if(X<T->Left->Data){ T = S_RR(T); } // X插入到左树的右边,左右双旋 else if(X>T->Left->Data){ T=D_LR(T); } } } //插入到右子树 else if(T->Data<X){ T->Right=Insert(T->Right,X); if(getHeight(T->Right)-getHeight(T->Left)==2){ // X插入到右树的右边,左单旋转 if(X>T->Right->Data){ T = S_LR(T); } // X插入到右树的左边,右左双旋 else if(X<T->Right->Data){ T=D_RL(T); } } }// else 没插入就不用旋转了 //更新树的高度 T->Height = getMaxHeight(T->Right,T->Left)+1; return T; } int main(void){ int n,temp; scanf("%d",&n); AVLTree T=NULL; for(int i=0;i<n;i++){ scanf("%d",&temp); T = Insert(T,temp); } printf("%d",T->Data); }
文章评论
怪厉害的
第一耶
建议作者充分利用一下右边空白,而不是制造很长的页面,

毕竟滑起来怪费事的。
@Haha 这个是适应不同分辨率的响应式布局,在min-width小于767px的时候container是充满页面的。