【数据结构】之平衡二叉树（AVL树）的实现

喜欢ヅ旅行 2022-12-11 15:06 179阅读 0赞

### 文章目录 ###

*  标题
 *   *  概念
     *  实现原理
     *  实现算法
     *  总结
     *  测试代码

# 标题 #

## 概念 ##

**平衡二叉树（Balanced Binary Tree），是一种二叉树排序树，其中每一个结点的左子树和右子树的高度差至多等于1。**

平衡二叉树，顾名思义，他是一种高度平衡的二叉树。那么高度平衡是什么意思了？它要么是一颗空树，要么他的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过一。**我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor)**。那么平衡二叉树上所有结点的平衡因子只可能是-1,0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

图1-1中，为什么图一是平衡二叉树，而图二却不是呢？这里考察的就是我们对平衡二叉树的理解。他的前提首先是一颗二叉排序树，图二则不满足条件。图三不是平衡二叉树的原因就是，节点58的左子树高度为2，而右子树为空，二者差大于了绝对值1，因此也不是平衡的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center]

图1-1

距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，称为最小不平衡子树，如图1-2所示，当新插入结点37，距离它最近的平衡因子绝对值超过1的结点是58（左子树高度2减去右子树高度0）所以58开始以下的子树为最小不平衡子树。  
![在这里插入图片描述][20201003101543945.png_pic_center]

图1-2

## 实现原理 ##

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏块树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树的特性的前提下，调整最小不平衡二叉树中各个结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

先说一个构建平衡二叉树过程的例子。  
假设我们现在有一个数组a\[10\]=\{3,2,1,4,5,6,7,10,9,8\}需要构建二叉排序树，在没有学习平衡二叉树之前，根据二叉排序树的特性，我们通常会将它构成如图1-3的图1所示的样子。高度为4的二叉排序树才可以提供高效的查找效率。问题来了，如何将一个数组构建成图2的结构了？  
![在这里插入图片描述][2020100311561292.png_pic_center]

图1-3

对于数组a\[10\]=\{3,2,1,4,5,6,7,10,9,8\}的前两位3和2，我们就正常的构建，到了第三个树“1”的时候，发现此时根结点"3"的平衡因子变成了2，此时整棵树都成了最小不平衡树。因此需要调整，如果1-4的图1 结点左上角数字为平衡因子BF。因为BF值为正，因此我们将整个树进行顺时针右旋转，此时结点2成了根结点，3成了2的右孩子，这样三个结点的BF值仅为0，非常的平衡，如图2所示。

然后我们在增加节点4，平衡因子没有发生改变，如图二所示。增加节点5时，节点3的BF值为-2，说明要旋转了。由于BF是负值，所以我们对这颗最小平衡子树进行逆时针左旋转，如图4,此时整棵树达到了平衡。  
![在这里插入图片描述][20201003120936251.png_pic_center]![在这里插入图片描述][20201003120944308.png_pic_center]

图1-4

继续，增加节点6时，发现根结点2的BF值变成了-2，如图1-5所示的图6，所以我们对根结点进行逆时针左旋转，注意此时本来结点3是4的左孩子，由于旋转后需要满足二叉排序树的特性，因此它成了节点2的右孩子，如图7，增加节点7，同样的左旋转，如图8和图9，使整个树达到了平衡。  
![在这里插入图片描述][2020100312211147.png_pic_center]

图1-5

当增加节点10时，结构没有发生变化，图1-6的图10所示。在增加节点9，此时结点7的BF变成了-2，理论上我们只需要旋转最小不平衡树7,9,10即可，但是如果左旋转之后，节点9就成了10的右孩子，这是不符合二叉排序树的特性的，此时不能进行简单的左旋转。如图11所示。  
![在这里插入图片描述][2020100312423819.png_pic_center]

图1-6

观察图11，根本原因在于节点7的BF是-2，而节点10的BF是1，也就是说，他们两一正一负，符号并不统一，而前面几次的旋转，无论是左旋还是右旋，最小不平衡的子树的根结点与它的子节点符号都是相同的。这就是不能直接旋转的关键。  
符号不统一，就先旋转到符号统一了再说，我们先对节点9和结点10进行右旋转，使得节点10成了9的右子树，节点9的BF为-1，此时就与节点7的BF值符号统一了，图12所示。

这样我们再以节点为7的最小不平衡子树进行左旋转，得到图1-7的图13。接着插入节点8，情况与刚才类似。

![在这里插入图片描述][20201003125443432.png_pic_center]

图1-7

## 实现算法 ##

首先是需要改下二叉排序树的节点结构，增加一个BF，存储平衡因子。

