AVL树的插入和删除

一.AVL树的四种旋转方式

 

 

以上是AVL树插入和删除时需要用到的四种旋转方式。为什么要旋转？因为树不平衡了,通过旋转使其再次平衡。 但是上面的四副图在旋转前就是平衡的，所以这样的旋转是没有意义的，重点在于理解旋转的方法。下面的插入和删除操作会用到这四种方法，都是在这四副图的基础上变化。

具体如何选择旋转方法呢？记住以下几个技巧：

  1. 当某个结点(parent)的平衡因子绝对值大于1时(即2或-2)时，需要进行旋转
  2. child永远指向parent高的那颗子树
  3. parent和child都是左边高时右单旋，都是右边高时左单旋
  4. child左边高，parent右边高时进行右左单旋；child右边高，parent左边高时进行左右单旋
  5. 当进行插入和删除操作后，只可能影响被操作结点到根的路径上的所有结点的平衡因子，其余结点不受影响。
  6. 一个结点的平衡因子是否会受到影响，关键看它的子树高度是否发生变化。

二.AVL树的插入操作

parent和child都是左边高，右单旋，插入前和旋转后，这颗树的高度不变(h+1)，故旋转后不用向上更新平衡因子

 parent和child都是右边高，左单旋，插入前和旋转后，这颗树的高度不变(h+1)，故旋转后不用向上更新平衡因子

 parent右边高，child左边高，右左单旋，插入前和旋转后，这颗树的高度不变(h+2)，故旋转后不用向上更新平衡因子

 parent左高，child右边高，左右单旋，插入前和旋转后，这颗树的高度不变(h+2)，故旋转后不用向上更新平衡因子

三.AVL树的删除操作

 parent左边高，child两边一样高，右单旋。插入前和旋转后，这棵树的高度不变(h+2)，故旋转后不用向上更新平衡因子

parent和child都是左边高，右单旋。插入前和旋转后，这棵树的高度发生变化(h+2->h+1)，故旋转后需要向上更新平衡因子

parent右边高，child两边一样高，左单旋。插入前和旋转后，这棵树的高度不变(h+2)，故旋转后需要向上更新平衡因子

parent和child都是右边高，左单旋。插入前和旋转后，这棵树的高度发生变化(h+2->h+1)，故旋转后需要向上更新平衡因子

 parent左边高，child右边高，左右双旋。插入前和旋转后，这棵树的高度发生变化(h+2->h+1)，故旋转后需要向上更新平衡因子

 parent右边高，child左边高，右左双旋。插入前和旋转后，这棵树的高度发生变化(h+2->h+1)，故旋转后需要向上更新平衡因子

四.参考代码 

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

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

