数据结构：AVL树

目录

1、AVL树的概念

2、二叉搜索树的功能与实现

1、AVL树节点定义

2、AVL树的插入

3、AVL树的旋转操作

1、左旋

2、右旋

3、左右旋

 4、右左旋

 3、AVL树完整代码实现

1、AVL树的概念

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

一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是 AVL 树
左右子树高度之差 ( 简称平衡因子 ) 的绝对值不超过 1(-1/0/1)
平衡因子：右子树高度减去左子树高度
如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在
O(log2 n) ，搜索时间复杂度 O(log2 n) 。
以下是一个简单AVL树的示例：节点周围的是平衡因子。

2、二叉搜索树的功能与实现

1、AVL树节点定义

template<class K,class V>
	struct AVLTreeNode
	{
		AVLTreeNode<K, V>* _left;
		AVLTreeNode<K, V>* _right;
		AVLTreeNode<K, V>* _parent;
		int _bf; //平衡因子
		pair<K, V> _kv;
		AVLTreeNode(const pair<K, V>& kv)
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _bf(0)
			,_kv(kv)
		{

		}
	};
每个节点的平衡因子设置为0，每个节点包含左右指针，以及父节点指针，每个节点的数据用pair来实现，第一个元素为Key来比较。

2、AVL树的插入

AVL树是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看作二叉搜索树

插入过程与二叉搜索树一致，只不过要注意更新节点的平衡因子。

因为平衡因子是右子树高度减去左子树高度，所以如果在左子树添加节点，bf(平衡因子）--，在右子树添加，bf++。

parent节点的平衡因子更新有三种情况：

1、parent的平衡因子为0，说明满足AVL性质，插入成功。

2、parent的平衡因子为1或-1，说明该树的高度增加，需要向上更新。

3、parent的平衡因子为-2或2，说明该节点违反了平衡树性质，需要对其进行旋转处理。

旋转处理下面会介绍，我们先来看插入的代码实现：

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;
				}
				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 = 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)
						{
							RotateLR(parent);
						}
						else
						{
							RotateRL(parent);
						}
						break;
					}
					else
					{
						assert(false);
					}
				}
			return true;
		}

寻找插入位置与搜索二叉树一致，然后更新平衡因子 ，对于不同的违反AVL树性质需要不同的旋转操作。

3、AVL树的旋转操作

我们先来看左旋对应的情况：

1、左旋

a,b,c具有相同的高度，旋转后注意更新parent和cur的平衡因子为0； 
void RotateL(Node* parent)
		{
			Node* sub = parent->_right;
			Node* subl = sub->_left;
			parent->_right = subl;
			if (subl)
			{
				subl->_parent = parent;
			}
			sub->_left = parent;
			Node* ppnode = parent->_parent;
			parent->_parent = sub;
			if (parent == _root)
			{
				_root = sub;
				sub->_parent = nullptr;
			}
			else
			{
				if (parent == ppnode->_left)
				{
					ppnode->_left = sub;
				}
				else
				{
					ppnode->_right = sub;
				}
				sub->_parent = ppnode;
			}
			parent->_bf = 0;
			sub->_bf = 0;
		}

2、右旋

原理与左旋相似，不过是向右旋转而已 （a,b,c具有相同的高度）

void RotateR(Node* parent)
		{
			Node* sub = parent->_left;
			Node* subr = sub->_right;
			parent->_left = subr;
			if (subr)
			{
				subr->_parent = parent;
			}
			sub->_right = parent;
			Node* ppnode = parent->_parent;
			parent->_parent = sub;
			if (parent == _root)
			{
				_root = sub;
				sub->_parent = nullptr;
			}
			else
			{
				if (parent == ppnode->_left)
				{
					ppnode->_left = sub;
				}
				else
				{
					ppnode->_right = sub;
				}
				sub->_parent = parent;
			}
			parent->_bf = 0;
			sub->_bf = 0;
		}

3、左右旋

先以subl为根左旋，再以parent为根进行右旋。（a,b,c具有相同的高度）

