【C++】AVL树

2023-09-15 14:33:00

在这里插入图片描述
在这里插入图片描述

个人主页：🍝在肯德基吃麻辣烫
我的gitee：C++仓库
个人专栏：C++专栏

文章目录

前言

本文章将会模拟实现一棵AVL树。

以下是本篇文章正文内容

一、什么是AVL树？

AVL树也是一个二叉搜索树，只不过是在二叉搜索树的基础上，增加了一个条件：

任意一棵子树的左右高度差的绝对值不大于1。

设计AVL树的原因

在二叉平衡搜索树中，在正常情况下，对该树的任意节点进行查找，最多查找OlogN次，但如果在极端情况下，该树退化成了单只树，则会极大降低搜索效率，变成O(n)，所以为了避免让二叉搜索树出现极端情况，设计出一棵具有平衡性质的二叉搜索树：AVL树

二、AVL树的性质

  • 1）它的左右子树都是AVL树
  • 2）左右子树高度之差（平衡因子）的绝对值不超过1（-1/0/1）

平衡因子：右子树高度 - 左子树的高度（注意是右 - 左）

由此可知，一棵AVL树是高度平衡的，它的高度可保持在logN，所以搜索效率可以保持在logN

三、二叉树节点的定义

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

	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;
};
  • 1）需要有一个平衡因子存在，即_bf
  • 2）_data值可以是一个键值对，也可以是其他类型，这里我选择了pair。
  • 3）在后面的其他操作中，会频繁用到一个节点的父亲，所以直接在节点中添加一个_parent成员。

四、AVL树的插入

插入大致分为几个步骤：

如果根节点为空，则直接插入到根节点的位置

1）先找到插入位置，因为这是一棵搜索树，如果该节点的值比根小，则往左走，如果比根大，往右边走。

2）找到待插入位置后，插入该节点，然后调整平衡因子。

如果插入的是左边，则parent的平衡因子–，如果插入的是右边，则parent的平衡因子++。

如果parent的平衡因子是1或-1，说明父亲的子树有一边高了，则需要继续向上调整。(最坏情况就是调整平衡因子到根的位置)

如果parent的parent的平衡因子大于1或者小于-1了，则不满足AVL树的特性，需要进行旋转。

旋转

1）右单旋

在这里插入图片描述
新插入的节点在根节点的左侧，导致根节点的平衡因子变成-2。
则需要将根节点进行右旋。
规则如下：

在这里插入图片描述

  • 1）cur的right给parent的left
  • 2）parent变成了cur的right
    调整后，cur变成了新的根，parent变成cur的right
    此时需要注意一些细节：

如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后cur变成新的根，需要替代parent的位置，变成那个节点的孩子。

如果旋转前parent就是根，则直接让旋转后的cur的parent为空即可。

调整后cur和parent的平衡因子变成0。

2）左单旋

在这里插入图片描述
新插入的节点在根节点的右侧，导致根节点的平衡因子变成2。
则需要将根节点进行左旋。
规则如下：

  • 1）cur的left给parent的right
  • 2）parent变成了cur的left
    调整后，cur变成了新的根，parent变成curr的left
    此时需要注意一些细节：

如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后cur变成新的根，需要替代parent的位置，变成那个节点的孩子。

如果旋转前parent就是根，则直接让旋转后的cur的parent为空即可。

调整后cur和parent的平衡因子变成0。

3）左右双旋

在这里插入图片描述

插入新节点后，如果cur的平衡因子为1，parent的平衡因子为-2
说明整颗树的结构大概是这样的：
在这里插入图片描述
这就说明，此时这棵树不再是AVL树，所以我们需要对其进行旋转。

在这里插入图片描述

旋转操作如下：

  • 1）让cur的右指向curright的左，然后cur成为curright的左。此时curright的父亲就变成了原来的cur的父亲，cur的父亲变成了curright

以上操作是左旋的操作过程

  • 2）让parent的左指向curright的右，然后parent变成了curright的右，此时parent的父亲变成了curright。

以上操作是右旋的操作过程

这里还需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后curright变成新的根，需要替代parent的位置，变成那个节点的孩子。

平衡因子的处理：

    • 1）如果旋转之前，curright的平衡因子是0，则说明，curright这个节点，一定是新插入的节点。