template <class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	AVLTree() = default;
	
	//查找
	Node* find(const K& key)
	{
		Node* cur = _root;
		
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				return cur;
			}
			else if (key > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else
			{
				cur = cur->_left;
			}
		}
		return nullptr;
	}

	//插入
	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			//printf("插入根结点%d\n", kv.first);
			_root = new Node(kv);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_kv == kv)
			{
				return false;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				parent = cur;
				cur = cur->_left;
			}
		}
		//找到空结点了，开始插入
		cur = new Node(kv);
		cur->_parent = parent;
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		
		//以parent为起点，向上更新平衡因子，必要时进行调整
		//一个结点的平衡因子是否被影响，只需看它的子树高度是否发生变化
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			
			if (parent->_bf == 0)//-1->0或者1->0,说明以parent为根结点的这颗树的高度没有变化,不用向上更新平衡因子了
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)//说明以parent为根结点的这颗子树高度+1，需要继续向上跟新平衡因子
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)//parent这个结点已经不平衡了，需要调整
			{
				if (cur->_bf == 1 && parent->_bf == 2)
				{
					//左单旋--parent和cur都是右边高
					rotateL(parent);
				}
				else if (cur->_bf == -1 && parent->_bf == -2)
				{
					//右单旋--parent和cur都是左边高
					rotateR(parent);
				}
				else if (cur->_bf == -1 && parent->_bf == 2)
				{
					//右左双旋--cur左边高，parent右边高
					rotateRL(parent);
				}
				else if (cur->_bf == 1 && parent->_bf == -2)
				{
					//左右双旋
					rotateLR(parent);
				}
				break;//调整后不用往上更新平衡因子了，因为以parent为根结点的这棵树插入前高度和调整后高度一样
			}
			else
			{
				cout << "平衡因子出错" << endl;
				assert(false);
			}
		}

		return true;
		
	}

	bool erase(const K& key)
	{
		//先找到它
		Node* cur = find(key);
		if (cur == nullptr)
		{
			return false;
		}
		if (key == 9798)
		{
			int i = 0;
		}
		//如果cur有两个孩子，则用右子树的最左结点替换它
		if (cur->_left && cur->_right)
		{
			Node* target = cur->_right;
			while (target->_left)
			{
				target = target->_left;
			}
			swap(cur->_kv, target->_kv);
			cur = target;
		}
		//删除cur
		Node* parent = cur->_parent;
		Node* lChild = cur->_left;
		Node* rChild = cur->_right;
		Node* child = nullptr;
		//1.cur右孩子为空
		if (rChild == nullptr)
		{
			child = lChild;
		}
		//2.cur左孩子为空
		else if (lChild == nullptr)
		{
			child = rChild;
		}
		else
		{
			cout << "替换结点有误" << endl;
			assert(false);
		}

		//parent和child构建关系
		//1.被删的cur是根结点
		if (parent == nullptr)
		{
			_root = child;
		}
		//2.被删的是一个普通结点，cur的父亲不为空
		else
		{
			if (cur == parent->_left)
			{
				parent->_left = child;
				parent->_bf++;
			}
			else
			{
				parent->_right = child;
				parent->_bf--;
			}
		}
		if (child)
		{
			child->_parent = parent;
		}
		
		delete cur;


		//开始更新平衡因子
		bool flag = false;
		while (parent)
		{
			//第一次进来不更新平衡因子
			if (flag)
			{
				if (child == parent->_left)
				{
					parent->_bf++;
				}
				else
				{
					parent->_bf--;
				}
			}
			flag = true;

			if (parent->_bf == 1 || parent->_bf == -1)//还是平衡的，树高度没有变，不需要向上处理
			{
				break;
			}
			else if (parent->_bf == 0)//高那颗子树删除了一个结点，树的高度降低，继续向上更新
			{
				child = parent;
				parent = parent->_parent;
 			}
			else if (parent->_bf == 2 || parent->_bf == -2)//不平衡了，需要调整
			{
				//child指向高的那颗子树
				if (parent->_bf > 0)
				{
					child = parent->_right;
				}
				else
				{
					child = parent->_left;
				}
				assert(child);

				Node* grandpa = parent->_parent;//提前记录parent的父节点，否则旋转后就找不到了
				//child和parent都是同一边高，或者child两边一样高，单旋即可
				if (child->_bf * parent->_bf >= 0)
				{
					int bf = child->_bf;
					if (parent->_bf == 2)
					{
						rotateL(parent);
						if (bf == 0)
						{
							parent->_bf = 1;
							child->_bf = -1;
						}
					}
					else
					{
						rotateR(parent);
						if (bf == 0)
						{
							parent->_bf = -1;
							child->_bf = 1;
						}
						
					}
					
					//判断是否还需要向上更新平衡因子
					//--当child原来的_bf = 0时parent这颗树删除前和调整后高度不变
					if (bf == 0)
					{
						break;
					}
					child = parent->_parent;
					parent = grandpa;
					
				}
				//parent和child的平衡因子符号不同--需要双旋
				else
				{
					if (parent->_bf == 2 && child->_bf == -1)
					{
						rotateRL(parent);
					}
					else if (parent->_bf == -2 && child->_bf == 1)
					{
						rotateLR(parent);
					}
					child = parent->_parent;
					parent = grandpa;
				}
			}
			else
			{
				cout << "平衡因子出错" << endl;
				assert(false);
			}
		}

		return true;
	}
	
	void inOrder()
	{
		_inOrder(_root);
	}
	
	bool isBalance()
	{
		return _isBalance(_root);
	}

	int height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		return max(height(root->_left), height(root->_right)) + 1;
	}

