• 平衡二叉树(AVL) 的认识与实现

    文章目录

    1 基本

    1.1 概念

    平衡二叉树是一棵合理的二叉排序树

    解释

    对于这么一个序列

    在这里插入图片描述

    如果按照普通的排序思路，5>4>3>2>1，会得到这么一棵树

    如果想要查询结点5，则需要比对很多次；

    而如果以3为根，则可以得到一棵较为合理的树

    这样就搜索结点5只需要3次即可

    为了实现较为合理的排序，AVL就因此诞生

    1.2 特点

    平衡二叉树有个至关重要的特点：

    左右子树高度差不超过1

    由此减少树的深度，从而减少查找次数

    1.3 构建

    • 本质上与构建二叉排序树一致
    • 在构建二叉排序树的过程中，如果发现树不符合左右子树高度差不超过1的特点，需要进行调整

    1.4 调整

    通过**失衡树的根节点root和导致树失衡的结点node**来调整新的树

    而根据2个方向来选择调整方法

    • 导致树失衡的结点node在root的哪一侧
    • node在root孩子结点的哪一侧

    调整方法

    • LL：上面两个方向均在左侧
    • RR：上面两个方向均在右侧
    • RL：上面两个方向一右一左
    • LR：上面两个方向一左一右

    1.4.1 RR

    RR：

    • 取中间节点，使其父节点成为其左子树
    • 如果它有左子树，则先使其父节点成为其左子树，然后使其原有的左子树连接到现有左子树的右子树上
    //	代码的实现则是反过来，先连接原有左子树到现有左子树的右子树，再连接到中间节点的右子树
root 1	node/child 3
root->right_child = child->left_child;
child->left_child = root;

    • 1
    • 2
    • 3
    • 4
    1.4.1.1 示例

    对于开头提到的序列

    在这里插入图片描述

    进行正常排序

    可见，root是1， node是3

    • node在root的右侧:R
    • node在root孩子节点的右侧:R

    两个都是R

    进行调整

    在这里插入图片描述

    如果2原先有左子树，调整：

    在这里插入图片描述

    1.4.1.2 多棵树不平衡

    注意：如果遇到多棵树不平衡，则调整最小树

    将上面的序列继续排序

    在这里插入图片描述

    排序

    在这里插入图片描述

    如图，有两棵树失衡，一棵树最大的树12345，一颗是345，我们只用调整最小的345即可

    这棵也是RR，直接调整

    在这里插入图片描述

    1.4.2 LL

    和RR完全相反

    LL：

    • 取中间节点，使其父节点成为其右子树
    • 如果它有右子树，则先使其父节点成为其右子树，然后使其原有的右子树连接到现有右子树的左子树上
    //	代码的实现则是反过来，先连接原有左子树到现有左子树的右子树，再连接到中间节点的右子树
root 5	node/child 3
root->left_child = child->right_child;
child->right_child = root;

    • 1
    • 2
    • 3
    • 4
    1.4.2.1 示例

    再来一组数据

    在这里插入图片描述

    正常排序

    进行LL排序

    在这里插入图片描述

    继续

    继续排序最小树

    在这里插入图片描述

    1.4.3 LR

    LR：

    • 取最后一个节点，使其作为父节点
    • 将其原有的父节点作为它的左子树，将它原有的父节点的父节点作为它的右子树
    • 如果它有左子树，则先使其父节点成为其左子树，然后使其原有的左子树连接到现有左子树的右子树上
    • 如果它有右子树，则先将它原有的父节点的父节点作为它的右子树，然后将其原有的右子树连接到它原有的父节点的父节点的左子树上

    总结

    • 先RR
    • 后LL
    //	代码的实现则是反过来
