【C++】用红黑树模拟实现set、map

目录

  • 前言及准备：
  • 一、红黑树接口
    • 1.1 begin
    • 1.2 end
    • 1.3 查找
    • 1.4 插入
    • 1.5 左单旋和右单旋
  • 二、树形迭代器（正向）
    • 2.1 前置++
  • 三、模拟实现set
  • 四、模拟实现map

前言及准备：

set、map的底层结构是红黑树，它们的函数通过调用红黑树的接口来实现，红黑树一些接口需要通过树形迭代器来实现。set是k模型，map是kv模型，红黑树要不要写两份呢？答案是不需要，只用一份即可，通过仿函数来控制。

定义树的节点：

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Colour _col;
	RBTreeNode(const T& data)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(data)
		,_col(RED)
	{}
};

红黑树有3个指针域，数据域用T来表示，如果是set，那么传过来的是k模型；如果是map，是kv模型。新增的节点的颜色默认是红色（根节点除外）。

一、红黑树接口

1.1 begin

返回的是红黑树的第一个节点，注意，这里的第一个的顺序是按中序遍历来的，所以，第一个节点的位置是树的最左节点。

//返回的迭代器指向的数据可修改
iterator begin()
{
	Node* subLeft = _root;
	while (subLeft->_left)
	{
		subLeft = subLeft->_left;
	}
	return iterator(subLeft);
}
//返回的迭代器指向的数据不可修改
const_iterator begin() const
{
	Node* subLeft = _root;
	while (subLeft->_left)
	{
		subLeft = subLeft->_left;
	}
	return const_iterator(subLeft);
}

1.2 end

返回的是最后一个节点（最右侧节点）的下一个位置。由于这里实现的红黑树没有头节点，所以只能给nullptr来勉强实现这个迭代器。但是这样其实是不行的，因为对end()位置的迭代器进行 - - 操作，必须要能找最后一个元素，给nullptr就找不到了。如果有头节点，那么end()的位置应该是在头节点的位置。
在这里插入图片描述

iterator end()
{
	return iterator(nullptr);
}
const_iterator end() const
{
	return const_iterator(nullptr);
}

1.3 查找

查找的过程与之前写的二叉搜索树没有多大区别，要注意的是返回类型，找到了，返回的是该节点的迭代器，找不到就返回end()。

iterator Find(const K& key)
{
	KeyOfT kot;
	Node* cur = _root;
	while (cur)
	{
		if (kot(cur->_data) < key)
		{
			cur = cur->_right;
		}
		else if (kot(cur->_data) > key)
		{
			cur = cur->_left;
		}
		else
		{
			return iterator(cur);
		}
	}
	return end();
}

咋知道是set还是map的数据进行比较，看传过来的类模板参数中的仿函数是set的还是map的。当然，这里只需写好就行，不用关心传过来的是什么，set和map的仿函数内部已经确定好了。

说明一下：

template<class K, class T, class KeyOfT>

这是该红黑树的类模板，K是Find()函数中要对比的数据类型，T是节点的数据域，可能是k模型，也有可能是kv模型。怎么确定呢？通过第三个类模板参数——仿函数来确定。仿函数传的是set的，就是k模型；仿函数传的是map的，就是kv模型。仿函数内部具体实现下面再说。

1.4 插入

为了接近STL库中的insert函数，返回类型是pair，即插入成功，返回该节点的迭代器和true；插入失败，说明该节点已经存在，返回该节点的迭代器和false。

pair<iterator, bool> Insert(const T& data)
{
	//为空
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;//根节点都是黑色的，特殊处理
		return make_pair(iterator(_root), true);
	}
	//非空
	KeyOfT kot;
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kot(cur->_data) < kot(data))
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kot(cur->_data) > kot(data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return make_pair(iterator(cur), false);
		}
	}
	//插入新节点
	cur = new Node(data);//红色的
	if (kot(parent->_data) < kot(data))
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;
	Node* newnode = cur;

	//调整颜色
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;//爷爷节点
		//父节点在爷爷节点的左边，那么叔叔节点在右边
		if (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;
			//情况一：叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				grandfather->_col = RED;
				uncle->_col = parent->_col = BLACK;
				cur = grandfather;//爷爷不是根，向上更新
				parent = cur->_parent;
			}
			//情况二：叔叔不存在/存在且为黑
			else
			{
				//单旋
				if (cur == parent->_left)
				{
					RotateR(grandfather);//右单旋
					parent->_col = BLACK;//变色
					grandfather->_col = RED;
				}
				//左右双旋 
				// cur == parent->_right
				else
				{
					RotateL(parent);//先左单旋
					RotateR(grandfather);//再右单旋
					grandfather->_col = RED;//变色
					cur->_col = BLACK;
				}
			}
		}
		else//父节点在右边，叔叔在左边
		{
			Node* uncle = grandfather->_left;
			//情况一：叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				grandfather->_col = RED;
				uncle->_col = parent->_col = BLACK;
				cur = grandfather;//爷爷不是根，向上更新
				parent = cur->_parent;
			}
			//情况二：叔叔不存在/存在且为黑
			else
			{
				//单旋
				if (cur == parent->_right)
				{
					RotateL(grandfather);//左单旋
					parent->_col = BLACK;//变色
					grandfather->_col = RED;
				}
				//右左双旋 
				// cur == parent->_left
				else
				{
					RotateR(parent);//先右单旋
					RotateL(grandfather);//再左单旋
					grandfather->_col = RED;//变色
					cur->_col = BLACK;
				}
				break;//经过情况二后跳出
			}
		}
	}
	_root->_col = BLACK;//统一处理，根必须是黑的
	return make_pair(iterator(newnode), true);
}