protected:
	void rotateL(Node* parent)
	{
		Node* grandfather = parent->_parent;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		//grandfather和subR
		subR->_parent = grandfather;
		if (grandfather == nullptr)
		{
			_root = subR;
		}
		else
		{
			parent == grandfather->_left ? grandfather->_left = subR : grandfather->_right = subR;
		}

		//parent和subRL
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		//subR和parent
		subR->_left = parent;
		parent->_parent = subR;

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

	void rotateR(Node* parent)
	{
		Node* grandpa = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		
		//grandpa和subL
		subL->_parent = grandpa;
		if (grandpa == nullptr)
		{
			_root = subL;
		}
		else
		{
			parent == grandpa->_left ? grandpa->_left = subL : grandpa->_right = subL;
		}
		//parent和subLR
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		//subL和parent
		parent->_parent = subL;
		subL->_right = parent;

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

	void rotateRL(Node* parent)//--本质是将subRL作为根结点，parent和subR成为它的左右护法，并将subRL的左右子树分给它们
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		rotateR(subR);
		rotateL(parent);
		//更新平衡因子
		if (bf == 0)//subRL自己就是新插入的结点
		{
			subR->_bf = subRL->_bf = parent->_bf = 0;
		}
		else if (bf == 1)//在subRL的右子树插入结点
		{
			subR->_bf = subRL->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)//在subRL的左子树插入结点
		{
			subRL->_bf = parent->_bf = 0;
			subR->_bf = 1;
		}
	}
	Node* _root = nullptr;

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

		//更新平衡因子
		if (bf == 0)//subLR自己就是新插入的结点
		{
			subLR->_bf = parent->_bf = subL->_bf = 0;
		}
		else if (bf == -1)//在subLR左子树插入结点
		{
			subLR->_bf = subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)//在subLR右子树插入结点
		{
			subLR->_bf = parent->_bf = 0;
			subL->_bf = -1;
		}
	}

	void _inOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_inOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << " ";
		_inOrder(root->_right);
	}

	bool _isBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftHeight = height(root->_left);
		int rightHeight = height(root->_right);
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << root->_kv.first << "平衡因子出错:实际" << rightHeight - leftHeight << "记录" << root->_bf << endl;
			return false;
		}

		return abs(leftHeight - rightHeight) <= 1
			&& _isBalance(root->_left)
			&& _isBalance(root->_right);
	} 
};

一些说明：

四个旋转函数包含了平衡因子的调节，这是以插入时的四种情况为准(因为我是先实现的插入)，删除有几种情况平衡因子还需要自己调节。建议大家实现旋转函数时不包含平衡因子调节。

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

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

相关文章

Nexus的Maven私有仓库搭建

Nexus的Maven私有仓库搭建

Nexus的maven私有仓库搭建 一、了解 maven仓库设置 默认设置 其中&#xff1a; maven-central: 预定义的代理Maven Central仓库&#xff0c;它包含了大量的开源Java依赖包。maven-public: 存储库是一个组合存储库&#xff0c;它包含了maven-releases和maven-snapshots存储库…
阅读更多...
【MySQL系列】 第三章 · 函数

【MySQL系列】 第三章 · 函数

写在前面 Hello大家好&#xff0c; 我是【麟-小白】&#xff0c;一位软件工程专业的学生&#xff0c;喜好计算机知识。希望大家能够一起学习进步呀&#xff01;本人是一名在读大学生&#xff0c;专业水平有限&#xff0c;如发现错误或不足之处&#xff0c;请多多指正&#xff0…
阅读更多...
支付宝支付==沙盒

支付宝支付==沙盒

