c++AVL树

c++AVL树

1. 前言

map/multimap、set/multiset这几个容器的共同点是：它们的底层都是按照搜索二叉树来实现的，但是搜索二叉树存在一个缺陷：如果往树中插入的元素有序或接近有序，二叉树搜索就会退化成单支树，时间复杂度会退化成O(N)。

因此map、set等关联式容器的底层结构对搜索二叉树做了平衡处理，即用平衡树（AVL树）来实现。

2. AVL树的概念

俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决二叉搜索树将退化为单支树的方法：

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。平衡因子不是必须的，只是一种控制方式，帮助便捷得控制树。

AVL树的性质：

1.它的左右子树都是AVL树

2.左右子树高度之差（简称平衡因子）的绝对值不超过1(-1/0/1)，平衡因子=右子树高度-左子树高度

3.如果一颗二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可以保持在O(log2n)，搜索时间复杂度为O(log2n) 。

3. AVL树的定义

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data)
        :_pLeft(nullptr),_pRight(nullptr),_pParent(nullptr),_data(data),_bf(0)
        {}
    AVLTreeNode<T>* _pLeft;//左孩子
    AVLTreeNode<T>* _pRight;//右孩子
    AVLTreeNode<T>* _pParent;//该结点的父结点
    T_data;
    int _bf;       
};

3. AVL树的插入

AVL树是添加了平衡因子的搜索二叉树，它的插入可以分成两步：

1.按照搜索二叉树的方式插入新结点

2.调整平衡因子

在这里插入图片描述

在这颗AVL树中，绿色的数字表示每个结点的平衡因子(_bf)：如果左子树高度多1，那么_bf减1；如果右边的子树高度多1，那么_bf；如果左右子树高度相等，那么_bf就是0

在这里插入图片描述

插入一个结点会对平衡因子产生影响

插入结点对平衡因子的影响：

  1. 在父结点的左边插入，父结点的_bf–；在父结点的右边插入，父结点的_bf++

  2. _bf是否继续更新取决于父结点的高度是否发生变化，是否影响爷结点

  3. 更新后，如果_bf是0，说明更新前_bf是1或-1。父结点的左右平衡了，高度不变，不会影响爷结点。

  4. 更新后，如果_bf是1或-1，说明更新前_bf是0，父结点的左右不平衡了，高度变化，会影响爷结点。

  5. 更新后，如果_bf是2或-2，树就要旋转，使树的结构仍符合AVL树。

判断怎么插入的方式是通过查看平衡因子的值决定的：

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
			{
				// 插入之前AVL树就有问题
				assert(false);
			}
		}

		return true;
	}

4. AVL树的旋转

由于AVL树插入的规则是根据“比我小的插入左边，比我大的插入右边”，所以在某些情况下，插入会导致出现不平衡的情况。这时候就需要通过旋转操作来平衡AVL树。旋转的目的是降低树的高度。

在这里插入图片描述

某些情况插入可能会导致出现不平衡的情况

在这里插入图片描述

这种情况下，把结点旋转到左边，树就能变回平衡了

4.1 左单旋：

对于插入的结点是在右边的情况，只需要把200的结点向左旋转即可。

左旋某个结点的口诀是**“我的左变成你的右，你变成我的左”**。

在这里插入图片描述

200的左子树（b）变成了100的右子树，100变成了200的左孩子

void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    
    parent->_right = subRL;
    if(subRL)//b不一定有
        subRL->_parent = parent;
    subR->_left = parent;
    Node* ppnode = parent->parent;
    parent->_parent = subR;
    
    if(ppnode == _root)//判断100为根结点的情况
    {
        _root=subR;
        subR->_parent = nullptr;
    }
    else			 //判断100还有父结点的情况
    {
        if(ppnode->left == parent)//判断100在它父结点的左边的情况
        {
            ppnode->_left = subR;
        }
        else					//判断100在它父结点的右边的情况
        {
            ppnode->_right = subR;
        }
    }
    parent->_bf = 0;
    subR->_bf = 0;
}

4.2 右单旋：

对于插入的结点是在左边的情况，只需要把100的结点向右旋转即可。