1.5 左单旋和右单旋

这两个就是之前的，这里不作重复叙述了

//左单旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	//不为空
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subR->_left = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subR;
	//处理parent如果为根
	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	//不为根，处理与ppnode的连接
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subR;
		}
		else
		{
			ppnode->_right = subR;
		}
		subR->_parent = ppnode;
	}
}

//右单旋
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;
	}
}

二、树形迭代器（正向）

2.1 前置++

首先要清楚的是++到下一个节点位置是按中序遍历走的，主要有两种情况：

  1. 该节点有右子树
  2. 该节点没有右子树

1️⃣有右子树
在这里插入图片描述
总结：有右子树++后的下一个节点是右子树的最左节点

2️⃣没有右子树
在这里插入图片描述
总结：没有右子树++后下一个节点是祖先节点中左孩子是当前节点（原来节点的位置）或者左孩子是当前节点的父亲的那个祖先

有点弯，再来图捋一捋：
在这里插入图片描述

前置- -的逻辑与前置++刚好相反

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;
	RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	//前置++
	Self& operator++()
	{
		//右子树存在
		if (_node->_right)
		{
			//下一个节点在右子树的最左边
			Node* subLeft = _node->_right;
			while (subLeft->_left)
			{
				subLeft = subLeft->_left;
			}
			_node = subLeft;
		}
		//右子树不存在
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			//cur是parent的左子树，parent就是下一个
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	//前置--
	Self& operator--()//与前置++的逻辑相反
	{
		//左子树存在
		if (_node->_left)
		{
			//下一个节点是左子树的最右一个
			Node* subRight = _node->_left;
			while (subRight->_right)
			{
				subRight = subRight->_right;
			}
			_node = subRight;
		}
		//左子树不存在
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			//cur是parent的右子树时parent就是下一个
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const Self& s)
	{  
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};

三、模拟实现set

set是k模型，仿函数返回的只有key值。其他接口调用红黑树的

template<class K>
class set
{
	//仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:
	typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;
	typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator const_iterator;
	//迭代器
	iterator begin()
	{
		return _t.begin();
	}
	const_iterator begin() const
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	const_iterator end() const
	{
		return _t.end();
	}
	//插入
	pair<iterator, bool> Insert(const K& key)
	{
		return _t.Insert(key);
	}
	//查找
	iterator Find(const K& key)
	{
		_t.Find(key);
	}
private:
	RBTree<K, const K, SetKeyOfT> _t;
};

四、模拟实现map

map是kv模型，仿函数返回的取kv中的key值。其他接口调用红黑树的，除此之外，多了一个operator[]

template<class K, class V>
class map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};

public:
	typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
	typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
	//迭代器
	iterator begin()
	{
		return _t.begin();
	}
	const_iterator begin() const
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	const_iterator end() const
	{
		return _t.end();
	}

	//插入
	pair<iterator, bool> Insert(const pair<K, V>& kv)
	{
		return _t.Insert(kv);
	}

	//查找
	iterator Find(const K& key)
	{
		_t.Find(key);
	}

	//operator[]
	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = Insert(make_pair(key, V()));
		return ret.first->second;
	}
private:
	RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

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

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

相关文章

【CSS练习】万年历 html+css+js

【CSS练习】万年历 html+css+js

效果图 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>Document</title><style>bod…
阅读更多...
车辆运动学和动力学模型

车辆运动学和动力学模型

