STL容器之map和set的补充AVL树

一、AVL树

​ 不同搜索的对比：1.暴力搜索时间复杂度是O(N)；2.二分查找的时间复杂度是O(lgN)，但是伴随着有序，插入删除挪动数据的成本极高；3.二叉搜索的时间复杂度是高度次数，极端场景会退化为类似链表时间复杂度是O(N)/O(lgN)；4.平衡二叉搜索树；5.多叉平衡搜素树；6.哈希表快速搜索；

​ 平衡二叉搜索树有avl树和红黑树；

1.1概念

​ AVL树又叫做高度平衡二叉搜索树；

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

​ AVL树要不是空树，要不然就是：1.左右子树都是AVL树，平衡因子(右子树高度减去左子树高度)的绝对值小于等于1；

​ 满二叉树就是最平衡的AVL树；

1.2AVL树的模拟实现

1.2.1插入原理

在这里插入图片描述

​ 先创建搜索二叉树，然后更新平衡因子，然后解决平衡错误(旋转解决)；

​ 1.左子树插入会使得父亲的平衡因子–，右子树会使得父亲的平衡因子++，平衡因子只会影响祖先；

​ 2.平衡因子变为0，说明树的高度没有发生变化，其他祖先的平衡因子不需要发生变化，变为正负一才需要，沿着祖先路径，parent和cur向上调整；

​ 3.插入一个节点是平衡因子默认就是0；

​ 4.若平衡因子是2或者-2，就不平衡了，需要旋转，旋转要注意：1.保持子树是搜索树；2.变成平衡树且降低整棵树的高度；即左单旋，对于右子树过高，向左旋转，使得parent->right=cur->left,cur->left=parent，强行让parent 节点向下走一截，旋转之后的高度相较于插入之前是没有变化的。在旋转的过程中除了更新平衡因子，还需要更新parent_。右单旋类似；

​ 5更新到平衡因子为0或者旋转结束或者更新到根节点就插入结束；

旋转原理：插入前平衡因子是1/-1；

在这里插入图片描述

h是子树的高度，h是1或者0和之前是一样的，如果h是2，则a、b子树可以是：

在这里插入图片描述

在这里插入图片描述

但是c只能是第三种，因为第1和第2种都不会影响到30和60节点的平衡因子；一共有36种可能的插入情况。即无法穷尽，但是核心规则是不变的。

双旋

​ 当parent与cur的平衡因子为异号时，即是折线就是双旋，否则就是直线单旋；

右左双旋：

在这里插入图片描述

​ h=0，就是简单的直线；h=1，就是在60的左右叶子节点插入都会使得parent异常；h=2，a和d可以是上述任意三种情况，bc是一个节点。

​ 先90为旋转点进行右旋，然后30为旋转点进行左旋。即第一次旋转变成直线，左单旋，第二次单旋变成平衡。要注意双旋之后要更新平衡因子。

​ 观察发现双旋的结果本质就是60的左给30，右给90并且30，90，做了60的左右。

​ 更新平衡因子分三种情况，1、插入元素后，对于30、60、90，60的平衡因子为-1，说明在60的左子树插入，最终会使得60的右的平衡因子为1，其他为0；2、60平衡因子为1，则60左的平衡因子为-1；3、60的平衡因子为0，则60左右的平衡因子为0。

​ 但是双旋存在问题。学会使用自己写一个辅助程序帮助调试。对于循环可以if等于具体的值来打断点调试。

#pragma once

#include <cassert>

namespace AvlTree
{
	template <class K, class V>
	struct AVLTreeNode
	{
		// 构造函数
		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_;
	};
	template <class K, class V>
	class AVLTree
	{
		// 内嵌类型
		typedef AVLTreeNode<K, V> node;

	public:
		// 默认构造函数
		AVLTree() : root_(nullptr) {}

	public:
		// 普通成员函数
		void rotatel(node *parent);
		void rotater(node *parent);
		void rotaterl(node *parent);
		void rotatelr(node *parent);
		bool insert(const pair<K, V> &kv);
		int height(node *root);
		bool isavltree()
		{
			return _isavltree(root_);
		}
		void inorder()
		{
			_inorder(root_);
		}

