AVL树的建立的完整C代码怎么编写

发布时间:2021-10-14 14:14:57 作者:柒染
来源:亿速云 阅读:120

AVL树的建立的完整C代码怎么编写,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。

平衡二叉树的相关概念

二叉搜索树上实现查找的时间复杂度与从根节点到所查对象节点的路径成正比,最坏情况下等于树的高度。

在构造二叉搜索树时,如果输入对象的序列恰好是按其关键码大小有序,则结果将产生一棵单支树。

例如:输入序列为{11,39,46,38,75}
AVL树的建立的完整C代码怎么编写
在这样的树上查找所需要的时间是O(n)(与节点个数成正比)。

平衡树(Balanced Tree):高度为O(logn)的树。

平衡二叉树(Balanced Binary Tree):由阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的,所以又称为AVL树。

空二叉树是AVL树;

如果T是一棵非空的二叉搜索树,TL和TR分别是其左子树和右子树,那么当T满足以下条件时,T是一棵AVL树:
1)TL和TR 是AVL树;
2)|hL-hR|≤1,hL和hR分别是左子树和右子树的高度。

n个元素的AVL树的高度是O(logn);
一棵n元素的AVL搜索树能在O(高度)=O(logn) 的时间内完成搜索;
将一个新元素插入到一棵n元素的AVL搜索树中,可得到一棵n+1元素的AVL树,这种插入过程可以在O(logn)时间内完成;
从一棵n元素的AVL搜索树中删除一个元素,可得到一棵n-1元素的AVL树,这种删除过程可以在O(logn)时间内完成。

为每个节点增加一个平衡因子bf。节点x 的平衡因子bf (x)定义为:bf (x)= hL-hR 。
即:x的左子树的高度-x 的右子树的高度。

从AVL树的定义可以知道,平衡因子的可能取值为-1、0、1。

如果树中任意一个结点的平衡因子的绝对值大于 1,则这棵二叉树就失去平衡。

如果一棵AVL树有n个节点,其高度可以保持在O(logn),因此平均搜索长度也可以保持在O(logn)。
二叉搜索树的算法完全适用于AVL树。

若一棵二叉搜索树是平衡二叉树,插入某个节点后,可能会变成非平衡二叉树;
【解决办法】对该二叉树进行平衡处理,使其变成一棵平衡二叉树。

非AVL树的平衡化处理

    1. 单旋转(LL旋转和LR旋转)

    2. 双旋转(LR旋转和RL旋转)

如果这三个节点处于一条直线上,则采用单旋转进行平衡化。

如果这三个节点处于一条折线上,则采用双旋转进行平衡化。


LL 平衡旋转:

AVL树的建立的完整C代码怎么编写

若在 C 的左子树的左子树上插入 结点,使 C 的平衡因子从 1 增加 至 2, 需要进行一次顺时针旋转。 (以 B 为旋转轴)

RR 平衡旋转:

AVL树的建立的完整C代码怎么编写

若在 A 的右子树的右子树上插入 结点,使 A 的平衡因子从 -1 改变为 -2,需要进行一次逆时针旋转。(以 B 为旋转轴)

LR 平衡旋转:

AVL树的建立的完整C代码怎么编写

若在 C 的左子树的右子树上插入 结点,使 C 的平衡因子从 1 增加 至 2, 需要先进行逆时针旋转,  再顺时针旋转。 (以插入的结点 B 为旋转轴)

RL 平衡旋转:

AVL树的建立的完整C代码怎么编写

若在 A 的右子树的左子树上插入 结点,使 A 的平衡因子从 -1 改变 为 -2,需要先进行顺时针旋转,再逆时针旋转。(以插入的结点 B 为旋转轴)

LL旋转:新插入节点在不平衡节点的左子树的左子树中;

RR旋转:新插入节点在不平衡节点的右子树的右子树中;

LR旋转:新插入节点在不平衡节点的左子树的右子树中;

RL旋转:新插入节点在不平衡节点的右子树的左子树中。

AVL树的建立完整C代码

/* AVL树的创建完整C代码 */

#include <stdio.h>
#include <stdlib.h>
#define max(a,b) ( ((a)>(b)) ? (a):(b) )

typedef int ElemType;

