数据结构---AVL树

2023-09-20 16:34:07

AVL树

AVL树的概念

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

一颗AVL树或者是空树，或者是具有以下性质的二叉搜索树。

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

在这里插入图片描述

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

AVL树节点的定义

template <class K, class V>
class AVLNode
{
public:
	AVLNode<K, V>* _letf;
	AVLNode<K, V>* _right;
	AVLNode<K, V>* _parent;

	pair<K, V> _kv;

	int _bf;

	AVLNode(const pair<K, V>& kv)
		:_left(nullptr)// 左孩子
		, _right(nullptr)// 右孩子
		, _parent(nullptr)// 父节点
		, _kv(kv)// 平衡因子
		,_bf(0)
	{}

};

AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索申诉，那么AVL树的插入过程可以分为两步。

  1. 按照二叉搜索树的方式插入新节点
  2. 调整平衡因子

如果这个节点新增在左，parent平衡因子减1；如果新增在右，parent平衡因子加1。如果更新后parent平衡因子为0，说明parent所在的子树的高度不变，不会影响祖先，不用再继续沿着到root的路径往上更新。更新后parent的平衡因子为0或者-1，说明parent所在的子树的高度变化，会影响祖先，需要沿着到root的路径往上更新。更新后parent平衡因子为2或者-2，说明parent所在子树的高度变化且不平衡，要对parent所在的子树进行旋转，让它平衡。

如何通过旋转，让这个树平衡呢？

右边高，就往左边旋转。

左边高，就往右边旋转。

旋转的时候要注意，保持他是搜索树，变成平衡树且降低这个子树的高度。
在这里插入图片描述

左单旋，右边高，强行往左边旋。

右单旋与左单旋道理一样。

在这里插入图片描述

如果出现了上图中的树，靠左单旋或者右单旋就不能到平衡的目的了。这种情况要靠双旋来解决。

就图中的树而言：先以7为旋转点，进行右单旋(此时6会变成7的右儿子，此时树的情况就是一条斜线)，在以5为旋转点，进行左单旋。就可以平衡了。

但这个时候需要对平衡因子做出调整，因为左右旋转之后会把平衡因子更新为0，所以到强行更改一下旋转部分的平衡因子。

	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		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 if (cur == parent->_parent)
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				// 再更新的过程中，父节点的平衡因子=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);
				}// 1.左单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}// 2.右单旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}// 3.右左单旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}// 4.左右单旋
				break;
			}
			else
			{
				// 防止代码出bug，遇到平衡因子为>2的情况。
				assert(false);
			}

		}

		return true;

	}

源代码

#pragma once

template <class K, class V>
class AVLNode
{
public:
	AVLNode<K, V>* _left;
	AVLNode<K, V>* _right;
	AVLNode<K, V>* _parent;

	pair<K, V> _kv;

	int _bf;

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

};


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

	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		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 if (cur == parent->_parent)
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				// 再更新的过程中，父节点的平衡因子=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);
				}// 1.左单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}// 2.右单旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}// 3.右左单旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}// 4.左右单旋
				break;
			}
			else
			{
				// 防止代码出bug，遇到平衡因子为>2的情况。
				assert(false);
			}

		}

		return true;

	}

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



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

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

	}


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


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

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

	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		
		parent->_right = curleft;
		if (curleft)
			curleft->_parent = parent;

		cur->_left = parent;
		Node* ppnode = parent->_parent; // 如果parent是一颗局部子树，ppnode用来记录局部子树的父节点
		parent->_parent = cur;

		if (parent == _root) // 如果parent是根节点
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else // 如果parent是一颗局部的子树
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
			cur->_parent = ppnode;
		}


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

	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;

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


		cur->_right = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = cur;

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

			}

			cur->_parent = ppnode;
		}

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

	void InOrder()
	{
		_InOrder(_root);
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << endl;
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;
};
更多推荐

Git学习笔记10