/* 二叉树的二叉链表结点结构定义 */
    typedef  struct BiTNode	/* 结点结构 */
    {
        
    	int data;	/* 结点数据 */
    	int bf; /*  结点的平衡因子 */ 
    	struct BiTNode *lchild, *rchild;	/* 左右孩子指针 */
    } BiTNode, *BiTree;

右旋转操作

/* 对以p为根的二叉排序树作右旋处理， */
    /* 处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */
    void R_Rotate(BiTree *P)
    {
         
    	BiTree L;
    	L=(*P)->lchild; /*  L指向P的左子树根结点 */ 
    	(*P)->lchild=L->rchild; /*  L的右子树挂接为P的左子树 */ 
    	L->rchild=(*P);
    	*P=L; /*  P指向新的根结点 */ 
    }

左旋转操作

/* 对以P为根的二叉排序树作左旋处理， */
    /* 处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0  */
    void L_Rotate(BiTree *P)
    {
         
    	BiTree R;
    	R=(*P)->rchild; /*  R指向P的右子树根结点 */ 
    	(*P)->rchild=R->lchild; /* R的左子树挂接为P的右子树 */ 
    	R->lchild=(*P);
    	*P=R; /*  P指向新的根结点 */ 
    }

左平衡旋转处理

#define LH +1 /*  左高 */ 
    #define EH 0  /*  等高 */ 
    #define RH -1 /*  右高 */ 
    
    /*  对以指针T所指结点为根的二叉树作左平衡旋转处理 */
    /*  本算法结束时，指针T指向新的根结点 */
    void LeftBalance(BiTree *T)
    {
         
    	BiTree L,Lr;
    	L=(*T)->lchild; /*  L指向T的左子树根结点 */ 
    	switch(L->bf)
    	{
         /*  检查T的左子树的平衡度，并作相应平衡处理 */ 
    		 case LH: /*  新结点插入在T的左孩子的左子树上，要作单右旋处理 */ 
    			(*T)->bf=L->bf=EH;
    			R_Rotate(T);
    			break;
    		 case RH: /*  新结点插入在T的左孩子的右子树上，要作双旋处理 */ 
    			Lr=L->rchild; /*  Lr指向T的左孩子的右子树根 */ 
    			switch(Lr->bf)
    			{
         /*  修改T及其左孩子的平衡因子 */ 
    				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;
    			L_Rotate(&(*T)->lchild); /*  对T的左子树作左旋平衡处理 */ 
    			R_Rotate(T); /*  对T作右旋平衡处理 */ 
    	}
    }

主函数

/*  若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */ 
    /*  数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */ 
    /*  失去平衡，则作平衡旋转处理，布尔变量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;
    			if(*taller) /*   已插入到T的左子树中且左子树“长高” */ 
    				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;
    			if(*taller) /*  已插入到T的右子树且右子树“长高” */ 
    				switch((*T)->bf) /*  检查T的平衡度 */ 
    				{
        
    					case LH: /*  原本左子树比右子树高，现左、右子树等高 */ 
    							(*T)->bf=EH; *taller=FALSE;	break;
    					case EH: /*  原本左、右子树等高，现因右子树增高而使树增高  */
    							(*T)->bf=RH; *taller=TRUE; break;
    					case RH: /*  原本右子树比左子树高，需要作右平衡处理 */ 
    							RightBalance(T); *taller=FALSE; break;
    				}
    		}
    	}
    	return TRUE;
    }

## 总结 ##

如果我们需要查找的集合本身没有顺序，在频繁查找的同事也需要经常的插入和删除操作，显然我们需要构建一颗平衡二叉树，但是不平衡的二叉排序树，查找效率是非常低下的，因此我们在构建时，就让二叉树排序树是平衡二叉树，此时查找的时间复杂O(logn)，而插入删除也是O（logn）。

## 测试代码 ##