	private:
		// 私有成员
		void _inorder(node *root);
		bool _isavltree(node *root);
		node *root_;
	};
	template <class K, class V>
	void AVLTree<K, V>::rotatel(node *parent)
	{
		node *cur = parent->right_;
		node *curleft = cur->left_;
		parent->right_ = curleft;
		node *ppnode = parent->parent_;
		if (curleft)
			curleft->parent_ = parent;
		parent->parent_ = cur;
		cur->left_ = parent;
		parent->bf_ = 0;
		cur->bf_ = 0;

		if (parent == root_)
		{
			root_ = cur;
			cur->parent_ = nullptr;
		}
		else
		{
			if (ppnode->left_ == parent)
			{
				ppnode->left_ = cur;
			}
			else
			{
				ppnode->right_ = cur;
			}
			cur->parent_ = ppnode;
		}
	}
	template <class K, class V>
	void AVLTree<K, V>::rotater(node *parent)
	{
		node *cur = parent->left_;
		node *curright = cur->right_;
		node *ppnode = parent->parent_;
		parent->left_ = curright;
		cur->right_ = parent;
		if (curright)
			curright->parent_ = parent;
		parent->parent_ = cur;
		parent->bf_ = 0;
		cur->bf_ = 0;

		if (parent == root_)
		{
			root_ = cur;
			cur->parent_ = nullptr;
		}
		else
		{
			if (ppnode->left_ == parent)
			{
				ppnode->left_ = cur;
			}
			else
			{
				ppnode->right_ = cur;
			}
			cur->parent_ = ppnode;
		}
	}
	template <class K, class V>
	void AVLTree<K, V>::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_ = 1;
			curleft->bf_ = 0;
			parent->bf_ = 0;
		}
		else if (bf == 1)
		{
			parent->bf_ = -1;
			cur->bf_ = 0;
			curleft->bf_ = 0;
		}
		else
		{
			assert(false);
		}
	}
	template <class K, class V>
	void AVLTree<K, V>::rotatelr(node *parent)
	{
		// 更新平衡因子
		node *cur = parent->left_;
		node *curright = cur->right_;
		int bf = curright->bf_;

		rotatel(parent->left_);
		rotater(parent);
		if (bf == 0)
		{
			cur->bf_ = 0;
			curright->bf_ = 0;
			parent->bf_ = 0;
		}
		else if (bf == -1)
		{
			cur->bf_ = 0;
			curright->bf_ = 0;
			parent->bf_ = 1;
		}
		else if (bf == 1)
		{
			parent->bf_ = 0;
			cur->bf_ = -1;
			curright->bf_ = 0;
		}
		else
		{
			assert(false);
		}
	}
	template <class K, class V>
	bool AVLTree<K, V>::insert(const pair<K, V> &kv)
	{
		if (root_ == nullptr)
		{
			root_ = new node(kv);
			return true;
		}
		node *cur = root_;
		node *parent = cur;
		while (cur)
		{
			if (kv.first > cur->kv_.first)
			{
				parent = cur;
				cur = cur->right_;
			}
			else if (kv.first < cur->kv_.first)
			{
				parent = cur;
				cur = cur->left_;
			}
			else
			{
				return false;
			}
		}
		cur = new node(kv);
		if (kv.first > parent->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_)
			{
				break;
			}
			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);
					break;
				}
				else if (parent->bf_ == -2 && cur->bf_ == -1)
				{
					// 右单旋
					rotater(parent);
					break;
				}
				else if (parent->bf_ == 2 && cur->bf_ == -1)
				{
					// 右左双旋
					rotaterl(parent);
					break;
				}
				else if (parent->bf_ == -2 && cur->bf_ == 1)
				{
					// 左右双旋
					rotatelr(parent);
					break;
				}
				else
				{
					assert(false);
				}
			}
			else
			{
				assert(parent->bf_ <= 2 && parent->bf_ >= -2);
			}
		}
		return true;
	}
	template <class K, class V>
	int AVLTree<K, V>::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;
	}
	template <class K, class V>
	bool AVLTree<K, V>::_isavltree(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 << ":" << root->kv_.second << ":" << root->bf_ << endl;
			return false;
		}
		return abs(rightheight - leftheight) < 2 && _isavltree(root->left_) && _isavltree(root->right_);
	}
	template <class K, class V>
	void AVLTree<K, V>::_inorder(node *root)
	{
		if (root == nullptr)
		{
			return;
		}
		_inorder(root->left_);
		cout << root->kv_.first << ":" << root->kv_.second << endl;
		_inorder(root->right_);
	}
}

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

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

