C++进阶（七）AVL树

在这里插入图片描述


📘北尘_：个人主页

🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》
☀️走在路上，不忘来时的初心

文章目录

  • 一、AVL树的概念
  • 二、AVL树的旋转
    • 1、左单旋
    • 2、右单旋
    • 3、左右双旋
    • 4、右左双旋
  • 三、AVL树的基本实现
  • 四、AVL树的性能

一、AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
在这里插入图片描述

二、AVL树的旋转

由于插入节点后，平衡因子会发生变化，从而使绝对值大于1，所以就需要去旋转，而旋转就有4中情况。

1、左单旋

在这里插入图片描述

代码实现

void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}

		parent->_bf = subR->_bf = 0;
	}

2、右单旋

在这里插入图片描述

代码实现

void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}

		subL->_bf = parent->_bf = 0;
	}

3、左右双旋

右左双旋可以直接调用，右单旋，然后再左单旋，但需要注意的是，调用后，并没有完成，因为平衡因子还不是正确的值。
平衡因子也分为三种情况，以下图为例：
当60的平衡因子为0时，平衡因子皆为0，
当60的平衡因子为1时，60的平衡因子为0，30的平衡因子为-1，90的平衡因子为0
当60的平衡因子为-1时，60的平衡因子为0，30的平衡因子为0，90的平衡因子为1
在这里插入图片描述

代码实现

void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);
		if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

4、右左双旋

右左双旋可以直接调用，右单旋，然后再左单旋，但需要注意的是，调用后，并没有完成，因为平衡因子还不是正确的值。
平衡因子也分为三种情况，以下图为例：
当60的平衡因子为0时，平衡因子皆为0，
当60的平衡因子为1时，60的平衡因子为0，30的平衡因子为-1，90的平衡因子为0
当60的平衡因子为-1时，60的平衡因子为0，30的平衡因子为0，90的平衡因子为1
在这里插入图片描述

代码实现

void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)
		{
			// subRL自己就是新增
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			// subRL的左子树新增
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			// subRL的右子树新增
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

三、AVL树的基本实现

AVL树的节点实现

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	int _bf; // balance factor

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};

AVL树的插入实现

class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}

				// 1、旋转让这颗子树平衡了
				// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
				break;
			}
			else
			{
				assert(false);
			}
		}

		return true;
	}
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);
		if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)
		{
			// subRL自己就是新增
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			// subRL的左子树新增
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			// subRL的右子树新增
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}

		parent->_bf = subR->_bf = 0;
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}

		subL->_bf = parent->_bf = 0;
	}

private:
	Node* _root=nullptr;
};

