平衡二叉树

平衡二叉树(AVL树)是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1,是一种高平衡的二叉排序树

平衡因子(BF)

  • 将二叉排序树上的节点的左子树深度减去右子树深度的值叫做平衡因子
  • 平衡二叉树的平衡因子只能为 -1,0,1
  • 二叉树上若有一个节点的平衡因子的绝对值大于1,则不平衡

最小不平衡子树

  • 距离插入节点最近的,且平衡因子的绝对值大于1的节点为根的子树

图片示例

构建平衡二叉树

  1. 在构建二叉排序树的过程中,每当插入一个节点时,先检查是否因插入而破坏了树的平衡性
  2. 若没有破坏,则仍为平衡二叉树
  3. 若有,则调整最小不平衡子树中各节点之间的链接关系,进行相应的旋转,使之成为新的平衡子树

构建示例

算法实现

结构定义:

1
2
3
4
5
6
7
typedef struct BiTNode
{
int data;//节点数据
int bf;//平衡因子
struct BiTNode *lchild, *rchild;//左右孩子指针

}BiTNode , *BiTree;

右旋操作:

1
2
3
4
5
6
7
8
9
//以p为根的二叉排序树
void Right_Rotate(BiTree *p)
{
BiTree L;
L=(*p) ->lchild;
(*p) ->lchild= L->rchild;
L->rchild=(*p);
*p=L;
}

左旋操作:

1
2
3
4
5
6
7
8
void Left_Rotate(BiTree *p)
{
BiTree R;
R= (*p) -> rchild;
(*p)->rchild=R->lchild;
R -> lchild=(*p);
*p=R;
}

左平衡旋转处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#define LH +1 //左高
#define EH 0 //等高
#define RH -1 //右高

void RightBalance(BiTree *T)
{
BiTree L,Lr;
L=(*T)->lchild;
switch(L->bf)//平衡度处理
{
/*新节点插入在T的左孩子的左子树上*/
case LH:
(*T) ->bf=L->bf=EH;
Right_Rotate(T);
break;
/*新节点插入在T的左孩子的右子树上*/
case RH:
Lr=L->rchild;
/*修改T及其左孩子的平衡因子*/
switch(Lr->bf)
{
case LH:
(*T)->bf=RH;
L->bf=EH;
break;
case EH:
(*T)->bf=L->bf=EH;
break;
case RH:
(*T)->bf=EH
L->bf=LH;
break;
}
Lr->bf=EH;
Left_Rotate(&(*T)->lchild);
Right_Rotate(T);
}
}

右平衡旋转处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#define LH +1 //左高
#define EH 0 //等高
#define RH -1 //右高

void LeftBalance(BiTree *T)
{
BiTree R,Rl;
R=(*T)->rchild;
switch(R->bf)//平衡度处理
{
/*新节点插入在T的右孩子的右子树上*/
case RH:
(*T) ->bf=R->bf=EH;
Left_Rotate(T);
break;
/*新节点插入在T的右孩子的左子树上*/
case LH:
Rl=R->lchild;
/*修改T及其右孩子的平衡因子*/
switch(Rl->bf)
{
case RH:
(*T)->bf=LH;
R->bf=EH;
break;
case EH:
(*T)->bf=R->bf=EH;
break;
case LH:
(*T)->bf=EH
R->bf=RH;
break;
}
Rl->bf=EH;
Right_Rotate(&(*T)->rchild);
Left_Rotate(T);
}
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*int类型e表示新节点,布尔类型*taller表示T的深度*/
Status InsertAVL(BiTree *T,int e,Status *taller)
{
if(!*T)
{
/*插入新节点,树"长高",置taller为TRUE*/
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=e;
(*T)->lchild-(*T)->rchild=NULL;
(*T)->bf=EH;
*taller=TRUE;
}
else
{
if (e==(*T)->data)
{
/*树中已存在和e有相同关键字的节点则不再插入*/
*taller=FALSE;
return FALSE;
}
if (e<(*t)->data)
{
/*继续在T的左子树中进行搜索*/
if(!InsertAVL(&(*T)->lchild,e,taller))
return FALSE; //未插入
//已插入到T的左子树且左子树深度增加
if(*taller)
{
switch((*T)->bf)//检查T的平衡度
{
case LH:
LeftBalance(T);
*taller=FALSE;
break;
case EH:
(*T)->bf=LH;
*taller=TRUE;
break;
case RH:
(*T)->bf=EH;
*taller=FALSE;
break;
}
}
}
else
{
/*继续在T的右子树中进行搜索*/
if(!InsertAVL(&(*T)->rchild,e,taller))
return FALSE;//未插入
/*已插入到T的右子树且深度增加*/
if(*taller)
{

switch((*T)->bf)//检查平衡度
{
case LH:
(*T)->bf=EH;
*taller=FALSE;
break;
case EH:
(*T)->bf=RH;
*taller=TRUE;
break;
case RH:
RightBanlance(T);
*taller=FALSE;
break;
}
}
}
}

return TRUE;
}

构建平衡二叉树:

1
2
3
4
5
6
7
8
int i;
int a[10]={3,2,1,4,5,6,7,10,9,8}
BiTree T=NUll;
Status taller;
for (i=0;i<10;i++)< span>
{
InsertAVL (&T,a[i],&taller);
}

算法分析

  • 此算法为动态查找表算法,即在构造二叉排序树过程中进行旋转达到平衡为动态的进行查找
  • 一旦发生不平衡马上处理旋转
  • 旋转过后变为平衡二叉树,即较为平衡,用二叉排序查找时间复杂度为O(logn)插入删除也为O(logn)

    时间复杂度