1. AI技术聚合首页
  2. 技术文章

C语言之平衡二叉树详解

青葱年少 • • 技术文章 • 阅读 73

什么是平衡二叉树

平衡二叉树是具有平衡属性的有序二叉树，所谓的平衡即当前树的左右子树高度差的绝对值不超过1。因为平衡二叉树是由苏联数学家Adelson-Velskii和Landis提出，所以又称为AVL树。

平衡二叉树的基本特点

  • 是特殊的有序二叉树
  • 左右子树高度差的绝对值不超过1
  • 左右子树仍然是平衡二叉树

为什么会出现平衡二叉树

在学习平衡二叉树之前必定已经学过有序二叉树，有序二叉树的结构特点就是将数据有序的排好，查找起来快，但是有序二叉树有一个缺点，就是当节点呈现的状态是一边倒，那查找数据的时候就没有发挥出二叉树折半查找的优势了，这个时候是线性的查找（类似于链表的查找）。平衡二叉树就是解决有序二叉树一边倒的问题。如果有序二叉树是平衡的，那么查找数据就很快。时间复杂度为O ( l o g n ) O(logn)O(logn)。这样就充分发挥了二叉树的优势。

二叉树四种不平衡的情况

当树的左右子树高度差的绝对值大于1的时候就需要进行旋转操作，将不平衡的树变成平衡的树。以下是会出现的四种不平衡的情况。

  • 左左不平衡
  • 右右不平衡
  • 左右不平衡
  • 右左不平衡

左左不平衡旋转成平衡状态：

C语言之平衡二叉树详解

右右不平衡旋转成平衡状态：

C语言之平衡二叉树详解

左右不平衡旋转成平衡状态：

C语言之平衡二叉树详解

右左不平衡旋转成平衡状态：

C语言之平衡二叉树详解

上面是图解这四种不平衡状态旋转成平衡状态的情况。

C语言实现平衡二叉树

平衡二叉树的结构体描述：

#define Ty int  //以整型数据为例
typedef struct Node
{
	Ty data;             //数据
	int height;          //高度
	struct Node* LChild; //左子树
	struct Node* RChild; //右子树
}Node,AVLTree;

初始化函数:

AVLTree* creatAVLTree(Ty data)
{
    AVLTree* tree = (AVLTree*)malloc(sizeof(AVLTree));
    assert(tree);
    tree->data = data;
    tree->height = 0;
    tree->LChild = NULL;
    tree->RChild = NULL;
    return tree;
}

辅助宏函数：

//辅助函数
#define HEIGHT(x) ((x==NULL)?(-1):(x->height))
#define MAX(a,b)  ((a>b)?(a):(b))
//获取树的新高度
#define GET_NEW_HEIGHT(x) (MAX(HEIGHT(x->LChild),HEIGHT(x->RChild)) + 1)

使用宏函数的好处是运行过程中不需要进行函数压栈的操作，效率快一点。

前序遍历平衡二叉树：

//前序打印
void show_pre(AVLTree* root)
{
	if(root==NULL)
		return;
	printf("data:%dtheight:%dn",root->data,root->height);
	show_pre(root->LChild);
	show_pre(root->RChild);
}

使用前序遍历能更好地看出节点的高度，更方便还原平衡二叉树。

四种不平衡状态旋转的算法实现：

算法核心思想：找到新根的位置，然后进行对应的调整，最后返回新根的地址，这样就实现了旋转的操作，因为旋转后节点的高度改变了，所以在返回之前先调整一下节点的高度。

例如：左左不平衡进行旋转操作

因为是左左不平衡，所以新根的位置是当前根的左子树，那就使用一个指针（newRoot）去接收当前根的左子树，然后使劲将当前根拉下来，让新根代替当前根的位置，那就必须将当前根的LChild指向newRoot的右子树（因为newRoot不一定是空的所以不能直接让curRoot→LChild指向空）。最后就是将newRoot→RChild指向curRoot这样就把位置调整好了。在返回newRoot之前把curRoot和newRoot的高度调整一下。保持树的准确性。