void RotateLR(Node* parent)
		{
			Node* subl = parent->_left;
			Node* sublr = subl->_right;
			int bf = sublr->_bf;
			RotateL(subl);
			RotateR(parent);
			if (bf == -1)
			{
				sublr->_bf = 0;
				parent->_bf = 1;
				subl->_bf = 0;
			}
			else if (bf == 1)
			{
				sublr->_bf = 0;
				parent->_bf = 0;
				subl->_bf = -1;
			}
			else if (bf == 0)
			{
				subl->_bf = 0;
				parent->_bf = 0;
				sublr->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}

根据sublr的平衡因子的不同（也就是插入到了B还是C）来判断如何更新平衡因子。

 4、右左旋

原理与左右旋相似，只是换了个方向。（a,b,c具有相同的高度）

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

根据sublr的平衡因子的不同（也就是插入到了B还是C）来判断如何更新平衡因子。 

 3、AVL树完整代码实现

内部包含查找以及判断是否是AVL树的函数，以及中序遍历。

#pragma once
namespace AVLTree_test
{
	template<class K,class V>
	struct AVLTreeNode
	{
		AVLTreeNode<K, V>* _left;
		AVLTreeNode<K, V>* _right;
		AVLTreeNode<K, V>* _parent;
		int _bf; //平衡因子
		pair<K, V> _kv;
		AVLTreeNode(const pair<K, V>& kv)
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _bf(0)
			,_kv(kv)
		{

		}
	};

	template<class K,class V>
	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;
				}
				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 = 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)
						{
							RotateLR(parent);
						}
						else
						{
							RotateRL(parent);
						}
						break;
					}
					else
					{
						assert(false);
					}
				}
			return true;
		}

		void RotateL(Node* parent)
		{
			Node* sub = parent->_right;
			Node* subl = sub->_left;
			parent->_right = subl;
			if (subl)
			{
				subl->_parent = parent;
			}
			sub->_left = parent;
			Node* ppnode = parent->_parent;
			parent->_parent = sub;
			if (parent == _root)
			{
				_root = sub;
				sub->_parent = nullptr;
			}
			else
			{
				if (parent == ppnode->_left)
				{
					ppnode->_left = sub;
				}
				else
				{
					ppnode->_right = sub;
				}
				sub->_parent = ppnode;
			}
			parent->_bf = 0;
			sub->_bf = 0;
		}
		void RotateR(Node* parent)
		{
			Node* sub = parent->_left;
			Node* subr = sub->_right;
			parent->_left = subr;
			if (subr)
			{
				subr->_parent = parent;
			}
			sub->_right = parent;
			Node* ppnode = parent->_parent;
			parent->_parent = sub;
			if (parent == _root)
			{
				_root = sub;
				sub->_parent = nullptr;
			}
			else
			{
				if (parent == ppnode->_left)
				{
					ppnode->_left = sub;
				}
				else
				{
					ppnode->_right = sub;
				}
				sub->_parent = parent;
			}
			parent->_bf = 0;
			sub->_bf = 0;
		}

		void RotateLR(Node* parent)
		{
			Node* subl = parent->_left;
			Node* sublr = subl->_right;
			int bf = sublr->_bf;
			RotateL(subl);
			RotateR(parent);
			if (bf == -1)
			{
				sublr->_bf = 0;
				parent->_bf = 1;
				subl->_bf = 0;
			}
			else if (bf == 1)
			{
				sublr->_bf = 0;
				parent->_bf = 0;
				subl->_bf = -1;
			}
			else if (bf == 0)
			{
				subl->_bf = 0;
				parent->_bf = 0;
				sublr->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}
		void RotateRL(Node* parent)
		{
			Node* subr = parent->_right;
			Node* subrl = subr->_left;
			int bf = subrl->_bf;
			RotateR(subr);
			RotateL(parent);
			if (bf == -1)
			{
				subrl->_bf = 0;
				parent->_bf = 0;
				subr->_bf = 1;
			}
			else if (bf == 1)
			{
				subrl->_bf = 0;
				parent->_bf = -1;
				subr->_bf = 0;
			}
			else if(bf==0)
			{
				subrl->_bf = 0;
				parent->_bf = 0;
				subr->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_kv.first << " " << root->_bf << endl;
			_InOrder(root->_right);
		}
		void InOrder()
		{
			_InOrder(_root);
		}

		int Height(Node* root)
		{
			if (root == nullptr)
			{
				return 0;
			}
			int leftHeight = Height(root->_left);
			int rightHeight = Height(root->_right);

			return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
		}
		bool _IsBalance(Node* root)
		{
			if (root == nullptr)
				return true;
			int leftHeight = Height(root->_left);
			int rightHeight = Height(root->_right);
			if (abs(rightHeight - leftHeight) >= 2)
			{
				cout << root->_kv.first << "不平衡" << endl;
				return false;
			}
			if (rightHeight - leftHeight != root->_bf)
			{
				cout << root->_kv.first << "平衡因子异常" << endl;
				return false;
			}
			return _IsBalance(root->_left) && _IsBalance(root->_right);
		}
		bool IsBalance()
		{
			return _IsBalance(_root);
		}
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first < key)
				{
					cur = cur->_right;
				}
				else if (cur->_kv.first > key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}
			return NULL;
		}
	private:
		Node* _root = nullptr;
	};
	void TestAVLTree1()
	{
		int a[] = { 4, 2, 6, 1,0 ,67,56,33,212,90};
		AVLTree<int, int> t;
		for (auto e : a)
		{
			if (e == 14)
			{
				int x = 0;
			}

			t.Insert(make_pair(e,e));
		}

		t.InOrder();
		cout << t.IsBalance();
	}
}

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

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

