当前位置： 首页 > article >正文

【算法】- 查询 -平衡二叉树

article 2024/10/9 21:04:48

文章目录

  • 前言
  • 一、平衡二叉树思想
  • 二、如何进行平衡调整
    • 2.1如何实现左平衡（L_Balance）
  • 三、平衡二叉树
  • 总结

前言

编译语言：C++
编译器：VS2022

一、平衡二叉树思想

在上节我们讲到了二叉排序树，当我们在使用二叉排序树时，要插入的数组是一个有序数组，这时二叉排序树的效率将会下降，所以就有了平衡二叉排序树来解决二叉排序树效率下降的问题。平衡二叉树的大致思想就是将数组保持平衡状态，平衡因子在-1，0，1之间不能超过，超过则视为破坏平衡，需要进行平衡调整。

二、如何进行平衡调整

首先，我们的直到根节点的平衡因子为多少，比如跟结点为1，则这时分为三种情况插入左孩子，插入右孩子，插入时使平衡因子为0。（这里我们以左孩子的插入为例）插入左孩子时我们还要判断根节点当前平衡因子状况。

#define LH +1  //左高
#define EH 0   //等高
#define RH -1  //右高

if (e < (*T)->data)//判断e值和根节点的数据大小，小就进入左孩子插入
{
	if (!InsertAVL(&(*T)->lchild, e, taller))//判断是否已经插入，已经插入则返回
	{
		return FALSE;
	}
	if (*taller)
	{
		switch ((*T)->bf)//根据平衡因子进行判断
		{
		case LH://插入前平衡因子为1，则插入左孩子后为2，需要平衡
			L_Balance(T);
			*taller = TRUE;//由于平衡因子超过1，增长赋值为TRUE
			break;
		case EH://插入前平衡因子为0，则插入左孩子后为1，不需要平衡
			(*T)->bf = LH;//将平衡因子赋值为1
			*taller = FALSE;//平衡因子没超过1，则赋值为FALSE
			break;
		case RH://插入前平衡因子为-1，插入左孩子后为0，不需要平衡
			(*T)->bf = EH;
			*taller = FALSE;//平衡因子没有超过1，赋值为FALSE
			break;
		}
	}
}
  1. 插入前为1，插入后为2，这时打破平衡需要进行平衡调整。
case LH://插入前平衡因子为1，则插入左孩子后为2，需要平衡
	L_Balance(T);
	*taller = TRUE;//由于平衡因子超过1，增长赋值为TRUE
	break;
  1. 插入前为0，插入后为1，不需要平衡
case EH://插入前平衡因子为0，则插入左孩子后为1，不需要平衡
	(*T)->bf = LH;//将平衡因子赋值为1
	*taller = FALSE;//平衡因子没超过1，则赋值为FALSE
	break;
  1. 插入前为-1，插入后为0，不需要调整
case RH://插入前平衡因子为-1，插入左孩子后为0，不需要平衡
	(*T)->bf = EH;
	*taller = FALSE;//平衡因子没有超过1，赋值为FALSE
	break;

2.1如何实现左平衡（L_Balance）

在实现左平衡函数，我们就得直到根节点和根的左孩子的平衡因子，根据平衡因子完成左旋和右旋来完成左平衡假设L = (*T)->lchild,用L来代表T的左孩子。这时我们要判断L的平衡因子选择合适的旋转实现平衡

//左平衡
int L_Balance(BiTree* T)
{
	BiTree L, Lr;
	L = (*T)->lchild;//将T的左孩子给L
	switch (L->bf)//根据L->bf的值判断
	{
		case LH://左高 插入到L的左孩子上，只需要进行右旋
			R_Rotate(T);//进行右旋
			L->bf = (*T)->bf = EH;//将平衡因子赋值为0
			break;
		case RH://右高，插入到L的右孩子上，需要左旋一次，右旋一次
			Lr = L->rchild;//将Lr的右孩子给Lr
			switch (Lr->bf)//根据Lr的平衡因子判断
			{
				case LH://左高，插入到Lr的左孩子上
					L->bf = EH;
					(*T)->bf = RH;
					break;
				case EH://平衡因子等高
					L->bf = (*T)->bf = EH;
					break;
				case RH://右高，插入到Lr的右孩子上
					L->bf = LH;
					(*T)->bf = EH;
					break;
			}
			Lr->bf = EH;//将Lr的平衡因子赋值为0
			L_Rotate(&(*T)->lchild);//左旋
			R_Rotate(T);//右旋
	}
	return OK;
}

1.假设插入到L的左子树上，只需要右旋转实现平衡