右旋某个结点的口诀是**“我的右变成你的左，你变成我的右”**。

在这里插入图片描述

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

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

		subL->_right = parent;

		Node* ppnode = parent->_parent;
		parent->_parent = subL;

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

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

4.3 双旋：

双旋也有两种情况，可以分为先左单旋再右单旋的结构和先右单旋再左单旋的结构：

4.3.1 左右双旋

如果插入的结点在中间且左高右低，这时候不能直接在这个层面上操作，还需要把b拆开，然后再对插入的左或右子树进行先左旋再右旋的操作：

在这里插入图片描述

那么此时需要分三种情况讨论

插入的结点在中间结点的左子树：

在这里插入图片描述

在这里插入图片描述

插入的结点在中间结点的右子树：

如果插入的结点在150的右边，那么其实操作和上面类似，只是最后的平衡因子不一样

在这里插入图片描述

在这里插入图片描述

中间结点就是被插入的结点本身：

如果150就是被插入的结点，操作也是一样的，先左单旋，再右单旋

在这里插入图片描述

void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* 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 == 1)//插入在中间结点的右边
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == 0)//中间结点就是插入结点
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
4.2 右左双旋

如果插入的结点在中间且左低右高，需要把b拆开，然后再对插入的左或右子树进行先右旋再左旋的操作：

在这里插入图片描述

插入的结点在中间结点的左子树：

在这里插入图片描述

在这里插入图片描述

插入的结点在中间结点的右子树：

在这里插入图片描述

在这里插入图片描述

中间的结点就是插入结点本身：

在这里插入图片描述

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

		RotateR(subR);
		RotateL(parent);

		subRL->_bf = 0;
		if (bf == 1)
		{
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else
		{
			parent->_bf = 0;
			subR->_bf = 0;
		}
	}

	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 + 1 : rightHeight + 1;
	}

	int Height()
	{
		return _Height(_root);
	}

5. AVL树的检查

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步
1.验证其为二叉搜索树：

如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

2.验证其为平衡树：

每个节点子树高度差的绝对值不超过1注意节点中如果没有平衡因子）
节点的平衡因子是否计算正确

bool _IsBalance(Node* root, int& height)
	{
		if (root == nullptr)
		{
			height = 0;
			return true;
		}

		int leftHeight = 0, rightHeight = 0;
		if (!_IsBalance(root->_left, leftHeight) 
			|| !_IsBalance(root->_right, rightHeight))
		{
			return false;
		}

		if (abs(rightHeight - leftHeight) >= 2)
		{
			cout <<root->_kv.first<<"不平衡" << endl;
			return false;
		}

		if (rightHeight - leftHeight != root->_bf)
		{
			cout << root->_kv.first <<"平衡因子异常" << endl;
			return false;
		}

		height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

		return true;
	}

	bool IsBalance()
	{
		int height = 0;
		return _IsBalance(_root, height);
	}

6. AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O(log2n)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。

因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑AVL树，但一个结构经常修改，就不太适合。
t << root->_kv.first <<“平衡因子异常” << endl;
return false;
}

	height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

	return true;
}

bool IsBalance()
{
	int height = 0;
	return _IsBalance(_root, height);
}




## 6. AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即**O(log2n)**。但是**如果要对AVL树做一些结构修改的操作，性能非常低下**，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。

因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑AVL树，但一个结构经常修改，就不太适合。

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

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

相关文章

Java入门之数据类型

Java入门之数据类型

一、数据类型 基本数据类型 &#xff08;1&#xff09;如果要定义“long类型的变量要在数值后面加一个L作为后缀” &#xff08;2&#xff09;如果要定义float类型的变量的时候数据值也要加一个作为后缀 小结&#xff1a; 练习 内容&#xff1a; 姓名&#xff1a;巴巴托斯 &…
阅读更多...
centos7二进制安装openstack train版本双网口五节点

centos7二进制安装openstack train版本双网口五节点