四、AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 l o g 2 ( N ) log_2 (N) log2​(N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/354255.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

跨平台框架Flutter工作原理初探

跨平台框架Flutter工作原理初探

前言 Flutter是开发跨平台应用的框架&#xff0c;支持将应用打包到几乎市面所有平台&#xff0c;本文较浅层次探究flutter框架的工作原理 参考来源为flutter中文社区官方文档 Flutter 开发文档 - Flutter 中文文档 - Flutter 中文开发者网站 - Flutter flutter的布局 组合…
阅读更多...
防御保护--第一次实验

防御保护--第一次实验

目录 一&#xff0c;vlan的划分及在防火墙上创建单臂路由 二&#xff0c;创建安全区域 三&#xff0c;配置安全策略 四&#xff0c;配置认证策略 五&#xff0c;配置NAT策略 1.将内网中各个接口能够ping通自己的网关 2..生产区在工作时间内可以访问服务器区&#xff0c;仅…
阅读更多...
vivado 2018.3 烧写固化FPGA verilog代码以及出现的问题解决

vivado 2018.3 烧写固化FPGA verilog代码以及出现的问题解决

vivado一般是与SDK同时使用的，像zynq系列，通过SDK烧写固化代码很方便，但是有的时候比如本人目前使用的是XC7K325T FPGA进行的开发，不会用到SDK软件，所以烧写固化代码想通过vivado直接操作。 1、按照网上百度的方法进行设置，如下 遇到的第一个问题就是在vivado2018.3的fl…
阅读更多...
Blender教程（基础）-物体添加-03

Blender教程（基础）-物体添加-03

1、打开的界面如下图会存在3个物体、英文状态下按键盘字母A全选、然后按键盘delete删除。 删除后一片空白 2、新增物体 方式1&#xff1a;在英文状态下按键盘shiftA组合键弹出如下添加物体弹窗 方式2&#xff1a;在菜单下找到添加点击弹出添加选项 3、举例新增物体 采用上述…
阅读更多...
【数字通信】数字带通传输

【数字通信】数字带通传输

数字调制和数字带通传输系统 数字调制解调 数字调制 用数字基带信号控制载波&#xff0c;把数字基带信号变换为数字带通信号的过程 目的&#xff1a;数字基带信号含大量低频分量&#xff0c;无法通过具有带通特性的信道传输。需对数字基带信号进行数字调制使信号与信道的特…
阅读更多...
log4j2 java api 入门介绍

log4j2 java api 入门介绍

概述 Log4j 2 API 提供了应用程序应该编码的接口&#xff0c;并提供了实现者创建日志实现所需的适配器组件。 虽然 Log4j 2 在 API 和实现之间被分解&#xff0c;但这样做的主要目的不是允许多个实现&#xff0c;尽管这当然是可能的&#xff0c;而是明确定义在“正常”应用程…
阅读更多...
YOLOv8融合改进 更换检测头同时改进C2f模块

YOLOv8融合改进 更换检测头同时改进C2f模块

一、Detect_DyHead检测头和C2f-EMSC，C2f-EMSCP模块 详细介绍和代码在往期的博客里： Detect_DyHead： （YOLOv8改进检测头Detect为Detect_Dyhead-CSDN博客） C2f-EMSC和C2f-EMSCP： （YOLOv8改进之多尺度转换模块C2f-EMSC和C2f-EMSCP-CSDN博客） 二、算法实现 1、将检测…
阅读更多...
github连不上

github连不上

github连不上 错误提示解决方案 错误提示 fatal: unable to access ‘https://github.com/Ada-design/qianduan.git/’: Failed to connect to github.com port 443 after 21073 ms: Couldn’t connect to server 解决方案 下载steam https://steampp.net/ 安装成功之后&am…
阅读更多...
Linux系统明明还有足够的物理内存，调用fork却返回ENOMEM

Linux系统明明还有足够的物理内存，调用fork却返回ENOMEM

使用systemtab hook fork&#xff0c;定位到报错调用路径SYSCALL_DEFINE0(fork)-》kernel_clone-》copy_process-》copy_mm-》dup_mm-》dup_mmap-》security_vm_enough_memory_mm-》__vm_enough_memory __vm_enough_memory返回了 -ENOMEM。其源码如下&#xff1a; 从代码可知f…
阅读更多...
算法38：子数组的最小值之和（力扣907题）----单调栈

算法38：子数组的最小值之和（力扣907题）----单调栈

题目&#xff1a; 给定一个整数数组 arr&#xff0c;找到 min(b) 的总和&#xff0c;其中 b 的范围为 arr 的每个&#xff08;连续&#xff09;子数组。 示例 1&#xff1a; 输入&#xff1a;arr [3,1,2,4] 输出&#xff1a;17 解释&#xff1a; 子数组为 [3]&#xff0c;[…
阅读更多...
Java集合总览

Java集合总览

1.总览 Java中的集合分List、Set、Queue、Map 4种类型。 List&#xff1a;大多数实现元素可以为null&#xff0c;可重复&#xff0c;底层是数组或链表的结构&#xff0c;支持动态扩容 Set&#xff1a;大多数实现元素可以为null但只能是1个&#xff0c;不能重复&#xff0c; …
阅读更多...
MySQL 聚集与非聚集索引

MySQL 聚集与非聚集索引

文章目录 1.聚集索引1.1 介绍1.2 优点1.3 缺点 2.非聚集索引3.区别参考文献 MySQL 中&#xff0c;根据索引树叶结点存放数据行还是数据行的地址&#xff0c;可以将索引分为两类&#xff1a; 存放数据行&#xff1a;聚集索引存放数据行地址&#xff1a;非聚集索引 InnoDB 使用聚…
阅读更多...
Linux学习之文件系统与动静态库

Linux学习之文件系统与动静态库

目录 一&#xff0c;文件的管理 什么是磁盘&#xff1f; 磁盘的逻辑抽象结构 格式化 inode 挂载 软硬链接 二&#xff0c;动静态库 什么是动静态库&#xff1f; 1.站在库的制作者角度 静态库&#xff1a; 制作一个静态库 2.站在静态库使用者的角度 动态库 作为制…
阅读更多...
windows安装PostgreSQL后进行远程连接，发生SSL错误

windows安装PostgreSQL后进行远程连接，发生SSL错误

1. 报错情况 SSL 关闭 的 pg_hba.conf 记录 (pgjdbc: autodetected server-encoding to be GB2312, if the message is not readable, please check database logs and/or host, port, dbname, user, password, pg_hba.conf) 或是乱码提示&#xff0c;提示中有SSL、 pg_hba.con…
阅读更多...
C语言KR圣经笔记 5.12 复杂声明

C语言KR圣经笔记 5.12 复杂声明

5.12 复杂声明 C 语言有时会因为声明的语法而受到谴责&#xff0c;特别是涉及函数指针的声明语法。语法试图使声明和使用一致&#xff1b;在简单的情况下它的效果不错&#xff0c;但在更复杂的情况下会让人困惑&#xff0c;因为声明不能从左往右读&#xff0c;而且括号被过度使…
阅读更多...
RabbitMQ快速上手

RabbitMQ快速上手

首先他的需求实在什么地方。我美哟明显的感受到。 它给我的最大感受就是脱裤子放屁——多此一举&#xff0c;的感觉。 他将信息发送给服务端中间件。在由MQ服务器发送消息。 服务器会监听消息。 但是它不仅仅局限于削峰填谷和稳定发送信息的功能&#xff0c;它还有其他重要…
阅读更多...
Nacos(先解释专属名词，然后大白话讲解+安装配置教程+代码实例 信我，看了必会！！点进来吧各位大佬们)

Nacos(先解释专属名词，然后大白话讲解+安装配置教程+代码实例 信我，看了必会！！点进来吧各位大佬们)

Nacos 先来一个注意&#xff1a;以下涉及到配置和项目的创建&#xff0c;我的jdk是jdk17&#xff0c;idea是2023.2.4&#xff0c;并且是社区版的idea 1.什么是Nacos Nacos是Dyamic Naming and Configuration Service的首字母简称&#xff0c;一个更易于构建云原生应用的动态…
阅读更多...
重生奇迹MU平民玩家推荐的职业

重生奇迹MU平民玩家推荐的职业

女魔法师 女魔法师是一个非常适合平民玩家的职业选择。她拥有着强大的魔法攻击能力&#xff0c;可以轻松地击败敌人。而且女魔法师的装备价格相对较低&#xff0c;适合玩家们的经济实力。 精灵射手 精灵射手是一个非常灵活的职业选择。他们可以远程攻击&#xff0c;可以在战…
阅读更多...
数据结构之生成树及最小生成树

数据结构之生成树及最小生成树

数据结构之生成树及最小生成树 1、生成树概念2、最小生成树 数据结构是程序设计的重要基础&#xff0c;它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发&#xff0c;分析和研究计算机加工的数据的特性&#xff0c;以便为应用所…
阅读更多...
centos7 挂载windows共享文件夹报错提示写保护

centos7 挂载windows共享文件夹报错提示写保护

centos7挂载windows共享时&#xff0c;提示被共享的位置写保护&#xff0c;只能以只读方式挂载&#xff0c;紧接着就是以只读方式挂载失败 原因是组件少装了 yum install cifs-utils 安装完后&#xff0c;正常挂载使用。 下载离线安装包 下载离线包下载工具 下载离线安装包…
阅读更多...
最新文章

Copyright @ 2022~2023