地址 登录 - 支付宝 可以看到有买家和卖家账户了 完整代码 https://gitee.com/hebian1994/demo-zhifubao.git
阅读更多...
动作活体检测能力支持自定义扫描动作，开发者接入更高效

动作活体检测能力支持自定义扫描动作，开发者接入更高效

随着人脸识别技术在金融、医疗等多个领域的加速落地&#xff0c;网络安全、信息泄露等问题愈为突出&#xff0c;用户对应用稳定性和安全性的要求也更为严格。 华为机器学习服务的动作活体检测能力&#xff0c;支持实时捕捉人脸&#xff0c;根据用户配合做动作可以判断是真实活…
阅读更多...
Centos7.9用rancher来快速部署K8S

Centos7.9用rancher来快速部署K8S

什么是 Rancher&#xff1f; Rancher 是一个 Kubernetes 管理工具&#xff0c;让你能在任何地方和任何提供商上部署和运行集群。 Rancher 可以创建来自 Kubernetes 托管服务提供商的集群&#xff0c;创建节点并安装 Kubernetes&#xff0c;或者导入在任何地方运行的现有 Kube…
阅读更多...
H5游戏源码分享-网页版2048小游戏

H5游戏源码分享-网页版2048小游戏

H5游戏源码分享-网页版2048小游戏 玩过的都懂 <!DOCTYPE html> <html> <head><meta charset"utf-8"><title>分享2048到朋友圈&#xff0c;将免费参加南山郡8.17号啤酒狂欢节&#xff01;</title><link href"style/main…
阅读更多...
Windows配置IP-SAN（iSCSI）

Windows配置IP-SAN（iSCSI）

之前写了《Linux配置IP-SAN&#xff08;iSCSI&#xff09;》&#xff0c;现在简单记录Windows配置IP-SAN&#xff08;iSCSI&#xff09;&#xff0c;基本过程都是一样的。一些原理请参考《Linux配置IP-SAN&#xff08;iSCSI&#xff09;》&#xff0c;更详细一些。 目录 一、确…
阅读更多...
Spring核心

Spring核心

Spring Framework Spring的两个核心IOC控制反转IOC容器依赖注入DIIOC容器实现注解管理BeanBean对象定义Bean对象获取 AOP面向切面编程 添加依赖入门案例注解通过Spring创建Java bean对象 xml管理Bean案例main下创建bean.XMl文件 DI依赖注入案例创建Spring配置文件 bean-di.xml …
阅读更多...
低成本毫米波雷达系统设计与研发

低成本毫米波雷达系统设计与研发

毫米波雷达系统在汽车、工业感知和安全领域等多个领域有着广泛的应用。然而&#xff0c;传统毫米波雷达系统的高昂成本限制了其普及。本文介绍了一种低成本毫米波雷达系统的设计与研发&#xff0c;旨在降低成本的同时保持系统性能。 毫米波雷达工作在30到300 GHz的频率范围内&a…
阅读更多...
Linux常见指令

Linux常见指令