参考&#xff1a;路径规划与轨迹跟踪系列算法学习_第9讲_车辆运动学和动力学模型 1 车辆运动学模型和动力学模型概述 要控制车辆的运动&#xff0c;首先要对车辆的运动建立数字化模型&#xff0c;模型建立的越准确&#xff0c;对车辆运动的描述越准确&#xff0c;对车辆的跟踪…
阅读更多...
Django分页器

Django分页器

Django分页器 分页器前瞻之url urls.py不需要做修改 urlpatterns [path(test/, views.test,nametest), ]假设此时在原有的路径http://127.0.0.1:8000/app01/test后面添加/?page2 然后再后端获取到page def test(request):page request.GET.get(page)print(page) # 2retu…
阅读更多...
Linux--如何在Linux上运行一个helloworld

Linux--如何在Linux上运行一个helloworld

一.安装vim和gcc sudo --是进入管理员模式 apt --是 Advanced Package Tool&#xff08;高级软件包工具&#xff09;的缩写&#xff0c;这是用于管理软件包的一种工具。 install --是安装的意思 后面跟软件的名称 完整的意思&#xff1a;在管理员的模式下安装 某个软件 …
阅读更多...
使用jQuery的autocomplete实现数据查询一次，联想自动补全

使用jQuery的autocomplete实现数据查询一次，联想自动补全

书接上回&#xff0c;上次说到在jsp页面中&#xff0c;通过监听输入框的数值变化&#xff0c;实时查询数据库&#xff0c;得到返回值使用autocomplete属性自动补全&#xff0c;实现一个联想补全辅助操作&#xff0c;链接&#xff1a;使用jquery的autocomplete属性实现联想补全操…
阅读更多...
C++--STL标准库

C++--STL标准库

一.模板 模板是C中泛型编程的基础。一个模板就是一个创建类或函数的蓝图。 生活中常见的模板有: 编写一个比较两个值大小的函数&#xff0c;如果第一个值大于第二个值返回大于0的数字,两个值相等返回0,第一个值小于第二个值返回小于0的数字。 我们可以根据值类型定义多个函数&…
阅读更多...
2024年阿里云服务器搭建幻兽帕鲁游戏_保姆级教程

2024年阿里云服务器搭建幻兽帕鲁游戏_保姆级教程

玩转幻兽帕鲁服务器&#xff0c;阿里云推出新手0基础一键部署幻兽帕鲁服务器教程&#xff0c;傻瓜式一键部署&#xff0c;3分钟即可成功创建一台Palworld专属服务器&#xff0c;成本仅需26元&#xff0c;阿里云服务器网aliyunfuwuqi.com分享2024年新版基于阿里云搭建幻兽帕鲁服…
阅读更多...
SecureCRT出现乱码的解决方法

SecureCRT出现乱码的解决方法

SecureCRT是一个商业终端连接工具&#xff0c;它支持多种自定义设置。默认设置下&#xff0c;通过SecureCRT连接SSH服务器可能出现中文乱码的情况。这是由于SecureCRT字符编码与服务器的字符编码不一致造成的。 当然解决这个问题也很简单&#xff0c;将SecureCRT字符编码设置成…
阅读更多...
深入探讨Python中的文件操作与文件IO操作【第141篇—Python实现】

深入探讨Python中的文件操作与文件IO操作【第141篇—Python实现】

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 深入探讨Python中的文件操作与文件IO操作 在Python编程中&#xff0c;文件操作和文件IO操作…
阅读更多...
计算机缺失msvcp110.dll如何修复，多种修复方法教给你

计算机缺失msvcp110.dll如何修复，多种修复方法教给你

当电脑系统中msvcp110.dll文件丢失时&#xff0c;可能会对计算机的正常运行产生一系列显著的影响。msvcp110.dll是Microsoft Visual C Redistributable Package的一部分&#xff0c;这个动态链接库文件对于许多基于Windows的应用程序至关重要&#xff0c;尤其是一些使用C编译器…
阅读更多...
干货整理！火石控股创始人吴渔夫的 AI 游戏思维20条

干货整理！火石控股创始人吴渔夫的 AI 游戏思维20条

近日&#xff0c;在一场面对面的直播中&#xff0c;自媒体「极新」创始人姜稳与火石控股创始人、奇酷网络董事长吴渔夫进行视频对话中&#xff0c;探讨了AI技术对游戏行业的新机遇和新挑战。 中国网游先锋&#xff0c;火石控股创始人&#xff0c;奇酷网络董事长吴渔夫认为&…
阅读更多...
【亲测】Onlyfans年龄认证怎么办？Onlyfans需要年龄验证？

【亲测】Onlyfans年龄认证怎么办？Onlyfans需要年龄验证？