代码更新方法：蓝绿部署：蓝绿部署，英文名：BlueGreenDeployment，是一种可以保证系统在不间断提供服务的情况下上线代码的部署方式。如何保证系统不间断提供服务呢？蓝绿部署的模型中包含两套集群。在正常情况下（没有上线操作），集群A和集群B的代码版本是一致的，并且同时对外提供服务。在有项目代码上线的时候，我们首

C++ 基本的输入输出

C++基本的输入输出C++标准库提供了一组丰富的输入/输出功能，我们将在后续的章节进行介绍。本章将讨论C++编程中最基本和最常见的I/O操作。C++的I/O发生在流中，流是字节序列。如果字节流是从设备（如键盘、磁盘驱动器、网络连接等）流向内存，这叫做输入操作。如果字节流是从内存流向设备（如显示屏、打印机、磁盘驱动器、网

【PX4】PX4第一个offborad例程

【PX4】PX4第一个offborad例程文章目录【PX4】PX4第一个offborad例程1.什么是OFFBOARD2.第一个offboard例程3.编写launch文件Reference1.什么是OFFBOARDPX4的OFFBOARD指的是外部控制模式，飞行器根据飞行控制栈外部（如机载计算机）提供的设定值控制位置

API安全

1API的简介API代表应用程序编程接口，它由一组允许软件组件进行通信的定义和协议组成。作为软件系统之间的中介，API使软件应用程序或服务能够共享数据和功能。但是API不仅仅提供连接基础,它还管理软件应用程序如何被允许进行通信和交互。API控制程序之间交换请求的类型、请求的方式以及允许的数据格式。例如，智能手机上的天气

小谈设计模式（2）—简单工厂模式

小谈设计模式（2）—简单工厂模式专栏介绍专栏地址专栏介绍简单工厂模式简单工厂模式组成抽象产品（AbstractProduct）具体产品（ConcreteProduct）简单工厂（SimpleFactory）三者关系核心思想Java代码实现首先，我们定义一个抽象产品接口Product，其中包含一个抽象方法use()：然后

Redis的缓存、消息队列、计数器应用

目录一、redis的应用场景二、redis如何用于缓存三、redis如何用于消息队列四、redis如何用于计数器一、redis的应用场景Redis在实际应用中有广泛的应用场景，以下是一些常见的Redis应用场景：缓存：Redis可以用作缓存层，将频繁读取的数据存储在内存中，提高数据读取速度，减轻数据库负载。计数器：Re

Vulnhub系列靶机---HarryPotter-Fawkes-哈利波特系列靶机-3

文章目录信息收集主机发现端口扫描dirsearch扫描gobuster扫描漏洞利用缓冲区溢出edb-debugger工具msf-pattern工具docker容器内提权tcpdump流量分析容器外-sudo漏洞提权靶机文档：HarryPotter:Fawkes下载地址：Download(Mirror)难易程度：难上难信

Redis 集合操作实战（全）

目录SADD插入集合SCARD取元素数量SPOP随机移除元素SREM移除多个元素SMOVE移动元素到别的集合SMEMBERS取所有成员SRANDMEMBER取指定数量元素SISMEMBER判断元素是否存在SUNION多集合求并集SUNIONSTORE多集合求并集（存储）SINTER多集合求交集SINTERSTORE多集

PY32F003F18之比较器问题

PY32F003F18的模拟模块，其内部参考电压容易受到电源电压影响。当我连接"USB转串口的RXD"时，PC接收到模拟数据均正常；当我连接“USB转串口的TXD”时，发现内部参考电压的AD值为0xFFF。断开连接的“USB转串口的TXD”，模拟功能模块又恢复正常。于是用万用表测量“USB转串口的TXD”的电压，开路电

Spring高手之路10——解锁Spring组件扫描的新视角

文章目录1.组件扫描路径2.按注解过滤组件（包含）3.按注解过滤组件（排除）4.通过正则表达式过滤组件5.Assignable类型过滤组件6.自定义组件过滤器7.组件扫描的其他特性7.1组合使用组件扫描8.组件扫描的组件名称生成8.1Spring是如何生成默认bean名称的（源码分析）8.2生成默认bean名称的特殊情

一文巩固Spring MVC的Bean加载机制