其他的不平衡情况也是类似的操作。

//出现不平衡的情况
//左左不平衡
Node *LL_Rotation(Node *curRoot)
{
	Node *newRoot = curRoot->LChild;
	curRoot->LChild = newRoot->RChild;
	newRoot->RChild = curRoot;

	curRoot->height = GET_NEW_HEIGHT(curRoot);
	newRoot->height = GET_NEW_HEIGHT(newRoot);
	return newRoot;
}

//右右不平衡
Node *RR_Rotation(Node *curRoot)
{
	Node *newRoot = curRoot->RChild;
	curRoot->RChild = newRoot->LChild;
	newRoot->LChild = curRoot;

	curRoot->height = GET_NEW_HEIGHT(curRoot);
	newRoot->height = GET_NEW_HEIGHT(newRoot);
	return newRoot;
}
//左右不平衡
Node *LR_Rotation(Node *curRoot)
{
	curRoot->LChild = RR_Rotation(curRoot->LChild);
	return LL_Rotation(curRoot);
}
//右左不平衡
Node *RL_Rotation(Node *curRoot)
{
	curRoot->RChild = LL_Rotation(curRoot->RChild);
	return RR_Rotation(curRoot);
}

平衡二叉树的插入操作：

插入操作需要考虑到四种情况：

  • 当前节点是空的
  • 要插入进来的数据比当前节点的数据小
  • 要插入进来的数据比当前节点的数据大
  • 要插入进来的数据和当前节点的数据一样大

情况一的解决方案：直接申请一个节点内存。

情况二的解决方案：递归往左边跑，然后跑到对应的位置就申请内存，插入完成后判断需不需要调整。

情况三的解决方案：递归往右边跑，然后跑到对应的位置就申请内存，插入完成后判断需不需要调整。

情况四的解决方案：因为我们做的是一棵没有重复数据的平衡二叉树所以遇到这种情况的时候不进行插入操作。当然如果做的是一棵可以有重复数据的平衡二叉树，那遇到这种情况的时候可以个人的想法放左边放右边都可以。

源代码：

//插入数据
Node *insertNode(Node *curRoot, Ty data)
{
	//插入分有四个大情况
	if (curRoot == NULL)			  //当前节点是空的
		curRoot = creatAVLTree(data); //如果是空就直接创建一个新的节点
	else if (data < curRoot->data)	  //要插入的数据比当前节点的数据小
	{
		//往左边跑
		curRoot->LChild = insertNode(curRoot->LChild, data);
		//插入完成之后，判断需不需要调整树
		if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
			//因为插入的位置在左边，所以插入完成之后，左子树的高度大于等于右子树高度
			curRoot = data < curRoot->LChild->data ? LL_Rotation(curRoot) : LR_Rotation(curRoot);
	}
	else if (data > curRoot->data) //要插入的数据比当前节点的数据大
	{
		//往右边跑
		curRoot->RChild = insertNode(curRoot->RChild, data);
		if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
			//因为插入的位置在右边，所以插入完成之后，右子树的高度大于等于左子树高度
			curRoot = data > curRoot->RChild->data ? RR_Rotation(curRoot) : RL_Rotation(curRoot);
	}
	else //要插入的数据和当前节点的数据一样大
		printf("无法插入数据n");
	//获取新高度
	curRoot->height = GET_NEW_HEIGHT(curRoot);
	return curRoot; //插入完成之后返回当前节点的指针
}

平衡二叉树的删除操作：

删除操作也是要考虑四个大情况：

  • 当前节点是空的
  • 要删除的数据比当前数据小
  • 要删除的数据比当前数据大
  • 要删除的数据和当前数据一样大

情况一的解决方案：没有删除的必要了，结束掉函数

情况二的解决方案：往左边递归找到对应位置，然后进行删除操作

情况三的解决方案：往右边递归找到对应位置，然后进行删除操作

情况四的解决方案：针对这个情况又要分为两个小情况

  • 当前节点的左子树和右子树都存在
  • 当前节点的左右子树至多有一个存在

