AVL树（平衡树）的理解与代码实现与讲解（尽可能写清楚）

2024-02-22 08:27:16

AVL树的原理

数据结构|二叉排序树的构造、查找、删除
AVL树在结构上十分严格
1.二叉树满足左结点小于根结点，根结点小于右结点
也要得知左子树上每一个值都小于根结点，根结点大于柚子树每一个结点！
**2.每一个结点的左子树与柚子树的高度差最多为1 **

高度

A图（平衡树）

在上面这颗树中 4结点的高度为1；20结点的高度也为1；9结点高度为2。
B图（仔细看不是平衡树）

高度从最远子树开始算起，存在就是高度为1.
**平衡因子 Balance Factor **
平衡因子bf是用来判断一个结点，左右子树高度差的
如A图中9结点：左右子树高度均为1，所以二者高度差为0，那么9结点的平衡因子也为0
B图8结点：左子树高度为2，柚子树高度为0 （不存在）所以bf为2
B图4结点：左子树高度为1，柚子树高度为3，bf为-2

之前定义了bf（高度差=绝对值）至多为1，那么说明这个不平衡需要将其调整，看完这篇你就懂如何调整了

平衡二叉树如何实现

我们看图一步一步来！
1.先创建一颗树的第一个结点

2.插入一个数 4
4比9小，是左子树

4的高度为1,9的高度为2，且平衡因子为0和1，平衡树。
3.插入一个结点3

9的左子树高度为2，柚子树高度为0，所以平衡因子（左高-右高）为2。
**打破了平衡，**将其归纳为左左LL型，需要进行平衡调整！
思路：降低高度，保持平衡
对于LL型，将最高的降下来，将中间大小的结点作为根结点
可理解为将最高结点进行右旋转到最低处。

（如果4有柚子树，那么分配给9作为它的左子树）
4.插入一个结点13

4的平衡因子为-1；9的平衡因子为-1；所以没有打破平衡
5.插入一个结点13

4的平衡因子为-2；9的平衡因子为-2；所以打破平衡。

调整思路： 寻找离地面最近的平衡因子为-2的结点。并以此寻找3个结点的子树
所以此处调整9 13 15
RR 型，左旋将最小值的结点降下来，中间大小结点作为根结点。取代那个降下来的结点。

5.插入一个结点8

4结点的平衡因子为-2，打破了平衡；
然后寻找一颗最近的子树（离地面），且与插入元素一条路。可见是4-13-9

这是左右型LR
这如何选择呢？遵循一个规律从下面的开始，先左子树进行右旋也就是
9-13进行右旋，

此时新的失衡树变为4-9-13了而无需再追着8了因为8已经被调整了，但是因为上面的4还未调整，所以此时第二次遵循调整上半部分，柚子树左旋

这里是我看网课看到的借鉴一下，总结了一下：

对于LR型和RL型来说，把ABC是哪个元素中，把中间那个大小的放在根结点位置，再把最小的放在左结点，最大的放在右结点上。

对于LR 或者RL型，寻找根平衡因子为2或-2的根节点，然以此寻找最近的子树三个结点（也就是里地面最近，最高的平衡因子为2或-2，且与插入元素一条线的（旋转两次，第一次寻找插入结点的那条线，第二次不用跟着那条线）），
然后将L部分右旋，R部分左旋，从下面部分开始进行。

中间大小的那个结点转变为三者的根结点，其左右子树，分别分配给其他两个结点。

AVL代码实现

这一部分比原理难多了苦笑
一定要画图加深理解，观察结点之间的变换和平衡因子的变换

咱一步一步来
先定义一下AVL树的结构
其多了一个平衡因子，在结构体定义一个int 型 bf
有人可能会说没有出现2和-2
嗯嗯嗯这点很重要
在2（bf未改，将树的结构改动就可以消除这个2）出现的时候，实际上结构出现了，但是我们及时将它调整回平衡树就行！

#define LH +1/*左边高一点*/
#define EH 0/*等高*/
#define RH -1/*右高*/

上面用来记录平衡因子

#include<iostream>
#include<malloc.h>
typedef int Status;
typedef int elementype;
#define TRUE 1
#define FALSE 0
using namespace std;
#define LH +1/*左边高一点*/
#define EH 0/*等高*/
#define RH -1/*右高*/

typedef struct AVLBTree
{
	elementype data;
	int bf;//平衡因子
	struct AVLBTree *lchild, *rchild;
}*BTree, BNode;