root 7	node/child 6
root->left_child = child->right_child;	child-right_>child = root;		//有右子树
root->left_child->right_child = child->left_child;	root->left_child->right_child = child->left_child 	//有左子树
child->right_child = root;
root = child;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    1.4.3.1 示例

    在这里插入图片描述

    进行正常排序

    在这里插入图片描述

    两棵树失衡

    在这里插入图片描述

    调整最下面的树

    可见，root是7， node是6

    • node在root的左侧:L
    • node在root孩子节点的右侧:R

    即LR

    进行调整

    在这里插入图片描述

    1.4.4 RL

    RL：

    • 取最后一个节点，使其作为父节点
    • 将其原有的父节点作为它的右子树，将它原有的父节点的父节点作为它的左子树
    • 如果它有左子树，则先将它原有的父节点的父节点作为它的左子树，然后将其原有的左子树连接到它原有的父节点的父节点的右子树上
    • 如果它有右子树，则先使其父节点成为其右子树，然后使其原有的右子树连接到现有右子树的左子树上，

    总结

    • 先LL
    • 后RR
    //	代码的实现则是反过来
root 1	node/child 6
root->right_child->left_child = child->right_child;	child-right_>child = root->right_child;		//有右子树
root->right_child = child->left_child;	child->left_child = root;		//有左子树
child->left_child = root;
root = child;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    1.4.4.1 示例

    在这里插入图片描述

    进行正常排序

    在这里插入图片描述

    已经失衡，进行调整

    可见，root是1， node是6

    • node在root的左侧:R
    • node在root孩子节点的右侧:L

    即RL

    进行调整

    在这里插入图片描述

    然后继续插入7/10

    在这里插入图片描述

    1.5 实现

    • 建立平衡二叉树的过程就是建立一棵二叉搜索树的过程
    • 而在建立过程中我们需要对树进行调整，调整需要用到树的高度，因此我们节点的结构体中需要添加一个height字段来标记当前树的高度

    1.5.1 示例

    只实现二叉排序树，还未使用字段height

    #include