这里写目录标题 材料准备宿主机安装KVM 网络规划硬件规划本案例局限性密码规划虚拟机准备网络准备centos7模板机准备 数据库安装安装rabbitMQ消息队列安装memcached服务安装Etcd安装keystone身份服务创建数据库用户keystone安装keystone组件创建admin并启动keystone监听验证key…
阅读更多...
第3章：角色提示，强化Chatgpt输出新篇章！

第3章：角色提示，强化Chatgpt输出新篇章！

角色提示技术 角色提示技术&#xff08;role prompting technique&#xff09;&#xff0c;是通过模型扮演特定角色来产出文本的一种方法。用户为模型设定一个明确的角色&#xff0c;它就能更精准地生成符合特定上下文或听众需求的内容。 比如&#xff0c;想生成客户服务的回复…
阅读更多...
新手如何去做性能测试？

新手如何去做性能测试？

1、性能测试是什么&#xff1f; 一句话概括&#xff1a;不断的通过不同场景的系统表现去探究系统设计与资源消耗之间的平衡。 具体一点&#xff1a;通过在测试环境下对系统或构件的性能进行探测&#xff0c;用以验证在生产环境下系统性能是否达到预估的性能需求&#xff0c;发…
阅读更多...
堆排序在优先队列的应用及其C代码示例

堆排序在优先队列的应用及其C代码示例

堆排序在优先队列的应用及其C代码示例 一、引言二、堆排序的基本思想三、优先队列的实现四、最大优先队列的实现五、最小优先队列的实现六、性能分析七、C代码示例八、应用场景与实例九、堆排序与优先队列的进一步优化十、结论 一、引言 堆排序&#xff08;Heap Sort&#xff…
阅读更多...
javascript基础代码练习

javascript基础代码练习

一、输入新增病例数&#xff0c;累计确诊病例数&#xff0c;14天内聚集性疫情发生天数。新增或者累计确诊病例为0则该地区为低风险地区。新增大于0且累计确诊&#xff1c;50或者累计大于50且14天内聚集性疫情发生天数为0的地区为中风险地区。其他情况为高风险地区。 <!DOCT…
阅读更多...
Live800:应对客户投诉的技巧与方法，以解决为导向

Live800:应对客户投诉的技巧与方法，以解决为导向

在商业世界中&#xff0c;客户投诉是无法避免的现象。无论你的产品或服务有多好&#xff0c;总会有一些客户对其不满。关键在于&#xff0c;你如何应对这些投诉。正确的处理方式可以转危为机&#xff0c;提升客户满意度&#xff0c;甚至增强品牌忠诚度。文章将探讨如何有效处理…
阅读更多...
Python基础教程：基本数据类型

Python基础教程：基本数据类型

基本数据类型 不可变数据（3 个）：Number（数字）、String（字符串）、Tuple（元组） 可变数据（3 个）：List（列表）、Dictionary（字典）、Set（集合） Numbers（数字） 数字数据类型用于存储数值。 他们是不可改变的数据类型，这意味着改变数字数据类型会分配一个新的对…
阅读更多...
Linux 进程信号：产生信号

Linux 进程信号：产生信号

目录 一、通过终端按键产生信号 1、signal()函数 2、核心转储 3、ulmit命令 二、调用系统函数向进程发信号 1、kill()函数 2、raise()函数 3、abort()函数 三、发送信号的过程 读端关闭、写端继续写入的情况 如何理解软件条件给进程发送信号: 四、软件条件产生信…
阅读更多...
【Vue】可拖拽侧边栏实现

【Vue】可拖拽侧边栏实现

在本篇博客中&#xff0c;我们将探讨如何在 Vue.js 项目中实现一个可拖拽的侧边栏。此功能可以通过修改 HTML 和 Vue 组件的脚本来实现。 首先&#xff0c;我们需要在 HTML 文件中定义侧边栏的容器和用于拖拽的元素。在 Vue 组件中&#xff0c;我们将使用 Vue 的响应式系统来追…
阅读更多...
缓存菜品、套餐、购物车相关功能

缓存菜品、套餐、购物车相关功能