目录一、什么是SpringMVC的Bean二、SpringMVC的Bean加载机制三、SpringMVC如何动态装载Bean一、什么是SpringMVC的Bean在SpringMVC中，Bean指的是在SpringIoC容器中创建和管理的对象。这些对象可以是普通的Java类，也可以是服务层组件、数据访问对象（DAO）或

热文推荐
  1. 揭秘：Wasserstein GAN与梯度惩罚（WGAN-GP）

    一、说明什么是梯度惩罚？为什么它比渐变裁剪更好？如何实施梯度惩罚？在提起GAN对抗网络中，就不能避免Wasserstein距离的概念，本篇为系列读物，目的是揭示围绕Wasserstein-GAN建模的一些重要概念进行探讨。图1（左）使用配重裁剪时的梯度范数要么爆炸，要么消失，不使用GP。（右）与GP不同，权重裁剪将权重

  2. C++——vector（3）

    作者：几冬雪来时间：2023年9月20日内容：C++部分——vector内容讲解目录前言：erase：erase和insert总结：resize：深拷贝：赋值：结尾：前言：在上一篇博客中我们更加介绍了vector的定位还特别的介绍了它的几个常用接口，也对接口的使用方法，注意事项，可能出错的地方以及接口的拓展都多多少少有

  3. HTTP 面试知识点提炼

    前言由于很多小伙伴看了《普通人如何进大厂》这篇文章对我的笔记比较感兴趣，所以我花时间整理提炼了一下跟大家分享，不保证内容完全正确，仅供参考哈其他笔记传送门Js基础总结Vue重点知识总结Webpack核心总结Http网络知识React核心设计模式算法从输入URL到页面加载完成，发生了什么？1、HTTP请求准备阶段构建请求

  4. Linux查看哪些进程占用的系统 buffer/cache 较高 (hcache，lsof）命令

    1、什么是buffer/cache？buffer/cache其实是作为服务器系统的文件数据缓存使用的，尤其是针对进程对文件存在read/write操作的时候，所以当你的服务进程在对文件进行读写的时候，Linux内核为了提高服务的读写速度，则将会把文件放在此处的buffer/cache中进行缓存使用，由于Linux服务的

  5. ICCV 2023 | MPI-Flow：从单视角构建的多平面图像中学习光流

    ICCV2023|MPI-Flow：从单视角构建的多平面图像中学习光流引言：主要贡献：Motivation：算法细节：OpticalFlowDataGenerationIndependentObjectMotionsDepth-AwareInpainting实验结果：来源：ICCV2023作者：YingpingLian

  6. linux搭建单机ES，集成ik分词器，文本抽取，Kibana可视化平台

    Elasticsearch单机（Linux）准备工作第一项：创建运行Elasticsearch和Kibana专用的普通用户，因为elasticsearch和kibana不允许使用root用户启动，所以需要创建新用户启动。linux用root权限创建一个用户赋权即可，注意权限要给足第二项（启动没有报相关错误此项可以不做调

  7. Visual Studio 更新：远程文件管理器

    VisualStudio中的远程文件管理器可以用来访问远程机器上的文件和文件夹，通过VisualStudio自带的连接管理器，可以实现不离开开发环境直接访问远程系统，这确实十分方便。自从此功能发布以来，VS开发团队努力工作，今天又为我们带来了新的功能，让我们来看看。>>请移步至topomel.com以查看图片<<背景知

  8. ARM64汇编基础

    ARM64汇编基础主要内容到目前为止，大部分的移动设备都是64位的arm架构，一直想抽个时间系统学习下，这个周末就专门来学习下。毕竟两天的时间，也只是简单的入门了解下，为后续工作和学习打下基础。本次学习的主要内容包括寄存器、指令系统以及堆栈函数相关的知识，了解这些知识后，后面就可以扩展进行学习了。话不多说，接下来介绍这

  9. 【Ubantu 18.04】配置sh脚本开机启动

    一、services服务脚本编写1、进入服务管理目录，创建service文件sudonano/etc/systemd/system/ads.service例如文件名为：ads.service，文件内容如下：[Unit]Description=AdsServiceAfter=network.target[Service]