文章目录 一. 操作系统简述二. Linux 下基本指令01. ls 指令补充知识点 1 (关于路径)02. pwd 指令03. cd 指令04. touch 指令05. mkdir 指令06. rmdir 指令 && rm 指令07. man 指令补充知识点 2 (开发三种环境)08. cp 指令09. mv 指令10. alise 指令补充知识点 3 (命令…
阅读更多...
No204.精选前端面试题，享受每天的挑战和学习

No204.精选前端面试题，享受每天的挑战和学习

🤍 前端开发工程师（主业）、技术博主（副业）、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…
阅读更多...
Linux--gdb的使用

Linux--gdb的使用

文章目录 release版本和Debug版本GDB一般步骤常用命令 release版本和Debug版本 Release版本&#xff1a;该版本用于发布的最终产品版本。它会进行各种优化&#xff0c;以提高代码的执行效率和运行速度。编译时通常会选择较高的优化级别&#xff0c;此外&#xff0c;该版本还会进…
阅读更多...
【C++初阶（八）】C/C++内存管理详解

【C++初阶（八）】C/C++内存管理详解

本专栏内容为&#xff1a;C学习专栏&#xff0c;分为初阶和进阶两部分。 通过本专栏的深入学习&#xff0c;你可以了解并掌握C。 &#x1f493;博主csdn个人主页&#xff1a;小小unicorn ⏩专栏分类&#xff1a;C &#x1f69a;代码仓库&#xff1a;小小unicorn的代码仓库&…
阅读更多...
黑马点评回顾 redis实现共享session

黑马点评回顾 redis实现共享session

文章目录 传统session缺点整体访问流程代码实现生成验证码登录 问题具体思路 传统session缺点 传统单体项目一般是把session存入tomcat&#xff0c;但是每个tomcat中都有一份属于自己的session,假设用户第一次访问第一台tomcat&#xff0c;并且把自己的信息存放到第一台服务器…
阅读更多...
typhonjs-escomplex 代码可读性 可维护度探索

typhonjs-escomplex 代码可读性 可维护度探索

目前市面上的前端代码质量评分中的代码可维护度是大都是基于 typhonjs-escomplex 这个库扫描而来&#xff0c;但是这个库的官方文档并没有介绍相关指标数据的计算规则&#xff0c;不知道规则如何提升指标数据呢&#xff1f;所以本文对 typhonjs-escomplex 源码进行探索&#xf…
阅读更多...
Linux操作系统使用及C高级编程-D5Linux shell命令(进程管理、用户管理)

Linux操作系统使用及C高级编程-D5Linux shell命令(进程管理、用户管理)

进程管理 查看进程ps 其中ps -eif可显示父进程 实时查看进程top 按q退出 树状图显示进程pstree 以父进程&#xff0c;子进程以树状形式展示 发送信号kill kill -l&#xff1a;查看都有哪些信号 9&#xff1a;进程终止 kill不指定信号&#xff0c;默认发送的是15信号SIGT…
阅读更多...
接口自动化测试，必须要掌握post提交数据的这4种方式

接口自动化测试，必须要掌握post提交数据的这4种方式

我们都知道POST一般用于向服务端提交数据&#xff0c;POST提交数据的4种格式即Content-Type的4种形式&#xff0c;尤其注意每种格式中http发送请求时body中数据的格式。4种形式分别是&#xff1a; 一、application/x-www-form-urlencoded&#xff1a;URL encoded。 二、multi…
阅读更多...
【C++】：STL——标准模板库介绍 || string类

【C++】：STL——标准模板库介绍 || string类

&#x1f4da;1.什么是STL STL(standard template libaray-标准模板库)&#xff1a;是C标准库的重要组成部分&#xff0c;不仅是一个可复用的组件库&#xff0c;而且 是一个包罗数据结构与算法的软件框架 &#x1f4da;2.STL的版本 原始版本 Alexander Stepanov、Meng Lee 在…
阅读更多...
Linux--makefile

Linux--makefile

一、makefile的作用 makefile是一个文件&#xff0c;是围绕依赖关系和依赖方法的自动化编译工具 一个工程中的源文件有很多&#xff0c;按照不同的类型、功能、模块放在不同的目录中。而makefile定义了一系列的规则来指定&#xff0c;那些文件需要先编译&#xff0c;那些文件…
阅读更多...
[文件读取]Druid 任意文件读取 （CVE-2021-36749）

[文件读取]Druid 任意文件读取 （CVE-2021-36749）

1.1漏洞描述 漏洞编号CVE-2021-36749漏洞类型文件读取漏洞等级⭐⭐⭐漏洞环境VULFOCUS攻击方式 描述: 由于用户指定 HTTP InputSource 没有做出限制&#xff0c;可以通过将文件 URL 传递给 HTTP InputSource 来绕过应用程序级别的限制。攻击者可利用该漏洞在未授权情况下&…
阅读更多...
最新文章

Copyright @ 2022~2023