（因为如果不是新插入的节点，在插入该节点前，这棵树就不是AVL树了）。

在这里插入图片描述

在进行左右双旋后，cur，curright，parent三个节点的平衡因子都是0。

    • 2）如果旋转之前，curright这个节点的平衡因子是-1，该情况就是上图画出的情况，说明新插入节点在curright的左子树，在左右双旋后，cur和curright的平衡因子变成0，parent的平衡因子是1
    • 3）如果旋转之前，curright这个节点的平衡因子是1，说明新插入节点在curright的右子树，在左右双旋后，parent和curright的平衡因子变成0，cur的平衡因子是-1

4）右左双旋

在这里插入图片描述

插入新节点后，如果cur的平衡因子为-1，parent的平衡因子为2
说明整颗树的结构大概是这样的：
在这里插入图片描述

这就说明，此时这棵树不再是AVL树，所以我们需要对其进行右左旋转。

在这里插入图片描述

旋转操作如下：

  • 1）让cur的左指向curleft的右，然后cur成为curleft的右。此时culeft的父亲就变成了原来的cur的父亲，cur的父亲变成了curleft

以上操作是右旋的操作过程

  • 2）让parent的右指向curleft的左，然后parent变成了curleft的左，此时parent的父亲变成了curleft。

以上操作是左旋的操作过程

这里还需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后currleft变成新的根，需要替代parent的位置，变成那个节点的孩子。

平衡因子的处理：

    • 1）如果旋转之前，curleft的平衡因子是0，则说明，curleft这个节点，一定是新插入的节点。

（因为如果不是新插入的节点，在插入该节点前，这棵树就不是AVL树了）。

在这里插入图片描述

在进行左右双旋后，cur，curleft，parent三个节点的平衡因子都是0。

    • 2）如果旋转之前，curleft这个节点的平衡因子是1，该情况就是上图画出的情况，说明新插入节点在curleft的右子树，在右左双旋后，cur和curleft的平衡因子变成0，parent的平衡因子是-1
    • 3）如果旋转之前，curleft这个节点的平衡因子是-1，说明新插入节点在curleft的左子树，在右左双旋后，parent和curleft的平衡因子变成0，cur的平衡因子是1

以上就是旋转的四种情况。

AVL树插入完整代码