相关文章

论文阅读_解释大模型_语言模型表示空间和时间

论文阅读_解释大模型_语言模型表示空间和时间

英文名称: LANGUAGE MODELS REPRESENT SPACE AND TIME 中文名称: 语言模型表示空间和时间 链接: https://www.science.org/doi/full/10.1126/science.357.6358.1344 https://arxiv.org/abs/2310.02207 作者: Wes Gurnee & Max Tegmark 机构: 麻省理工学院 日期: 2023-10-03…
阅读更多...
142.乐理基础-音程的构唱练习

142.乐理基础-音程的构唱练习

内容参考于&#xff1a;三分钟音乐社 上一个内容&#xff1a;141.乐理基础-男声女声音域、模唱、记谱与实际音高等若干问题说明-CSDN博客 本次内容最好去看视频&#xff1a; https://apphq3npvwg1926.h5.xiaoeknow.com/p/course/column/p_5fdc7b16e4b0231ba88d94f4?l_progra…
阅读更多...
Python变量类型常用的函数【函数】

Python变量类型常用的函数【函数】

一、Python Number(数字)常用的函数 主要有math模块和cmath模块。 math模块&#xff1a;提供了许多对浮点数的数学运算函数。 cmath模块&#xff1a;提供了一些用于复数运算的函数。 使用两个模块里的函数时要先导入&#xff1a; import math查看math模块里的函数&#xff1a…
阅读更多...
ky10 server 离线编译安装nginx

ky10 server 离线编译安装nginx

代码地址 https://gitcode.net/zengliguang/linux_video_audio_nginx_proxy.git 下载代码 查看服务器上下载的代码 编译安装 进入代码路径 cd /root/linux_video_audio_nginx_proxy 执行离线编译安装脚本 source centos7_nginx_offline_comp_install.sh安装编译相关依赖 …
阅读更多...
SystemVerilog构造、包

SystemVerilog构造、包

包 包提供了一种共享不同构造的附加方式。他们的行为与VHDL包。包可以包含函数、任务、类型和枚举。的语法包是&#xff1a; package package_name; items endpackage : package_name 最终的package_name不是必需的&#xff0c;但它使代码更易于阅读。包是import命令在其他…
阅读更多...
智慧城市中的数据力量：大数据与AI的应用

智慧城市中的数据力量：大数据与AI的应用

目录 一、引言 二、大数据与AI技术的融合 三、大数据与AI在智慧城市中的应用 1、智慧交通 2、智慧环保 3、智慧公共安全 4、智慧公共服务 四、大数据与AI在智慧城市中的价值 1、提高城市管理的效率和水平 2、优化城市资源的配置和利用 3、提升市民的生活质量和幸福感…
阅读更多...
String类，StringBuilder类，StringBuffer类

String类，StringBuilder类，StringBuffer类

前言 String类&#xff0c;StringBuilder类&#xff0c;StringBuffer类都是java提供的定义字符串的类&#xff0c;下面是三种字符串类的异同介绍 String类&#xff1a;String类表示的字符串是是常量&#xff0c;一旦创建内容和长度都无法修改 StringBuilder类&#xff1a;St…
阅读更多...
3.7练习题解

3.7练习题解

一共五道题&#xff1a; 1. PERKET&#xff1a; 观察容易发现n的值很小&#xff0c;所以我们可以考虑使用dfs的方法进行解答&#xff0c;首先我们可以考虑一共有n种配料&#xff0c;那么我们就可以考虑到可以选择1到n种配料数目&#xff0c;然后基于这个思路我们再对其进行判断…
阅读更多...
关于JVM的小总结（待补充）

关于JVM的小总结（待补充）

JVM组成及他们之间的关系 装载类子系统字节码执行引擎运行时数据区 装载类子系统 类加载器字节码调节器类加载运行时数据区 字节码执行引擎 运行时数据区 线程私有 虚拟机栈本地方法栈程序计数器 线程共享 堆方法区&#xff08;元空间&#xff09;
阅读更多...
C++的类和对象（四）：拷贝构造函数

C++的类和对象（四）：拷贝构造函数