相关文章

栈和队列之队列

栈和队列之队列

1.队列 1.1队列的概念 队列&#xff1a;只允许在一端进行插入数据操作&#xff0c;在另一端进行删除数据操作的特殊线性表&#xff0c;队列具有先进先出 FIFO(First In First Out) 入队列&#xff1a;进行插入操作的一端称为队尾 出队列&#xff1a;进行删除操作的一端称为队…
阅读更多...
android开发框架mvp，Android面试心得必备技能储备详解

android开发框架mvp，Android面试心得必备技能储备详解

面试复习路线图 我之前复习&#xff0c;大多都在20点以后&#xff0c;因为晚上比较能集中注意力&#xff0c;制定一个学习计划&#xff0c;切勿零散的复习&#xff0c;最好是系统的复习&#xff0c;才能胜却在握 主要内容如下&#xff1a; BAT的面试题目相关性能优化相关相关…
阅读更多...
日本极致产品力|与日本所有食物百搭，年销量2亿箱的啤酒品牌

日本极致产品力|与日本所有食物百搭，年销量2亿箱的啤酒品牌

摘要&#xff1a;《极致产品力》日本深度研学,可以帮助企业找产品、找方向、找方法,在日本终端市场考察中洞悉热销产品背后的成功逻辑,了解最新最前沿的产品趋势和机会。结合日本消费趋势中国转化的众多经验,从品牌、包装、卖点、技术和生产工艺等多方面寻找中口市场的解决方案…
阅读更多...
Echarts+D3气泡图

Echarts+D3气泡图

EchartsD3气泡图&#xff08;相邻效果&#xff0c;气泡之间不叠加&#xff09; <template><div ref"chart" style"width: 500px; height: 500px"></div> </template><script setup> import * as echarts from echarts/core …
阅读更多...
准确率达 91.74%！东南大学提出光伏电池缺陷检测模型，首次引入神经结构搜索

准确率达 91.74%！东南大学提出光伏电池缺陷检测模型，首次引入神经结构搜索

乘着从全球吹来的「绿色发展、低碳转型」东风&#xff0c;光伏 (photovoltaic, PV) 产业自进入 21 世纪以来&#xff0c;便以令世人惊叹的速度迅猛向前发展。在我国&#xff0c;光伏发电更是呈现出前所未有的活力。根据 2023 年 4 月国家能源局公布的当年 1-3 月份全国电力工业…
阅读更多...
【IO】进程间通信

【IO】进程间通信

A程序代码&#xff1a; #include <stdio.h> #include <sys/types.h> #include <sys/stat.h> #include <unistd.h> #include <errno.h> #include <fcntl.h> #include <string.h> int main(int argc, const char *argv[]) {if(mkfifo…
阅读更多...
Redis缓存【重点】

Redis缓存【重点】

参考链接 https://xiaolincoding.com/redis/cluster/cache_problem.html#%E7%BC%93%E5%AD%98%E9%9B%AA%E5%B4%A9 目录 缓存雪崩大量数据同时过期Redis 故障宕机 缓存击穿第一种方案&#xff0c;非法请求的限制第二种方案&#xff0c;缓存空值或者默认值第三种方案&#xff0c;使…
阅读更多...
Docker中使用nginx-rtmp推拉网络摄像头视频流

Docker中使用nginx-rtmp推拉网络摄像头视频流

前言&#xff1a; 该部分比较麻烦&#xff0c;闹腾了好久&#xff08;ffmpeg推拉流没学过&#xff0c;事实证明依葫芦画瓢是不行滴&#xff0c;后面有时间再学吧&#xff09;&#xff0c;后来借助chatGPT勉强解决&#xff0c;但不是很懂。因个人能力有限&#xff0c;只复述操作…
阅读更多...
合泰HT66F2390----定时器中断学习笔记

合泰HT66F2390----定时器中断学习笔记

前言 无需多言 直接开始定时器中断 的学习 通过上次的PWM学习&#xff0c;上次用的是周期型TM定时器模块 这次使用标准型TM定时器模块&#xff08;STM&#xff09; 代码 #include <HT66F2390.h>void Timer0_Init(void){_stm0c0 0b00001000;_stm0c1 0b11000001;_stm…
阅读更多...
Vmware虚拟机安装openEuler 20.03 LTS（openEuler20.03）

Vmware虚拟机安装openEuler 20.03 LTS（openEuler20.03）