template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:

	AVLTree()
		:_root(nullptr)
	{}

	bool Insert(const pair<K,V> kv)
	{
		if(_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* cur = _root;
		Node* cur_parent = _root;
		//1.找到待插入位置
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				cur_parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				cur_parent = cur;
				cur = cur->_left;
			}
			else
				return false;
		}

		//2.先判断待插入节点是在parent的左边还是右边
		cur = new Node(kv);
		if (cur_parent->_kv.first > kv.first)
		{
			cur_parent->_left = cur;
		}
		else
		{
			cur_parent->_right = cur;
		}
		cur->_parent = cur_parent;


		//下面为调整二叉树的平衡
		
		//1.更新平衡因子
		//
		while (cur_parent)
		{
			//左子树--
			if (cur_parent->_left == cur)
			{
				cur_parent->_bf--;
			}
			//右子树++
			else
			{
				cur_parent->_bf++;
			}

			//平衡因子=0，不再影响祖先
			if (cur_parent->_bf == 0)
			{
				break;
			}
			
			//不平衡了，影响祖先，要向上也调整
			else if (cur_parent->_bf == 1 || cur_parent->_bf == -1)
			{
				cur = cur_parent;
				cur_parent = cur_parent->_parent;
			}

			//此时该树出问题了，需要旋转进行平衡

			else if (cur_parent->_bf == 2 || cur_parent->_bf == -2)
			{
					//右边高，向左旋转
				if (cur_parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(cur_parent);
				}

				//左边高，向右旋转
				else if (cur_parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(cur_parent);
				}

				//折线型，右边高，右左双旋
				else if (cur_parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(cur_parent);
				}

				//折线形，左边高，左右双旋
				else if (cur_parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(cur_parent);
				}
					
				//旋转完成后一定平衡了，则break
				break;

			}

			else
			{
				assert(false);
			}

		}
		cout << kv.first << endl;
		return true;
	}

	//左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		Node* ppNode = parent->_parent;

		parent->_right = curleft;
		if (curleft)
			curleft->_parent = parent;

		cur->_left = parent;
		parent->_parent = cur;

		if (!ppNode)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppNode->_right == parent)
			{
				ppNode->_right = cur;
			}
			else
			{
				ppNode->_left = cur;
			}

			cur->_parent = ppNode;
		}

		cur->_bf = parent->_bf = 0;

	}

	//右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		Node* ppNode = parent->_parent;

		parent->_left = curright;
		//如果cur的右子树是空
		if(curright)
			curright->_parent = parent;

		cur->_right = parent;
		parent->_parent = cur;

		if (!ppNode)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			cur->_parent = ppNode;
			//要知道根的左边是cur还是右边是cur
			if (ppNode->_left == parent)
			{
				ppNode->_left = cur;
			}
			else
			{
				ppNode->_right = cur;
			}
		}

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

	void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		int bf = curright->_bf;
		
		RotateL(parent->_left);
		RotateR(parent);

		//该节点为新插入的节点
		if (bf == 0)
		{
			curright->_bf = 0;
			cur->_bf = 0;
			parent->_bf = 0;
		}

		//新插入节点在curright的右边，右边高了
		//     p
		//   c
		//     cr

		else if (bf == 1)
		{
			curright->_bf = 0;
			cur->_bf = -1;
			parent->_bf = 0;
		}

		//新插入节点在curright的左边，左边高了
		else if (bf == -1)
		{
			curright->_bf = 0;
			cur->_bf = 0;
			parent->_bf = 1;
		}

	}

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

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

		//该节点为新插入的节点
		if (bf == 0)
		{
			curleft->_bf = 0;
			cur->_bf = 0;
			parent->_bf = 0;
		}
		//新插入节点在curleft的右边，右边高了
		//     p
		//		  c
		//     cl
		else if (bf == 1)
		{
			curleft->_bf = 0;
			cur->_bf = 0;
			parent->_bf = -1;
		}
		//新插入节点在curleft的左边，左边高了
		else if (bf == -1)
		{
			curleft->_bf = 0;
			cur->_bf = 1;
			parent->_bf = 0;
		}
	}

private:
	Node* _root = nullptr;
};

验证一棵树为AVL树

  • 1）验证这棵树的中序遍历是有序的。
  • 2）验证每一棵树的左右子树高度差不大于1
int Height(Node* root)
{
	if (root == nullptr)
		return 0;

	int left = Height(root->_left);
	int right = Height(root->_right);
	return left > right ? left + 1 : right + 1;
}

bool IsBalanceTree()
{
	cout << "IsBalanceTree():";
	return _IsBalanceTree(_root);
}

//通过高度判断是否为AVL树
//1.通过高度计算出真实的平衡因子，再与AVL树本身的平衡因子进行比较