代码的主体部分，构思一下肯定会出现三连号的左旋和右旋
那么先实现他！

//右旋
void R_Rotate(BTree &tree)//从失衡结点开始走
{
	BTree L = new AVLBTree;//创建一个中间结点

	L = tree->lchild;
	tree->lchild = L->rchild;//这一步是使得中间元素的右子树  为最大元素的左子树   
	L ->rchild = tree;//这里是从二者之间的替换
	tree = L;
}

//右旋
void L_Rotate(BTree &tree)
{
	BTree R = new AVLBTree;
	R = tree->rchild;
	tree->rchild = R->lchild;
	R ->lchild = tree;
	tree = R;
}

上面这部分相信很好理解
下面从创建二叉树开始走

这里分为三大部分
1.创建一个结点（树未被创建时，最低端结点未被创立时）
2.插入的元素，从根结点开始比较大小，使用递归寻找其位置
3.当新的元素插入成功后，根据左插入和右插入，修改平衡因子

（三点一线，遵循最高的）最高的那个对于插入左子树的元素x时，
如果x的根结点原本左高一个，那么此时又插入一个就会生成bf为2的结构，就要进行左平衡处理，以免失衡；

如果原本右高，那么左插之后平衡，无需处理

如果原本平衡，那么x的根结点bf改为左高

插入柚子树的元素时类似

Status InSertAVL(BTree &tree, int x, Status *taller)
{
	if (tree == NULL)//当树没有建立时
	{
		tree = new AVLBTree;
		tree->data = x;
		tree->bf = EH;
		tree->lchild = tree->rchild = NULL;
		*taller = TRUE;
	}
	else//树存在时，从根结点开始比较
	{
		if (x == tree->data)//这步是排除一颗树中相等的元素          
		{
			*taller = FALSE;//没有插入 说明没有长高   taller用于后续判断是否需要旋转调平衡
			return FALSE;
		}
		if (x<tree->data)//往左插  在tree结点的左侧插入 且寻找合适的位置
		{
			//用递归查找最小的那个值
			//InSertAVL 这个函数 插入成功返回真  没插入返回假
			//如果在左侧没有遇见相同的，那么将插到一个NULL的结点上  且形成新的结点，然后返回为真。
			//所以这一步，插入成功的时候不会执行
			if (!InSertAVL(tree->lchild, x, taller))//这里是一个递归  很重要！！！！思路关键
			{
				return FALSE;
			}

			//插入成功后，taller为1 （真）
			//插入成功之后修改其平衡因子，
			//平衡因子修改完之后，进行判断是否需要旋转调平衡
			if (*taller)//
			{
				switch (tree->bf)//查看这个结点的平衡因子
				{
				case LH:/*原本左高，此时又插入一个左结点  那就不可能平衡，所以要进行平衡处理*/
					LeftBalance(tree);//
					*taller = FALSE;//左平衡程序后  跳出循环
					break;
				case EH:/*原本等高*/  //现在插入一个左结点，其平衡打破
					tree->bf = LH;//使平衡因子为左高
					*taller = TRUE;//需要再次进行递归 调整 以便上面的平衡因子
					break;
				case RH:/*原本右高，现在插入左结点之后 平衡了  无需处理*/
					tree->bf = EH;
					*taller = FALSE;
					break;
				}
			}
		}
		else
		{
			if (!InSertAVL(tree->rchild, x, taller))
			{
				return FALSE;
			}
			if (*taller)
			{
				switch (tree->bf)
				{
				case LH://原本左偏，加入柚子树后平衡了
					tree->bf = EH;
					*taller = FALSE;//标记F  后续无需处理
					break;
				case EH://原本平衡 往右加入之后  所以改为-1
					tree->bf = RH;
					*taller = TRUE;//标记T  后续还要进行处理
					break;
				case RH://原本右偏，加入柚子树后 更加右偏，需要右平衡处理！！！
					RightBalance(tree);
					*taller = FALSE;//经过R处理之后  标记后续不再进行。
					break;
				}
			}
		}


	}

	return TRUE;
}

balance 这部分如何变化上面可以get到，难处在于，变化之前要将1其平衡因子给修改过来。