case LH://左高 插入到L的左孩子上，只需要进行右旋
	R_Rotate(T);//进行右旋
	L->bf = (*T)->bf = EH;//将平衡因子赋值为0
	break;
  1. 假设插入到L的右子树上，需要一次左旋转和一次右旋转平衡
case RH://右高，插入到L的右孩子上，需要左旋一次，右旋一次
	Lr = L->rchild;//将Lr的右孩子给Lr
	switch (Lr->bf)//根据Lr的平衡因子判断
	{
		case LH://左高，插入到Lr的左孩子上
			L->bf = EH;
			(*T)->bf = RH;
			break;
		case EH://平衡因子等高
			L->bf = (*T)->bf = EH;
			break;
		case RH://右高，插入到Lr的右孩子上
			L->bf = LH;
			(*T)->bf = EH;
			break;
	}
	Lr->bf = EH;//将Lr的平衡因子赋值为0
	L_Rotate(&(*T)->lchild);//左旋
	R_Rotate(T);//右旋

平衡因子的调整需要对旋转的情况了解，并知道平衡因子使如何改变，这里不说明平衡因子的变化。

三、平衡二叉树

这样就可以将根据左孩子进行调整，还有根据右孩子调整，右孩子调整和左孩子调整类似，这里就不再累述了。最后看看平衡二叉树的完整代码。

#define MAXSIZE 20 //定义查询数组的长度
#define FALSE 0 
#define TRUE 1
#define OK 1
#define ERROR 0
#define LH +1  //左高
#define EH 0   //等高
#define RH -1  //右高
#include <iostream>
#include <stdlib.h>
using namespace std;
//平衡二叉树
//平衡二叉树结构体
typedef struct BinaryTree
{
	int data;//存放数据
	int bf;//存放平衡因子
	struct BinaryTree* lchild, * rchild;//创建左右孩子域
}BinaryTree,*BiTree;
//进行右旋
int R_Rotate(BiTree* T)
{
	BiTree R = (*T)->lchild;//将T的右孩子给R
	(*T)->lchild = R->rchild;//R的右孩子给T的左孩子
	R->rchild = *T;//将T给R的右孩子
	*T = R;//更新结点
	return OK;
}
//进行左旋
int L_Rotate(BiTree* T)
{
	BiTree L = (*T)->rchild;//将T的右孩子给L
	(*T)->rchild = L->lchild;//将L的左孩子给T的右孩子
	L->lchild = *T;//将T给L的左孩子
	*T = L;//更新结点
	return OK;
}
//左平衡
int L_Balance(BiTree* T)
{
	BiTree L, Lr;
	L = (*T)->lchild;//将T的左孩子给L
	switch (L->bf)//根据L->bf的值判断
	{
		case LH://左高 插入到L的左孩子上，只需要进行右旋
			R_Rotate(T);//进行右旋
			L->bf = (*T)->bf = EH;//将平衡因子赋值为0
			break;
		case RH://右高，插入到L的右孩子上，需要左旋一次，右旋一次
			Lr = L->rchild;//将Lr的右孩子给Lr
			switch (Lr->bf)//根据Lr的平衡因子判断
			{
				case LH://左高，插入到Lr的左孩子上
					L->bf = EH;
					(*T)->bf = RH;
					break;
				case EH://平衡因子等高
					L->bf = (*T)->bf = EH;
					break;
				case RH://右高，插入到Lr的右孩子上
					L->bf = LH;
					(*T)->bf = EH;
					break;
			}
			Lr->bf = EH;//将Lr的平衡因子赋值为0
			L_Rotate(&(*T)->lchild);//左旋
			R_Rotate(T);//右旋
	}
	return OK;
}
//进行右平衡
int R_Balance(BiTree* T)
{
	BiTree R, Rl;
	R = (*T)->rchild;
	switch (R->bf)
	{
		case LH://左高，插入R的左孩子，需要一次左旋转和一次右旋转
			Rl = R->lchild;
			switch (Rl->bf)
			{
				case LH://左高，插入Rl的左子树
					R->bf = RH;
					(*T)->bf = EH;
					break;
				case EH://等高
					R->bf = (*T)->bf = EH;
					break;
				case RH://右高，插入Rl的右子树
					R->bf = EH;
					(*T)->bf = LH;
					break;
			}
			Rl->bf = EH;
			R_Rotate(&(*T)->rchild);
			L_Rotate(T);
			break;
		case RH://右高，插入R的右孩子，需要一次左旋
			L_Rotate(T);
			R->bf = (*T)->bf = EH;
			break;
	}
	return OK;
}
//平衡二叉树的插入
int InsertAVL(BiTree* T, int e, int* taller)
{
	if (!*T)//判断二叉树是否为空，空则创建结点，不为空则进行判断是否为e值
	{
		*T = (BiTree)malloc(sizeof(BinaryTree));
		(*T)->bf = EH;//将平衡因子初始化为0
		(*T)->lchild = (*T)->rchild = NULL;//初始化二叉树结点的左右孩子为NULL
		(*T)->data = e;//将数据存储在结点
		*taller = TRUE;//将taller赋值为增高
	}
	else//如果判断二叉树的结点不为空，则进行以下插入操作
	{
		if (e == (*T)->data)
		{
			*taller = FALSE;//将taller赋值为不增长
			return FALSE;
		}
		if (e < (*T)->data)//判断e值和根节点的数据大小，小就进入左孩子插入
		{
			if (!InsertAVL(&(*T)->lchild, e, taller))//判断是否已经插入，已经插入则返回
			{
				return FALSE;
			}
			if (*taller)
			{
				switch ((*T)->bf)//根据平衡因子进行判断
				{
				case LH://插入前平衡因子为1，则插入左孩子后为2，需要平衡
					L_Balance(T);
					*taller = TRUE;//由于平衡因子超过1，增长赋值为TRUE
					break;
				case EH://插入前平衡因子为0，则插入左孩子后为1，不需要平衡
					(*T)->bf = LH;//将平衡因子赋值为1
					*taller = FALSE;//平衡因子没超过1，则赋值为FALSE
					break;
				case RH://插入前平衡因子为-1，插入左孩子后为0，不需要平衡
					(*T)->bf = EH;
					*taller = FALSE;//平衡因子没有超过1，赋值为FALSE
					break;
				}
			}
		}
		else//如果e>(*T)->data
		{
			if (!InsertAVL(&(*T)->rchild, e, taller))//判断是否已经插入
			{
				return FALSE;
			}
			if (*taller)
			{
				switch ((*T)->bf)//判断平衡因子
				{
				case LH://插入前为1，插入右孩子后为0，不需平衡
					(*T)->bf = EH;
					*taller = FALSE;
					break;
				case EH://插入前为0，插入右孩子后为-1，不需平衡
					(*T)->bf = RH;
					*taller = FALSE;
					break;
				case RH://插入前为-1，插入后右孩子为-2，需要平衡
					R_Balance(T);//进行有平衡
					*taller = TRUE;
					break;
				}
			}

		}
	}
	return OK;
}
int showTree(BiTree T)
{
	if (!T)
		return OK;
	else
	{
		showTree(T->lchild);
		printf("%d ", T->data);
		showTree(T->rchild);
	}
	return OK;
}
int main()
{
	BiTree T;
	T = NULL;//初始化二叉树
	int i;
	int arr[MAXSIZE] = { 5,6,8,4,2,1,9,3,7,10,15,16,18,14,12,11,19,13,17,20 };//创建待插入平衡二叉树
	int taller = FALSE;//记录二叉树高度是否变化，高度增高就为TRUE，高度减小就为FALSE
	for (i = 0; i < MAXSIZE; i++)
	{
		InsertAVL(&T,arr[i],&taller);
	}
	showTree(T);
	return 0;
}

