【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.kler.cn/a/274334.html

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

相关文章

学习笔记--强化学习（1）

学习笔记--强化学习（1）

参考&#xff1a;https://blog.csdn.net/koulongxin123/article/details/122676149 1.什么是强化学习&#xff1f; (1)定义 基于环境的反馈而行动&#xff0c;通过不断与环境的交互、试错&#xff0c;最终完成特定目的或者使得整体行动收益最大化&#xff08;是一种通过与环境…
阅读更多...
使用jQuery的autocomplete实现数据查询一次，联想自动补全

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

书接上回&#xff0c;上次说到在jsp页面中&#xff0c;通过监听输入框的数值变化&#xff0c;实时查询数据库&#xff0c;得到返回值使用autocomplete属性自动补全&#xff0c;实现一个联想补全辅助操作&#xff0c;链接&#xff1a;使用jquery的autocomplete属性实现联想补全操…
阅读更多...
Apache Dolphinscheduler - 无需重启 Master-Server 停止疯狂刷日志解决方案

Apache Dolphinscheduler - 无需重启 Master-Server 停止疯狂刷日志解决方案

记录的是一个 3.0 比较难搞的问题&#xff0c;相信不少使用过 3.0 的用户都遇到过 Master 服务中存在一些工作流或者任务流一直不停的死循环的问题&#xff0c;导致疯狂刷日志。不过本人到现在也没找到最关键的触发原因&#xff0c;只是看到一些连锁反应带来的结果…… 影响因素…
阅读更多...
Linux下安装Android Studio及创建桌面快捷方式

Linux下安装Android Studio及创建桌面快捷方式

下载 官网地址&#xff1a;https://developer.android.com/studio?hlzh-cn点击下载最新版本即可 安装 将下载完成后文件&#xff0c;进行解压&#xff0c;然后进入android-studio-2023.2.1.23-linux/android-studio/bin目录下&#xff0c;启动studio.sh即可为了更加方便的使…
阅读更多...
【论文阅读】Improved Denoising Diffusion Probabilistic Models

【论文阅读】Improved Denoising Diffusion Probabilistic Models

Improved Denoising Diffusion Probabilistic Models 文章目录 Improved Denoising Diffusion Probabilistic Models概述Improving the Log-likelihoodLearning ∑ θ ( x t , t ) \sum_{\theta}(x_{t}, t) ∑θ​(xt​,t)Improving the Noise ScheduleReducing Gradient Nois…
阅读更多...
Redis的安装和部署教程（Windows环境）

Redis的安装和部署教程（Windows环境）

一、安装Redis服务 1、下载Redis压缩包 以下这个是我网盘里面的&#xff08;这个是v8.0版本的&#xff0c;支持导入.rdb数据文件&#xff09; 链接&#xff1a;百度网盘 请输入提取码 提取码&#xff1a;x0f1 --来自百度网盘超级会员V5的分享 2、解压到文件夹 将下载的压缩…
阅读更多...
【DL经典回顾】激活函数大汇总（二十五）（GEGLU附代码和详细公式）

【DL经典回顾】激活函数大汇总（二十五）（GEGLU附代码和详细公式）

激活函数大汇总&#xff08;二十五&#xff09;&#xff08;GEGLU附代码和详细公式&#xff09; 更多激活函数见激活函数大汇总列表 一、引言 欢迎来到我们深入探索神经网络核心组成部分——激活函数的系列博客。在人工智能的世界里&#xff0c;激活函数扮演着不可或缺的角色…
阅读更多...
金蝶云星空——插件dll重新发布报错：鏃犳硶鏄剧ず椤甸潰锛屽洜涓哄彂鐢熷唴閮ㄦ湇鍔″櫒閿欒銆�

金蝶云星空——插件dll重新发布报错：鏃犳硶鏄剧ず椤甸潰锛屽洜涓哄彂鐢熷唴閮ㄦ湇鍔″櫒閿欒銆�

项目场景&#xff1a; 金蝶插件开发 问题描述 今天更新了插件dll然后重启IIS金蝶就报如下错误&#xff1a; 解决方案&#xff1a; 折腾了一天结果发现是给自己挖坑了&#xff0c;这次更新我担心插件代码有问题就把原dll重命名了然后把最新dll更新到金蝶bin文件中&#xff0c…
阅读更多...
使用Java JDBC连接数据库

使用Java JDBC连接数据库

在Java应用程序中&#xff0c;与数据库交互是一个常见的任务。Java数据库连接&#xff08;JDBC&#xff09;是一种用于在Java应用程序和数据库之间建立连接并执行SQL查询的标准API。通过JDBC&#xff0c;您可以轻松地执行各种数据库操作&#xff0c;如插入、更新、删除和查询数…
阅读更多...
c语言指针(二)

c语言指针(二)