void LeftBalance(BTree &tree)
{
	BTree L = new AVLBTree;
	BTree Lr = new AVLBTree;
	L = tree->lchild;

	//这个时候进行左平衡有两种情况
	//1.   仅仅左插入   所以要进行一次右循环
	//2.   打破平衡时是插入了左边的右结点  生成左-右型，这个时候要进行双循环。******上左下右的  结构时，要遵循先将下面的两个结点进行左循环，再将上面两个结点进行右循环
	
	switch (L->bf)
	{
	case LH://两个连续的左子树，进行右循环即可校正
		tree->bf = L->bf = EH;
		R_Rotate(tree);
		break;
	case RH://中间元素L为-1， 一左一右，插入的是右子树，所以遵循上左下右进行解决
	{
		Lr = L->rchild;//找到右元素
		switch (Lr ->bf)//这一步  是进行平衡因子的修改，因为平衡调整，不仅是位置上的调整，还需调整其平衡因子
		{
		case LH://具体如何可以根据不同情况画图   然后可以理解
			tree->bf = RH;
			L->bf = EH;
			break;
		case EH://这种是影响 在最下面的左右型
			tree->bf = L->bf = EH;
			break;
		case RH:
			tree->bf = EH;
			L ->bf = LH;
			break;
		}
	}
		Lr->bf = EH;//修正
		L_Rotate(tree->lchild);
		R_Rotate(tree);
	}
}

void RightBalance(BTree &tree)
{
	BTree R = new AVLBTree;
	BTree Rr = new AVLBTree;
	R = tree->rchild;
	switch (R->bf)
	{
	case RH:
		tree->bf = R->bf = EH;
		L_Rotate(tree);
		break;
	case LH:
	{
		Rr = R->lchild;
		switch (Rr->bf)//
		{
		case RH:
			tree->bf = LH;
			R->bf = EH;
			break;
		case EH:
			tree->bf = R->bf = EH;
			break;
		case LH:
			tree->bf = EH;
			R->bf = RH;
			break;
		}
	}
		Rr->bf = EH;
		R_Rotate(tree->rchild);
		L_Rotate(tree);
	}
}

关于Balance这开始也不能理解其中含义，但是画了图之后，就可以理解了，平衡旋转你肯定可以理解l，这段代码还对平衡因子在旋转之前做了修改。

下面是完整代码，代码源自大话数据结构一书

#include<iostream>
#include<malloc.h>
typedef int Status;
typedef int elementype;
#define TRUE 1
#define FALSE 0
using namespace std;
#define LH +1/*左边高一点*/
#define EH 0/*等高*/
#define RH -1/*右高*/


typedef struct AVLBTree
{
	elementype data;
	int bf;//平衡因子
	struct AVLBTree *lchild, *rchild;
}*BTree, BNode;


//右旋
void R_Rotate(BTree &tree)
{
	BTree L = new AVLBTree;//创建一个中间结点

	L = tree->lchild;
	tree->lchild = L->rchild;//这一步是使得中间元素的右子树  为最大元素的左子树   
	L ->rchild = tree;//这里是从二者之间的替换
	tree = L;
}

//右旋
void L_Rotate(BTree &tree)
{
	BTree R = new AVLBTree;
	R = tree->rchild;
	tree->rchild = R->lchild;
	R ->lchild = tree;
	tree = R;
}
//判断左平衡


void LeftBalance(BTree &tree)
{
	BTree L = new AVLBTree;
	BTree Lr = new AVLBTree;
	L = tree->lchild;

	//这个时候进行左平衡有两种情况
	//1.   仅仅左插入   所以要进行一次右循环
	//2.   打破平衡时是插入了左边的右结点  生成左-右型，这个时候要进行双循环。******上左下右的  结构时，要遵循先将下面的两个结点进行左循环，再将上面两个结点进行右循环
	
	switch (L->bf)
	{
	case LH://两个连续的左子树，进行右循环即可校正
		tree->bf = L->bf = EH;
		R_Rotate(tree);
		break;
	case RH://中间元素L为-1， 一左一右，插入的是右子树，所以遵循上左下右进行解决
	{
		Lr = L->rchild;//找到右元素
		switch (Lr ->bf)//这一步  是进行平衡因子的修改，因为平衡调整，不仅是位置上的调整，还需调整其平衡因子
		{
		case LH://具体如何可以根据不同情况画图   然后可以理解
			tree->bf = RH;
			L->bf = EH;
			break;
		case EH://这种是影响 在最下面的左右型
			tree->bf = L->bf = EH;
			break;
		case RH:
			tree->bf = EH;
			L ->bf = LH;
			break;
		}
	}
		Lr->bf = EH;//修正
		L_Rotate(tree->lchild);
		R_Rotate(tree);
	}
}