一、缓存菜品 通过缓存的方式提高查询性能 1.1问题说明 大量的用户访问导致数据库访问压力增大&#xff0c;造成系统响应慢&#xff0c;用户体验差 1.2 实现思路 优先查询缓存&#xff0c;如果缓存没有再去查询数据库&#xff0c;然后载入缓存 将菜品集合序列化后缓存入red…
阅读更多...
流域生态系统水-碳-氮耦合过程模拟

流域生态系统水-碳-氮耦合过程模拟

原文链接&#xff1a;流域生态系统水-碳-氮耦合过程模拟https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247599209&idx3&snbb447abff048424d640c4a45755451f7&chksmfa82058ecdf58c9810ec4c20ccaa521c71773422647f508b690ac4d90df1e273b65ae2db7521&…
阅读更多...
财报解读：中通正在从“价格战”跳到“价值战？”

财报解读：中通正在从“价格战”跳到“价值战？”

从数据来看&#xff0c;我国快递行业持续保持着上升势头。国家邮政局数据显示&#xff0c;今年1至2月我国快递发展指数为329.6&#xff0c;同比提升26.7%。 不过&#xff0c;在向好的行业趋势当中&#xff0c;相关企业仍有烦忧。一方面&#xff0c;行业竞争加剧&#xff0c;新…
阅读更多...
IP定位技术打击网络犯罪

IP定位技术打击网络犯罪

IP定位技术在打击网络犯罪中扮演着至关重要的角色。随着互联网的普及和网络技术的飞速发展&#xff0c;网络犯罪现象日益严重&#xff0c;对社会的稳定和安全造成了极大的威胁。IP定位技术的应用&#xff0c;为公安机关追踪和打击网络犯罪提供了有力的技术支持。 首先&#xff…
阅读更多...
【OS探秘】【虚拟化】【软件开发】在Windows 11上安装mac OS虚拟机

【OS探秘】【虚拟化】【软件开发】在Windows 11上安装mac OS虚拟机

一、所需原料 Windows 11主机、Oracle VM VirtualBox虚拟化平台、mac OS 11镜像文件 二、安装步骤 1、 在VBox管理器中&#xff0c;点击“新建”&#xff0c;进入向导模式&#xff0c;指定各个字段&#xff1a;
阅读更多...
Navicat BI 工具 | 连接数据

Navicat BI 工具 | 连接数据

早前&#xff0c;海外 LearnBI online 博主 Adam Finer 对 Navicat Charts Creator 这款 BI&#xff08;商业智能&#xff09;工具进行了真实的测评。上一期&#xff0c;我们介绍了这位博主对 Navicat BI 工具的初始之感。今天&#xff0c;我们来看看从连接数据的角度&#xff…
阅读更多...
Redis是单线程还是多线程？（面试题）

Redis是单线程还是多线程？（面试题）

1、Redis5及之前是单线程版本 2、Redis6开始引入多线程版本&#xff08;实际上是 单线程多线程 版本&#xff09; Redis6及之前版本&#xff08;单线程&#xff09; Redis5及之前的版本使用的是 单线程&#xff0c;也就是说只有一个 worker队列&#xff0c;所有的读写操作都要…
阅读更多...
外包干了15天，技术退步明显。。。。。。

外包干了15天，技术退步明显。。。。。。

说一下自己的情况&#xff0c;本科生&#xff0c;19年通过校招进入武汉某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试&a…
阅读更多...
07、Lua 流程控制

07、Lua 流程控制

Lua 流程控制 Lua 流程控制控制结构语句 Lua 流程控制 Lua编程语言流程控制语句通过程序设定一个或多个条件语句来设定。在条件为 true 时执行指定程序代码&#xff0c;在条件为 false 时执行其他指定代码。 以下是典型的流程控制流程图&#xff1a; 控制结构的条件表达式结…
阅读更多...
基于RAG的大模型知识库搭建

基于RAG的大模型知识库搭建

什么是RAG RAG(Retrieval Augmented Generation)&#xff0c;即检索增强生成技术。 RAG优势 部分解决了幻觉问题。由于我们可以控制检索内容的可靠性&#xff0c;也算是部分解决了幻觉问题。可以更实时。同理&#xff0c;可以控制输入给大模型上下文内容的时效性&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023