文章目录 vmware虚拟机安装openEuler 20.03 LTS安装硬件设备&#xff08;略&#xff09;安装OS镜像下载镜像版本发布说明开始安装&#xff08;vmware虚拟机&#xff09;安装操作系统必要操作关闭防火墙设置selinux为宽容模式系统内核问题禁用系统内核更新 ~~禁用yum update和dn…
阅读更多...
Ubuntu18.04运行ORB-SLAM3

Ubuntu18.04运行ORB-SLAM3

ORB-SLAM3复现(ubuntu18) 文章目录 ORB-SLAM3复现(ubuntu18)1 坐标系与外参Intrinsic parameters2 内参Intrinsic parameters2.1 相机内参① 针孔模型Pinhole② KannalaBrandt8模型③ Rectified相机 2.2 IMU内参 3 VI标定—外参3.1 Visual calibration3.2 Inertial calibration…
阅读更多...
构造pop链

构造pop链

反序列化视频笔记 第一步&#xff1a;找到目标触发echo调用$flag 第二步&#xff1a;触发_invoke函数调用appeng函数$varflag.php&#xff08;把对象当成函数&#xff09; 第三步&#xff1a;给$p赋值为对象&#xff0c;即function成为对象Modifier却被当成函数调用&#xff…
阅读更多...
基于springboot+vue的校园网上店铺

基于springboot+vue的校园网上店铺

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…
阅读更多...
Android开发者必看，我的移动开发春季历程

Android开发者必看，我的移动开发春季历程

热修复介绍 1.开发流程 当项目出现紧急bug时&#xff0c;传统的开发流程是发布新版本&#xff0c;引导用户覆盖安装。抛开平台审核上线的时间不说&#xff0c;一天重复下载安装至少两次的用户体验是很差的。而热修复的出现完美解决了这个问题&#xff0c;用户在收到服务器推送…
阅读更多...
概要了解postman、jmeter 、loadRunner

概要了解postman、jmeter 、loadRunner

postman还蛮好理解的&#xff0c;后续复习的话着重学习关联接口测试即可&#xff0c;感觉只要用几次就会记住&#xff1a; 1 从接口的响应结果当中提取需要的数据 2 设置成环境变量/全局变量&#xff08;json value check 、set environment para 3写入到下一个接口的请求数据中…
阅读更多...
python三剑客之一——Numpy

python三剑客之一——Numpy

温故而知新&#xff0c;借着工作需要用到Numpy的机会重新学习一遍Numpy。 Numpy是一个运行速度非常快的数学库&#xff0c;主要用于数组计算&#xff0c;包含如下&#xff1a; 一个强大的N维数组对象ndarray【Nd&#xff08;Dimension维度&#xff09;array】 广播功能函数 整…
阅读更多...
找不到msvcr100.dll怎么办，多种解决方法快速修复msvcr100.dll问题

找不到msvcr100.dll怎么办，多种解决方法快速修复msvcr100.dll问题

当计算机系统中关键文件msvcr100.dll丢失时&#xff0c;可能会引发一系列运行问题和故障现象。msvcr100.dll是Microsoft Visual C Redistributable Package的一部分&#xff0c;对于许多基于Windows的应用程序正常运行至关重要。由于msvcr100.dll是许多应用程序运行所必需的动态…
阅读更多...
22.基于springboot + vue实现的前后端分离-汽车票网上预定系统（项目 + 论文PPT）

22.基于springboot + vue实现的前后端分离-汽车票网上预定系统（项目 + 论文PPT）

项目介绍 系统是一个B/S模式系统&#xff0c;采用Spring Boot框架&#xff0c;MySQL 数据库设计开发&#xff0c;充分保证系统的稳定性。系统具有界面清晰、操作简单&#xff0c;功能齐全的特点&#xff0c;使得汽车票网上预订系统管理工作系统化、规范化。本系统的使用使管理人…
阅读更多...
外包干了3个月，技术倒退明显

外包干了3个月，技术倒退明显

先说情况&#xff0c;大专毕业&#xff0c;18年通过校招进入湖南某软件公司&#xff0c;干了接近6年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试&#xf…
阅读更多...
第1题：两数之和

第1题：两数之和

题目内容&#xff1a; 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是&#xff0c;数组中同一个元素在答案里不能重复出现。…
阅读更多...
最新文章

Copyright @ 2022~2023