#include "stdio.h"    
    #include "stdlib.h"   
    #include "io.h"  
    #include "math.h"  
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 100 /* 存储空间初始分配量 */
    
    typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 
    
    
    /* 二叉树的二叉链表结点结构定义 */
    typedef  struct BiTNode	/* 结点结构 */
    {
        
    	int data;	/* 结点数据 */
    	int bf; /*  结点的平衡因子 */ 
    	struct BiTNode *lchild, *rchild;	/* 左右孩子指针 */
    } BiTNode, *BiTree;
    
    
    /* 对以p为根的二叉排序树作右旋处理， */
    /* 处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */
    void R_Rotate(BiTree *P)
    {
         
    	BiTree L;
    	L=(*P)->lchild; /*  L指向P的左子树根结点 */ 
    	(*P)->lchild=L->rchild; /*  L的右子树挂接为P的左子树 */ 
    	L->rchild=(*P);
    	*P=L; /*  P指向新的根结点 */ 
    }
    
    /* 对以P为根的二叉排序树作左旋处理， */
    /* 处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0  */
    void L_Rotate(BiTree *P)
    {
         
    	BiTree R;
    	R=(*P)->rchild; /*  R指向P的右子树根结点 */ 
    	(*P)->rchild=R->lchild; /* R的左子树挂接为P的右子树 */ 
    	R->lchild=(*P);
    	*P=R; /*  P指向新的根结点 */ 
    }
    
    #define LH +1 /*  左高 */ 
    #define EH 0  /*  等高 */ 
    #define RH -1 /*  右高 */ 
    
    /*  对以指针T所指结点为根的二叉树作左平衡旋转处理 */
    /*  本算法结束时，指针T指向新的根结点 */
    void LeftBalance(BiTree *T)
    {
         
    	BiTree L,Lr;
    	L=(*T)->lchild; /*  L指向T的左子树根结点 */ 
    	switch(L->bf)
    	{
         /*  检查T的左子树的平衡度，并作相应平衡处理 */ 
    		 case LH: /*  新结点插入在T的左孩子的左子树上，要作单右旋处理 */ 
    			(*T)->bf=L->bf=EH;
    			R_Rotate(T);
    			break;
    		 case RH: /*  新结点插入在T的左孩子的右子树上，要作双旋处理 */ 
    			Lr=L->rchild; /*  Lr指向T的左孩子的右子树根 */ 
    			switch(Lr->bf)
    			{
         /*  修改T及其左孩子的平衡因子 */ 
    				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;
    			L_Rotate(&(*T)->lchild); /*  对T的左子树作左旋平衡处理 */ 
    			R_Rotate(T); /*  对T作右旋平衡处理 */ 
    	}
    }
    
    /*  对以指针T所指结点为根的二叉树作右平衡旋转处理， */ 
    /*  本算法结束时，指针T指向新的根结点 */ 
    void RightBalance(BiTree *T)
    {
         
    	BiTree R,Rl;
    	R=(*T)->rchild; /*  R指向T的右子树根结点 */ 
    	switch(R->bf)
    	{
         /*  检查T的右子树的平衡度，并作相应平衡处理 */ 
    	 case RH: /*  新结点插入在T的右孩子的右子树上，要作单左旋处理 */ 
    			  (*T)->bf=R->bf=EH;
    			  L_Rotate(T);
    			  break;
    	 case LH: /*  新结点插入在T的右孩子的左子树上，要作双旋处理 */ 
    			  Rl=R->lchild; /*  Rl指向T的右孩子的左子树根 */ 
    			  switch(Rl->bf)
    			  {
         /*  修改T及其右孩子的平衡因子 */ 
    				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;
    			  R_Rotate(&(*T)->rchild); /*  对T的右子树作右旋平衡处理 */ 
    			  L_Rotate(T); /*  对T作左旋平衡处理 */ 
    	}
    }
    
    /*  若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */ 
    /*  数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */ 
    /*  失去平衡，则作平衡旋转处理，布尔变量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;
    			if(*taller) /*   已插入到T的左子树中且左子树“长高” */ 
    				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;
    			if(*taller) /*  已插入到T的右子树且右子树“长高” */ 
    				switch((*T)->bf) /*  检查T的平衡度 */ 
    				{
        
    					case LH: /*  原本左子树比右子树高，现左、右子树等高 */ 
    							(*T)->bf=EH; *taller=FALSE;	break;
    					case EH: /*  原本左、右子树等高，现因右子树增高而使树增高  */
    							(*T)->bf=RH; *taller=TRUE; break;
    					case RH: /*  原本右子树比左子树高，需要作右平衡处理 */ 
    							RightBalance(T); *taller=FALSE; break;
    				}
    		}
    	}
    	return TRUE;
    }
    
    int main(void)
    {
            
    	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++)
    	{
        
    		InsertAVL(&T,a[i],&taller);
    	}
    	printf("本样例建议断点跟踪查看平衡二叉树结构");
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/eaae89a6c5894b088a9229075b7b5c93.png
[20201003101543945.png_pic_center]: /images/20221123/59e381c7e76c486d8c86d417fb3fd05e.png
[2020100311561292.png_pic_center]: /images/20221123/17ea7f8fdff6499cb2b2e3b61d53d390.png
[20201003120936251.png_pic_center]: https://img-blog.csdnimg.cn/20201003120936251.png#pic_center
[20201003120944308.png_pic_center]: /images/20221123/128a715b99b34980b41f9059d77ace23.png
[2020100312211147.png_pic_center]: /images/20221123/5ccc1bca570b46dfa9862b2205762356.png
[2020100312423819.png_pic_center]: /images/20221123/76b52a746bb94fc6b9c3870e52f4f078.png
[20201003125443432.png_pic_center]: /images/20221123/c1a7a751011a40dcbec29a970a0107ac.png