具体解决方案看代码和注释

源代码：

//查找节点
//找最大节点
Node *maxNode(Node *curRoot)
{
	if (curRoot == NULL)
		return NULL;
	//往右边找
	while (curRoot->RChild)
		curRoot = curRoot->RChild;
	return curRoot;
}

//找最小节点
Node *minNode(Node *curRoot)
{
	if (curRoot == NULL)
		return NULL;
	while (curRoot->LChild)
		curRoot = curRoot->LChild;
	return curRoot;
}

//删除数据
Node *deleteNode(Node *curRoot, Ty data)
{
	//删除数据有四个大情况
	if (curRoot == NULL)	  //当前节点是空的
		return NULL;		  //删除了个寂寞直接结束掉整个函数
	if (data < curRoot->data) //要删除的数据比当前节点的数据小
	{
		//往左边跑
		curRoot->LChild = deleteNode(curRoot->LChild, data);
		//获取新高度
		curRoot->height = GET_NEW_HEIGHT(curRoot);
		//判断需不需要调整
		if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
			curRoot = HEIGHT(curRoot->RChild->LChild) > HEIGHT(curRoot->RChild->RChild) ? RL_Rotation(curRoot) : RR_Rotation(curRoot);
	}
	else if (data > curRoot->data) //要删除的数据比当前节点的数据大
	{
		//往右边跑
		curRoot->RChild = deleteNode(curRoot->RChild, data);
		curRoot->height = GET_NEW_HEIGHT(curRoot);
		if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
			curRoot = HEIGHT(curRoot->LChild->RChild) > HEIGHT(curRoot->LChild->LChild) ? LR_Rotation(curRoot) : LL_Rotation(curRoot);
	}
	else
	{ //要删除的数据和当前节点的数据一样大
		//针对于curRoot这个节点做删除操作
		//主要有两个主要的情况
		if (curRoot->LChild && curRoot->RChild) // curRoot有左子树和右子树
		{
			//先判断左右子树的高度，将高度比较高的子树的节点拿到上面来
			if (HEIGHT(curRoot->LChild) > HEIGHT(curRoot->RChild))
			{ //左子树的高度比右子树的高度高
				//找到左子树的最大节点
				Node *max = maxNode(curRoot->LChild);
				//找到之后就将max的数据替换curRoot的数据
				curRoot->data = max->data;
				//赋值完成之后继续递归，然后释放掉max对应的节点，不能直接在这里释放，因为要调整树的高度
				curRoot->LChild = deleteNode(curRoot->LChild, max->data);
			}
			else
			{ //左子树的高度小于等于右子树的高度
				//找到右子树的最小节点
				Node *min = minNode(curRoot->RChild);
				curRoot->data = min->data;
				curRoot->RChild = deleteNode(curRoot->RChild, min->data);
			}
		}
		else //上一种情况的否定，即curRoot没有子树或者只有一边
		{
			//释放内存
			Node *temp = curRoot;
			// curRoot拿到存在的子树
			curRoot = curRoot->LChild ? curRoot->LChild : curRoot->RChild;
			free(temp);
		}
	}

	return curRoot; //删除完成之后就返回当前节点
}

主函数测试：

int main()
{
	AVLTree *tree = NULL;
	for (int i = 1; i < 10; i++)
		tree = insertNode(tree, i);
	show_pre(tree); //前序打印树
	printf("----------------------------n");
	//删除6这个节点
	tree = deleteNode(tree, 6);
	show_pre(tree);
	printf("程序结束n");
	return 0;
}

运行结果：

C语言之平衡二叉树详解

删除前和删除后的平衡二叉树：

C语言之平衡二叉树详解

到此这篇关于C语言之平衡二叉树详解的文章就介绍到这了,更多相关C++平衡二叉树内容请搜索aitechtogether.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持aitechtogether.com！

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
青葱年少的头像青葱年少普通用户
0
上一篇 2023年5月13日 上午7:39
下一篇 2023年5月13日

相关推荐