void RightBalance(BTree &tree)
{
	BTree R = new AVLBTree;
	BTree Rr = new AVLBTree;
	R = tree->rchild;
	switch (R->bf)
	{
	case RH:
		tree->bf = R->bf = EH;
		L_Rotate(tree);
		break;
	case LH:
	{
		Rr = R->lchild;
		switch (Rr->bf)//
		{
		case RH:
			tree->bf = LH;
			R->bf = EH;
			break;
		case EH:
			tree->bf = R->bf = EH;
			break;
		case LH:
			tree->bf = EH;
			R->bf = RH;
			break;
		}
	}
		Rr->bf = EH;
		R_Rotate(tree->rchild);
		L_Rotate(tree);
	}
}



Status InSertAVL(BTree &tree, int x, Status *taller)
{
	if (tree == NULL)//当树没有建立时
	{
		tree = new AVLBTree;
		tree->data = x;
		tree->bf = EH;
		tree->lchild = tree->rchild = NULL;
		*taller = TRUE;
	}
	else//树存在时，从根结点开始比较
	{
		if (x == tree->data)//这步是排除一颗树中相等的元素          //所以AVL树后面要研究一下，一棵树中有相等的元素时是如何排序的
		{
			*taller = FALSE;//没有插入 说明没有长高   taller用于后续判断是否需要旋转调平衡
			return FALSE;
		}
		if (x<tree->data)//往左插  在tree结点的左侧插入 且寻找合适的位置
		{
			//用递归查找最小的那个值
			//InSertAVL 这个函数 插入成功返回真  没插入返回假
			//如果在左侧没有遇见相同的，那么将插到一个NULL的结点上  且形成新的结点，然后返回为真。
			//所以这一步，插入成功的时候不会执行
			if (!InSertAVL(tree->lchild, x, taller))//这里是一个递归  很重要！！！！思路关键
			{
				return FALSE;
			}

			//插入成功后，taller为1 （真）
			//插入成功之后修改其平衡因子，
			//平衡因子修改完之后，进行判断是否需要旋转调平衡
			if (*taller)//
			{
				switch (tree->bf)//查看这个结点的平衡因子
				{
				case LH:/*原本左高，此时又插入一个左结点  那就不可能平衡，所以要进行平衡处理*/
					LeftBalance(tree);//
					*taller = FALSE;//左平衡程序后  跳出循环
					break;
				case EH:/*原本等高*/  //现在插入一个左结点，其平衡打破
					tree->bf = LH;//使平衡因子为左高
					*taller = TRUE;//需要再次进行递归 调整 以便上面的平衡因子
					break;
				case RH:/*原本右高，现在插入左结点之后 平衡了  无需处理*/
					tree->bf = EH;
					*taller = FALSE;
					break;
				}
			}
		}
		else
		{
			if (!InSertAVL(tree->rchild, x, taller))
			{
				return FALSE;
			}
			if (*taller)
			{
				switch (tree->bf)
				{
				case LH://原本左偏，加入柚子树后平衡了
					tree->bf = EH;
					*taller = FALSE;//标记F  后续无需处理
					break;
				case EH://原本平衡 往右加入之后  所以改为-1
					tree->bf = RH;
					*taller = TRUE;//标记T  后续还要进行处理
					break;
				case RH://原本右偏，加入柚子树后 更加右偏，需要右平衡处理！！！
					RightBalance(tree);
					*taller = FALSE;//经过R处理之后  标记后续不再进行。
					break;
				}
			}
		}


	}

	return TRUE;
}


void main()
{
	BTree tree=NULL;

	int x;
	cin >> x;
	Status taller=0;
	InSertAVL(tree, x, &taller);
	
	cin >> x;
	InSertAVL(tree, x, &taller);
	cin >> x;
	InSertAVL(tree, x, &taller);
	cin >> x;
	InSertAVL(tree, x, &taller);
	cin >> x;
	InSertAVL(tree, x, &taller);
	cin >> x;
	InSertAVL(tree, x, &taller);
	cin >> x;
	InSertAVL(tree, x, &taller);
	cin >> x;
	InSertAVL(tree, x, &taller);
	cin >> x;
	InSertAVL(tree, x, &taller);
	cin >> x;
	InSertAVL(tree, x, &taller);
	system("pause");
}

码农公寓

AVL树的原理

高度

平衡二叉树如何实现

AVL代码实现

相关文章