bool _IsBalanceTree(Node* root)
{
	if (root == nullptr)
		return true;

	int lefth = Height(root->_left);
	int righth = Height(root->_right);
	int bf = righth - lefth;

	if (bf != root->_bf || bf > 1 || bf < -1)
	{
		return false;
	}

	return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

AVL树的性能分析

由于AVL树的绝对平衡（每棵树高度差不大于1），每次在插入数据时，难免会遇到多次旋转，最坏情况需要旋转到根部。虽然旋转时间复杂度O(1)，但如果旋转次数过多，也会造成效率下降。在本文中没有提到AVL树的删除，删除操作更加复杂，我没有研究过hh，不过同样每删除一个数据，都必须保证整棵树是AVL树，这又需要大量旋转来维持它的平衡。

所以在面对大量数据，并且不再有新数据的插入时，可以使用AVL树进行查找，效率为O(logN).

总结

本文主要讲述了AVL树的插入过程及其效率分析。

更多推荐

Cesium 问题：二三维切换矩形区域展示不够完整

文章目录问题分析问题设置影响图层覆盖范围时，出现三维和二维切换后展示不够完整的情况，Cesium.Rectangle.fromDegrees(-180,-90,180,90)创建的矩形区域，按理说是已经设置了全覆盖，但切换二维后并不全覆盖例如三维下切换到二维分析Cesium.Rectangle.fromDegrees(

资讯| 工信部拟筹建元宇宙标准化工作组；《权游》作者起诉OpenAI

元宇宙赛道工信部：优先开展“元宇宙+工业制造”等行业应用标准研制9月18日，工业和信息化部科技司就《工业和信息化部元宇宙标准化工作组筹建方案（征求意见稿）》（以下简称《方案》）公开征求意见。工业和信息化部元宇宙标准化工作组工作范围包括五个方面：一是研究分析元宇宙领域标准化需求方向，建设和维护元宇宙行业标准体系，提出元宇

leetcode 2602. 使数组元素全部相等的最少操作次数

给你一个正整数数组nums。同时给你一个长度为m的整数数组queries。第i个查询中，你需要将nums中所有元素变成queries[i]。你可以执行以下操作任意次：将数组里一个元素增大或者减小1。请你返回一个长度为m的数组answer，其中answer[i]是将nums中所有元素变成queries[i]的最少操作次数

多线程详解(上)

文章目录一、线程的概念1）线程是什么2）为甚要有线程（1）“并发编程”成为“刚需”（2）在并发编程中,线程比进程更轻量.3）线程和进程的区别二、Thread的使用1）线程的创建继承Thread类实现Runnable接口继承Thread类（使用匿名内部类）实现Runnable接口（使用匿名内部类）使用lambda2）Th

【探索C++】string类详解

(꒪ꇴ꒪)，Hello我是祐言QAQ我的博客主页：C/C++语言，数据结构，Linux基础，ARM开发板，网络编程等领域UP🌍快上🚘，一起学习，让我们成为一个强大的攻城狮！送给自己和读者的一句鸡汤🤔：集中起来的意志可以击穿顽石!作者水平很有限，如果发现错误，请在评论区指正，感谢🙏在C++中，字符串处理是非常重要

Linux 文件、目录和用户权限管理指南

文章目录1.用户和组管理引言创建用户删除用户更改用户密码修改用户属性创建组删除组将用户添加到组将用户从组中移除2.文件和目录权限管理引言文件权限概述更改文件权限更改文件所有者和所属组更改目录权限列出文件和目录权限使用特殊权限文件和目录权限的案例分析继承父目录权限特殊权限的使用案例ACL（访问控制列表）umask注意事项

双网卡主机内网外网网关冲突问题探索（策略路由、网络命名空间）（内外网双网卡时，通常不需要在内网网卡上设置默认网关）

文章目录问题背景内外网双网卡时，通常不需要在内网网卡上设置默认网关1.网络冲突2.性能影响解决方法1.默认网关的作用2.只设置一个默认网关3.内网通信4.结论参考文章问题背景我们有一台windowsserver2012服务器，配置了双网卡，一个网卡配置外网，一个网卡配置内网，当我们将外网网络配置外网网关，内网网络配置内

uvm源码解读-sequence，sequencer，driver三者之间的握手关系1

1.startitem1.start_item();sequencer.wait_for_grant(prior);this.pre_do(1);需要指出，这里明确说明了wait_for_grant和send_request之间不能有任何延迟，所以在mid_do这个任务里千万不能有任何延迟。taskuvm_sequen

Spring AOP使用

SpringAOP是什么？AOP(面向切面编程)：将那些与业务无关，却为业务模块所共同调用的逻辑（例如事务处理、日志管理、权限控制等）封装抽取成一个可重用的模块，这个模块被命名为“切面”（Aspect），便于减少系统的重复代码，降低模块间的耦合度，并有利于未来的可拓展性和可维护性；在SpringAOP中，切面由切点（P

【2023集创赛】IEEE杯二等奖作品：高性能亳米波倍频程压控振荡器设计

本文为2023年第七届全国大学生集成电路创新创业大赛（“集创赛”）IEEE杯二等奖作品分享，参加极术社区的【有奖征集】分享你的2023集创赛作品，秀出作品风采，分享2023集创赛作品扩大影响力，更有丰富电子礼品等你来领！团队介绍参赛单位：南京邮电大学队伍名称：顺芯如意指导老师：谢祖帅，王子轩参赛队员：张文旭，汤金圣，秦

GE IS220PAICH2A 336A4940CSP11 控制脉冲模块

GEIS220PAICH2A336A4940CSP11控制脉冲模块是一种用于工业自动化和控制系统的模块，通常用于监测和生成脉冲信号，以控制各种设备和过程。以下是可能与该控制脉冲模块相关的一些产品功能：脉冲生成：GEIS220PAICH2A336A4940CSP11控制脉冲模块通常具有脉冲生成功能，可以生成具有特定频率、

热文推荐
  1. iMazing 2 .17.9最新官方中文版免费下载安装激活

    iMazing2.17.9最新版是一款帮助用户管理IOS手机的应用程序，iMazing2最新版能力远超iTunes提供的终极的iOS设备管理器。IMazing与你的iOS设备(iPhone、iPad或iPod)相连，使用起来非常的方便。作为苹果指定的iOS设备同步工具。mazing什么意思iMazing2.17.9是一

  2. springcloud相关面试题

    目录springcloud相关面试题SpringCloud几个核心组件服务注册与发现组件——Eureka网关组件——Gateway路由：过滤：服务调用组件——Feign(默认包含Ribbon、Hystrix,基于Ribbon实现负载均衡)Ribbon和Feign调用服务的区别Feign、Ribbon、Hystrix三者

  3. spring的ThreadPoolTaskExecutor装饰器传递调用线程信息给线程池中的线程

    概述需求是想在线程池执行任务的时候，在开始前将调用线程的信息传到子线程中，在子线程完成后，再清除传入的数据。下面使用了spring的ThreadPoolTaskExecutor来实现这个需求.ThreadPoolTaskExecutor在jdk中使用的是ThreadPoolExecutor，用于自定义线程池。在spri

  4. FTP和SFT区别记录笔记

    项目中，需要使用ftp服务器上传下载文件，之前做过sftp的文件上传下载，以为是一个东西，迅速的把之前的工具类拿过来使用，发现文件为空，特此记录一下二者的区别和工具类。SFTP（SecureFileTransferProtocol）和FTP（FileTransferProtocol）是两种用于文件传输的协议，它们之间有

  5. 软考-操作系统

    /4操作系统的作用进程进程的概念进程是程序的一次执行过程，没有程序就没有进程进程可有多个线程，线程可共享资源进程的两个基本属性：可拥有资源的独立单位可独立调度和分配资源的基本单位线程可共享：内存地址空间代码数据文件线程不可共享：程序计数器寄存器栈进程的状态进程的调度（PV操作）重重点同步是合作进程的直接制约问题互斥是申

  6. Python-模块

    python模块（Module），是一个python文件，以.py结尾，模块可以定义函数，类和变量。模块的导入方法[from模块名]import[模块|类|变量|函数|*][as别名]import模块名importtimetime.sleep(5)from模块import功能fromtimeimportsleepsle

  7. MyBatis面试题(二)

    文章目录前言一、MyBatis与Hibernate有哪些不同？二、MyBatis的好处是什么？三、简述Mybatis的Xml映射文件和Mybatis内部数据结构之间的映射关系？四、什么是MyBatis的接口绑定,有什么好处？五、接口绑定有几种实现方式,分别是怎么实现的?六、什么情况下用注解绑定,什么情况下用xml绑定？

  8. PMP是水证吗，它的含金量到底怎么样？

    不是水证，毕竟到现在为止，国内已经有50万人拿到证了，没用干嘛考呢，可能有人是跟风考，考了也没处用，自然是水证，花的钱打水漂了嘛。（PMP干货放在文末了）所以建议啊，是项目经理等在职的，或者真的是想从事项目管理行业，又或者真的想学习项目管理的人的去考，如图，一般都是技术转项目、项目经理之类的是主要考试人群。我来说下pm

  9. 如何使用远程桌面软件进行远程工作

    远程工作提供了更大的灵活性和自由度，使得可以在任何地点工作。而要实现高效的远程工作，一个关键的工具就是远程桌面软件。本文将详细介绍如何使用远程桌面软件进行远程工作，以帮助读者提高工作效率。一、了解远程桌面软件的基本原理远程桌面软件是一种通过网络连接，将本地计算机的桌面映射到远程计算机上的工具。它允许用户在远程计算机上操