1. 引言 什么是OnlyFans&#xff1a;OnlyFans是一种内容订阅服务&#xff0c;成立于2016年&#xff0c;允许内容创作者从用户那里获得资金&#xff0c;用户需要支付订阅费用才能查看他们的内容。它在多个领域受到欢迎&#xff0c;包括音乐、健身、摄影&#xff0c;以及成人内容…
阅读更多...
万众期待，催更5年，《码农翻身2》强势来袭！！！

万众期待，催更5年，《码农翻身2》强势来袭！！！

转眼间&#xff0c;距离《码农翻身》的出版已经过了5 年时间&#xff0c;很多读者催问&#xff1a;“什么时候出《码农翻身2》&#xff1f;我已经等不及了&#xff01;”“疫情都结束了&#xff0c;《码农翻身2》在哪儿&#xff1f;”…… 现在《码农翻身2》终于来了&#xff…
阅读更多...
靠谱且性价比高的随身WiFi推荐！买随身WiFi应该注意什么？最全攻略，新手必看

靠谱且性价比高的随身WiFi推荐！买随身WiFi应该注意什么？最全攻略，新手必看

一、哪些人更适合使用随身WiFi呢&#xff1f; 1、【学生党】校园网太差&#xff0c;流量费太贵&#xff0c;没钱的学生党用个靠谱的随身WiFi挺不错的。 2、【户外工作者】货车司机、滴滴司机等。高峰期抢单没信号&#xff0c;空闲打发时间没流量&#xff0c;可以使用一个。 3…
阅读更多...
改进YOLOv8注意力系列六：结合SEAttention轻量通道注意力、ShuffleAttention重排特征注意力模块、SimAM无参数化注意力

改进YOLOv8注意力系列六：结合SEAttention轻量通道注意力、ShuffleAttention重排特征注意力模块、SimAM无参数化注意力

改进YOLOv8注意力系列五：结合ParNetAttention注意力、高效的金字塔切分注意力模块PSA、跨领域基于多层感知器（MLP）S2Attention注意力 代码SEAttention轻量通道注意力ShuffleAttention重排特征注意力模块SimAM无参数化注意力加入方法各种yaml加入结构本文提供了改进 YOLOv8注…
阅读更多...
智能合约 之 部署ERC-20

智能合约 之 部署ERC-20

Remix介绍 Remix是一个由以太坊社区开发的在线集成开发环境&#xff08;IDE&#xff09;&#xff0c;旨在帮助开发者编写、测试和部署以太坊智能合约。它提供了一个简单易用的界面&#xff0c;使得开发者可以在浏览器中直接进行智能合约的开发&#xff0c;而无需安装任何额外的…
阅读更多...
Linux 进程管理工具top ps

Linux 进程管理工具top ps

概述 top 和 ps 是 Linux 系统中两个非常重要的用于管理和监控进程的命令工具。以下是它们的主要功能和区别&#xff1a; top&#xff1a; 动态视图&#xff1a;top 提供了一个实时动态更新的视图&#xff0c;能够持续显示系统中当前正在运行的进程信息及其资源占用情况。 系统…
阅读更多...
2024-Spring IOC 和 AOP源码分析（上篇）

2024-Spring IOC 和 AOP源码分析（上篇）

**前言&#xff1a;**笔者最近面了几次大厂。。。开局Spring源码暴击 之前看过忘了写篇总结。。。 1、介绍一下Spring 核心组件&#xff1a; 常用模块&#xff1a; 常用注解&#xff1a; 2、说一下SpringIOC原理 概念&#xff1a;Spring 通过一个配置文件描述 Bean 及 B…
阅读更多...
Linux--Shell脚本安装 httpd 和 修改IP

Linux--Shell脚本安装 httpd 和 修改IP

shell脚本 关闭防火墙、安装httpd、启动httpd [rootnode11 ~]# mkdir shell[rootnode11 ~]# vim abc.sh #!/bin/bash#安装httpd服务#1、挂载 准备yum源 mount /dev/sr0 /mnt &> /dev/nulldf$(df -h | grep /dev/sr0 | awk {print $6})if [ "$df" "/mn…
阅读更多...
Day61：WEB攻防-PHP反序列化原生类TIPSCVE绕过漏洞属性类型特征

Day61：WEB攻防-PHP反序列化原生类TIPSCVE绕过漏洞属性类型特征

知识点&#xff1a; 1、PHP-反序列化-属性类型&显示特征 2、PHP-反序列化-CVE绕过&字符串逃逸 3、PHP-反序列化-原生类生成&利用&配合 补充&#xff1a;如果在 PHP 类中没有实现某个魔术方法&#xff0c;那么该魔术方法在相应的情况下不会被自动触发。PHP 的魔…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站