总结

平衡二叉树，解决了二叉排序树因有序数据导致效率下降的问题。


http://www.kler.cn/news/340308.html

相关文章：

  • microsoft edge浏览器卡死问题
  • python基础语法全解（两万字讲解，建议收藏）
  • cudnn8编译caffe过程（保姆级图文全过程，涵盖各种报错及解决办法）
  • Python使用技巧：注释和输出
  • 简述何为多态
  • 【MAUI】【Bug】UserDialogs.Instance.ShowLoading在ViewModel失效？
  • 揭秘开发者的效率倍增器：编程工具的选择与应用
  • 聚观早报 | 苹果重磅更新；OpenAI推出ChatGPT Canvas
  • 网站优化门槛低了还是高了？
  • 二层网络和三层网络的理解与区别（包含通俗理解和归纳总结）
  • Pulsar消息服务之Java工具类
  • 案例：问题处理与原因分析报告的模板
  • InnoDB 事务模型
  • Windows下的python安装教程_2024年10月最新最详细的安装指南
  • 高并发 - 1.进程和线程
  • 【Kubernetes】常见面试题汇总（五十七）
  • 【命令操作】linux上watch命令详解 _ 统信 _ 麒麟 _ 方德
  • dfs +剪枝sudoku———poj2676
  • QT：计算点到线段的垂线段的距离
  • 网络安全体系与网络安全模型