//定义了平衡二叉树的结构体
typedef struct AVLNode {
	ElemType data;
	int height;
	struct AVLNode *lchild, *rchild;
}AVLNode, *AVLTree;

//计算高度的函数
int GetHeight( AVLTree t )
{
	if( NULL == t )
		return -1;
	else
		return (1+max(GetHeight(t->lchild),GetHeight(t->rchild)));
}

//右旋操作
void SingleRotateWithRight( AVLTree *t )
{
	AVLTree p;

	p = (*t)->lchild;
	(*t)->lchild = p->rchild;
	p->rchild = (*t);

	//结点的位置改变,更新结点的高度值
	(*t)->height = GetHeight( *t );
	p->height = GetHeight( p );
	*t = p;
}

//左旋操作
void SingleRotateWithLeft( AVLTree *t )
{
	AVLTree p;

	p = (*t)->rchild ;
	(*t)->rchild = p->lchild ;
	p->lchild = (*t) ;

	//结点为位置改变,更新新结点的高度值
	(*t)->height = GetHeight( *t );
	p->height = GetHeight( p );

	*t = p;
}

//双旋转操作--先左后右
void DoubleRotateWithLeft( AVLTree *t )		//LR型失衡AVL
{
	 SingleRotateWithLeft( &(*t)->lchild );
	 SingleRotateWithRight( t );
}

//双旋操作--先右后左
void DoubleRotateWithRight( AVLTree *t )	//RL型失衡AVL
{
	SingleRotateWithRight( &(*t)->rchild );
	SingleRotateWithLeft( t );
}

//AVL树的结点插入函数
void Insert( AVLTree *t, ElemType e )
{
	if( NULL == *t ) {
		(*t) = (AVLTree)malloc(sizeof(AVLNode));
		(*t)->data = e;
		(*t)->height = 0;
		(*t)->lchild = (*t)->rchild = NULL;
	}

	else if( e < (*t)->data ) {		//插入到左子树中
		Insert( &(*t)->lchild, e );
		if( GetHeight((*t)->lchild) - GetHeight((*t)->rchild) == 2 ) {	//AVL树不平衡
			if( e < (*t)->lchild->data ) 		//LL插入到左子树左边
				SingleRotateWithRight( &(*t) );
			else
				DoubleRotateWithLeft( &(*t) );	//LR插入到左子树右边,先对左子树左旋,再对当前根节点右旋
		}
	}

	else if( e > (*t)->data ) {
		Insert( &(*t)->rchild, e );
		if( GetHeight((*t)->lchild) - GetHeight((*t)->rchild) == -2 ) {
			if( e > (*t)->rchild->data )			//插入到右子树右边
				SingleRotateWithLeft( &(*t) );
			else
				DoubleRotateWithRight( &(*t) );    //插入到右子树左边,先对右子树右旋,再对当前根节点左旋
		}
	}

	(*t)->height = max( GetHeight((*t)->lchild), GetHeight((*t)->rchild)) + 1;
}

//定义创建AVL树的函数
void CreateAVL( AVLTree *t, ElemType *a, int n )
{
	(*t) = NULL;
	for( int i=0; i<n; i++ )
		Insert( t, a[i] );
}


//中序遍历打印AVL树
void InOrderPrint( AVLTree t )
{
	if( NULL == t )
		return;

	InOrderPrint( t->lchild );
	printf("%d ", t->data);
	InOrderPrint( t->rchild );
}


int main()
{
	int n;
	AVLTree t;
	printf("请输入AVL树的结点数:\n");
	scanf("%d", &n);
	ElemType *a = (ElemType *)malloc(sizeof(ElemType)*n);
	printf("请输入结点数据:\n");
	for( int i=0; i<n; i++ )
		scanf("%d", &a[i]);

	CreateAVL( &t, a, n );
	printf("该AVL树的中序遍历结果为:\n");
	InOrderPrint( t );

	printf("\n");

	return 0;
}

测试数据以及测试结果

AVL树的建立的完整C代码怎么编写

经过单步调试可得AVL树为:

AVL树的建立的完整C代码怎么编写

测试通过。

看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注亿速云行业资讯频道,感谢您对亿速云的支持。

推荐阅读:
  1. 浅析AVL树算法
  2. AVL树之删除算法

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

avl c语言

上一篇:如何实现基于maven的web工程docker

下一篇:如何搭建私有镜像仓库

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》