c语言指针&#xff08;二&#xff09; 1.数组名的理解 2.使用指针访问数组 3.一维数组的传参本质 1.数组名的理解 int arr[10] { 1,2,3,4,5,6,7,8,9,10 }; int* p &arr[0]这⾥我们使⽤ &arr[0] 的⽅式拿到了数组第⼀个元素的地址&#xff0c;但是其实数组名本来就是…
阅读更多...
在线教育平台帮助教培机构打造线上

在线教育平台帮助教培机构打造线上

随着互联网的迅猛发展&#xff0c;在线教育逐渐成为了教育行业的主流趋势。为了满足教育机构和学生对高效、便捷在线教育的需求&#xff0c;乔拓云教育系统应运而生。该系统以学员端展示课程和后台管理教务为核心功能&#xff0c;为教育机构提供了一站式解决方案&#xff0c;助…
阅读更多...
IText5填充PDF表单使用自定义字体中文生效而英文和数字不生效？

IText5填充PDF表单使用自定义字体中文生效而英文和数字不生效？

为什么使用IText5填充PDF时&#xff0c;使用自定义字体&#xff08;特别是某些新兴的字体&#xff09;时中文生效&#xff0c;英文和数字不生效&#xff1f; 查了相关资料&#xff0c;发现无果&#xff0c;或者都不生效。 看了api接口文档&#xff0c;发现有解决方案&#xf…
阅读更多...
（008）Unity StateMachineBehaviour的坑

（008）Unity StateMachineBehaviour的坑

文章目录 StateMachineBehaviour同名函数的调用问题StateMachineBehaviour 的 OnState*、OnStateMachine* 的区别 StateMachineBehaviour同名函数的调用问题 1.如果脚本中&#xff0c;两个同名的函数都存在&#xff0c;那么两个函数都会被调用&#xff1b;如果只有其中一个同名…
阅读更多...
自动驾驶决策 - 规划 - 控制 （持续更新！！！）

自动驾驶决策 - 规划 - 控制 （持续更新！！！）

总目录 Frenet与Cartesian坐标系 Apollo基础 - Frenet坐标系 车辆模型 车辆运动学和动力学模型 控制算法 PID控制器轨迹跟随实现 Pure Pursuit控制器路径跟随 路径跟踪算法Stanley 实现 c 无人驾驶LQR控制算法 c 实现 MPC自动驾驶横向控制算法实现 c 双环PID控制详细讲解 …
阅读更多...
人外周血单核细胞来源树突状细胞(MoDC)的制备(一)

人外周血单核细胞来源树突状细胞(MoDC)的制备(一)

MoDC制备方法简图 背景 DC是“Dendritic Cells”的缩写&#xff0c;中文全称为“树突状细胞”&#xff0c;因其成熟时伸出许多树突样或伪足样突起而得名。DC 是由 2011 年诺贝尔奖获得者、加拿大籍科学家 Ralph M. Steinman 于1973 年发现的&#xff0c;是目前发现的功能最强的…
阅读更多...
下拉树级带搜索功能

下拉树级带搜索功能

可以直接复制粘贴到自己的项目里,方法处把接口替换一下 <template><div><el-popoverplacement"bottom"width"200"trigger"click"><el-inputslot"reference"class"mrInput":placeholder"placehol…
阅读更多...
虚拟机VMware上 centos7 的网络配置

虚拟机VMware上 centos7 的网络配置

第一步&#xff1a;权限的切换 由普通用户切换到管理者/超级用户 用户名为&#xff1a;root 密码为&#xff1a;自己安装 linux 时第一次设置的密码 su -root管理者/超级用户的命令提示符是“#”&#xff0c;普通用户的命令提示符是“$”。当看到你的命令提示符为“$”时&…
阅读更多...
2、鸿蒙学习-申请调试证书和调试Profile文件

2、鸿蒙学习-申请调试证书和调试Profile文件

申请发布证书 发布证书由AGC颁发的、为HarmonyOS应用配置签名信息的数字证书&#xff0c;可保障软件代码完整性和发布者身份真实性。证书格式为.cer&#xff0c;包含公钥、证书指纹等信息。 说明 请确保您的开发者帐号已实名认证。每个帐号最多申请1个发布证书。 1、登录AppGa…
阅读更多...
0基础学习VR全景平台篇第145篇：图层控件功能

0基础学习VR全景平台篇第145篇：图层控件功能

大家好&#xff0c;欢迎观看蛙色VR官方——后台使用系列课程&#xff01;这期&#xff0c;我们将为大家介绍如何使用图层控件功能。 一.如何使用图层控件功能&#xff1f; 进入作品编辑页面&#xff0c;点击左边的控件后就可以在右边进行相应设置。 二.图层控件有哪些功能&am…
阅读更多...
综合练习（python）

综合练习（python）

前言 有了前面的知识积累&#xff0c;我们这里做两个小练习&#xff0c;都要灵活运用前面的知识。 First 需求 根据美国/英国各自YouTube的数据&#xff0c;绘制出各自的评论数量的直方图 第一版 import numpy as np from matplotlib import pyplot as plt import matplo…
阅读更多...
最新文章

Copyright @ 2022~2023