using namespace std;
//节点
typedef struct TreeNode {
	int data;
	int height;
	struct TreeNode* left_child;
	struct TreeNode* right_child;
}TreeNode;
//进行二叉排序树的构建
void AVLInsert(TreeNode** T, int data)
{
	if (*T == NULL)	//没有节点
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));	//创建一个
		(*T)->data = data;
		(*T)->height = 0;	//高度设为0
		(*T)->left_child = NULL;
		(*T)->right_child = NULL;
	}
	else if (data < (*T)->data)
	{
		AVLInsert(&(*T)->left_child, data);	//比根节点的data大，插入在左子树
	}
	else if (data > (*T)->data)
	{
		AVLInsert(&(*T)->right_child, data);
	}
}
//前序遍历打印树
void PreOrder(TreeNode* T)
{
	if (T)
	{
		cout << T->data;
		PreOrder(T->left_child);	//递归调用左子树
		PreOrder(T->right_child);	//递归调用右子树
	}
}
int main()
{
	TreeNode* T = NULL;
	int nums[5] = { 1,2,3,4,5 };
	for (int i = 0; i < 5; i++)
	{	//构建树
		AVLInsert(&T, nums[i]);
	}
	PreOrder(T);
	cout << endl;
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    在这里插入图片描述

    1.5.2 完善

    • 获取高度（其实我们结构体中有定义height字段可以直接调用，但为了易读我这里创建一个函数得到height）
    //获取高度高度
int GetHeight(TreeNode* node)
{
	return node ? node->height : 0;	//节点不为空，则返回节点的height值，否则返回0
}

    • 1
    • 2
    • 3
    • 4
    • 5

    • 获取最大高度

      //获取最大高度
int GetMax(int a, int b)
{
	return a > b ? a : b;
}

      • 1
      • 2
      • 3
      • 4
      • 5

    • 实现RR和LL

    //RR旋转
void rrRotation(TreeNode* root, TreeNode** node)
{
	TreeNode* tmp = root->right_child;
	root->right_child = tmp->left_child;	//原有左子树连接到现有左子树的右子树上
	tmp->left_child = root;					//使其父节点成为其现有的左子树

	root->height = GetMax(GetHeight(root->left_child), GetHeight(root->right_child)) + 1;
	tmp->height = GetMax(GetHeight(tmp->left_child), GetHeight(tmp->right_child)) + 1;
	*node = tmp;
}

//LL旋转
void llRotation(TreeNode* root, TreeNode** node)
{
	TreeNode* tmp = root->left_child;
	root->left_child = tmp->right_child;	//原有右子树连接到现有右子树的左子树上
	tmp->right_child = root;				//使其父节点成为其现有的右子树

	root->height = GetMax(GetHeight(root->left_child), GetHeight(root->right_child)) + 1;
	tmp->height = GetMax(GetHeight(tmp->left_child), GetHeight(tmp->right_child)) + 1;
	*node = tmp;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    • 实现LR和RL，就是调用LL和RR

      //LR
void lrTotation(TreeNode** T)
{
	rrRotation((*T)->left_child, &(*T)->left_child);
	llRotation(*T, T);
}

//RL
void rlTotation(TreeNode** T)
{
	llRotation((*T)->right_child, &(*T)->right_child);
	rrRotation(*T, T);
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13

    • 最后完善构建二叉树

      //进行二叉排序树的构建
void AVLInsert(TreeNode** T, int data)
{
	if (*T == NULL)	//没有节点
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));	//创建一个
		(*T)->data = data;
		(*T)->height = 0;	//高度设为0
		(*T)->left_child = NULL;
		(*T)->right_child = NULL;
	}
	else if (data < (*T)->data)		//比根节点的data小，插入在左子树	:L
	{
		AVLInsert(&(*T)->left_child, data);
		//获取当前节点左右子树的高度
		int left_height = GetHeight((*T)->left_child);
		int right_height = GetHeight((*T)->right_child);

		//判断高度差
		if (left_height - right_height > 1)
		{
			if (data < (*T)->left_child->data)//小于父节点左子树的值，说明在左边	:L
			{
				//LL
				llRotation(*T, T);
			}
			else// : R
			{
				//LR
				lrTotation(T);
			}
		}
	}
	else if (data > (*T)->data)//比根节点的data大，插入在右子树			:R
	{
		AVLInsert(&(*T)->right_child, data);						
		//获取当前节点左右子树的高度
		int left_height = GetHeight((*T)->left_child);
		int right_height = GetHeight((*T)->right_child);

		//判断高度差
		if (right_height - left_height > 1)
		{
			if (data > (*T)->right_child->data)	//大于父节点右子树的值，说明在右边	:R
			{
					//RR
				rrRotation(*T, T);
			}
			else//:L
			{
					//RL
				rlTotation(T);
			}
		}
	}
	(*T)->height = GetMax(GetHeight((*T)->left_child), GetHeight((*T)->right_child)) + 1;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
      • 29
      • 30
      • 31
      • 32
      • 33
      • 34
      • 35
      • 36
      • 37
      • 38
      • 39
      • 40
      • 41
      • 42
      • 43
      • 44
      • 45
      • 46
      • 47
      • 48
      • 49
      • 50
      • 51
      • 52
      • 53
      • 54
      • 55
      • 56
      • 57

    • main

      int main()
{
	TreeNode* T = NULL;
	int nums1[5] = { 1,2,3,4,5 };
	int nums2[5] = { 5,4,3,2,1 };
	int nums3[5] = { 8,7,9,5,6 };
	int nums4[5] = { 1,8,6,7,10 };

	for (int i = 0; i < 5; i++)
	{	//构建树
		AVLInsert(&T, nums4[i]);
	}
	PreOrder(T);
	cout << endl;
	return 0;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16

      在这里插入图片描述

  • 相关阅读:
    哈工大2024春季计算机系统大作业（水平有限，仅供参考）
    【Python爬虫实战】 不生产小说，只做网站的搬运工，太牛逼了~（附源码）
    XPS测试加测轨道-科学指南针
    torch.roll
    国民技术N32G45x双ADC规则同步模式配置
    Java之多线程的综合练习二
    企业级自定义表单引擎解决方案（十六）--Excel导入导出
    90---Python 直角坐标系下绘制椭圆形
    分组子集对齐后再做差集
    SPRINGBOOT04_配置文件、三种读取配置文件方式
  • 原文地址：https://blog.csdn.net/qq_24472227/article/details/133797610