目录 拷贝构造函数 特性 自定义类型的传值传参和传引用传参对比 赋值运算符重载 拷贝构造函数 基本概念&#xff1a;只有单个形参&#xff0c;该形参是对本类类型对象的引用&#xff08;一般常用const修饰&#xff09;&#xff0c;在创建一个已存在对象一模一样的新对象时…
阅读更多...
IDEA 配置文件乱码，项目编码设置

IDEA 配置文件乱码，项目编码设置

见下图 其中第一二项控制全局以及工程的编码格式&#xff0c;下方的则是 properties 配置文件的格式&#xff0c;统一调整为 UTF-8 后不再乱码
阅读更多...
Java面试篇【并发编程】常见面试题（2024最新）

Java面试篇【并发编程】常见面试题（2024最新）

Java并发编程常见面试题 1.什么是线程和进程&#xff1f; 进程是操作系统分配资源的最小单位&#xff0c;各个进程之间占据独立的寻址空间&#xff0c;运行也是独立运行&#xff0c;进程间通信需要一些机制。进程间切换需要的开销较大。 线程是程序执行的基本单位&#xff0c…
阅读更多...
如何在Linux系统Docker部署Dashy并远程访问内网服务界面

如何在Linux系统Docker部署Dashy并远程访问内网服务界面

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
Unity：Animation 三 Playable、ImportModel

Unity：Animation 三 Playable、ImportModel

目录​​​​​​​ 1. Playables API 1.1 Playable vs Animation 1.2 Advantages of using the Playables API 1.3 PlayableGraph Visualizer 2. Creating models outside of Unity 2.1 Preparing your model files for export 2.1.1 Scaling factors 2.1.2 优化模型文…
阅读更多...
Unity中关于继承ScriptableObject的类

Unity中关于继承ScriptableObject的类

在游戏中我们会经常看到一些.asset的配置文件&#xff0c;而这些文件就是用一个自定义的类去继承ScriptableObject来生成的。比如当前有一些零散特效需要预加载&#xff0c;这个时候我们可以声明一个类去保存这些零散特效对象的信息&#xff0c;然后统一读取加载。 代码&#…
阅读更多...
专访|云安全攻防：从理论到应用的全面探索

专访|云安全攻防：从理论到应用的全面探索

2023年11月&#xff0c;美国核研究实验室&#xff08;INL&#xff09;遭遇数据泄露。同年10月&#xff0c;索尼的员工数据在MOVEit攻击事件中被泄露。2024年2月&#xff0c;某知名制造商因云存储服务器的配置错误导致了敏感数据泄露。 这些事件表示企业必须重视云安全建设&…
阅读更多...
【Memory协议栈】NVRAM Manager 模块介绍

【Memory协议栈】NVRAM Manager 模块介绍

目录​​​​​​​ 前言 正文 1.功能简介 2.关键概念 3.功能详解 3.1 内存硬件抽象层Ea/Fee的寻址方案 3.2 基本存储对象Basic storage objects 3.2.1 NV Block 3.2.2 RAM Block 3.2.3 ROM Block 3.2.4 Administrative block 3.2.5 NV Block Header 3.3块管理类型…
阅读更多...
iostat命令详解

iostat命令详解

转载说明&#xff1a;如果您喜欢这篇文章并打算转载它&#xff0c;请私信作者取得授权。感谢您喜爱本文&#xff0c;请文明转载&#xff0c;谢谢。 iostat是一个使用频率较高的命令&#xff0c;主要用来统计和输出CPU和磁盘IO信息。它的安装很简单&#xff1a; # yum -y insta…
阅读更多...
20240307-1-前端开发校招面试问题整理JavaScript

20240307-1-前端开发校招面试问题整理JavaScript

前端开发校招面试问题整理【1】——JavaScript 1、JavaScript 基础 Q&#xff1a;介绍 js 的基本数据类型&#xff1f; 基本类型&#xff08;值类型&#xff09;&#xff1a;String&#xff0c;Number&#xff0c;Boolean&#xff0c;Null&#xff0c;Undefined&#xff0c;S…
阅读更多...
创邻科技获评环紫金港创新生态圈智源创新企业

创邻科技获评环紫金港创新生态圈智源创新企业

3月1日&#xff0c;由杭州城西科创大走廊管理委员会指导&#xff0c;中共杭州市西湖区委员会、西湖区人民政府主办的“环紫金港创新生态圈”行动推进大会暨2024年紫金港科技城经济高质量发展大会在杭州举办。凭借重要的生态位置和创新业务成果&#xff0c;创邻科技受邀参会并被…
阅读更多...
最新文章

Copyright @ 2022~2023