当前位置： 首页 > article >正文

C++：用红黑树封装map与set-1

article 2024/11/25 11:33:37

在这里插入图片描述

文章目录

  • 前言
  • 一、STL源码分析
  • 二、红黑树的构建
  • 三、map与set整体框架的搭建与解析
  • 四、如何取出进行比较？
    • 1. met与set的数据是不同的
    • 2. 取出数据进行比较
      • 1）问题发现
      • 2）仿函数解决
  • 五、封装插入
  • 六、迭代器的实现
    • 1. operator* 与operator->
    • 2. operator!=
    • 3. operator++
    • 4. operator- -
    • 5. 套用普通迭代器
  • 七、const迭代器
  • 八、查找
  • 总结

前言

之前我们学习了红黑树的实现，现在我们一起来看一看如何使用红黑树封装出set与map~~~

一、STL源码分析

我们一起来分析分析STL源码，看一看库中是如何实现的🥰🥰

在这里插入图片描述
首先，库里面stl_set与stl_map中，

对于set来说，key_type是key，value_type也是key，也就是说set是一个rbTree<Key, Key>的模型。

对于map来说，key_type是key，但是value_type是pair<const key, T>，也就是说map是一个rbTree<Key, pair<Key, Value>>的模型。

我们再来看一下rb_tree的结构：

在这里插入图片描述

rb_tree中，前两个参数是<key, value>，而__rb_tree_node<value>里面的参数传的是value，因此我们可以总结出，这里map的结点中存储的是pair<key, value>，而set的结点中存储的是key。

在这里插入图片描述

那么到底为什么是这样的结构呢？
我们将在下面的讲解中逐一解释🥰

二、红黑树的构建

对于红黑树的构建，J桑之前的文章有详细的讲解，因此这里就直接给出代码啦，还不清楚的观众老爷门可以点击下方的传送门🥰🥰🥰

深入探索：C++红黑树原理与实现

当然，我们之前红黑树是默认存储pair，现在要同时满足map与set，因此一些地方需要改变，之后总结的时候会给出完整的更改后的代码，下面讲解也会被提到。

#pragma once
#include<iostream>

using namespace std;

enum Colour
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

template<class K, class V> 
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		// 树为空，直接插入然后返回
		if (_root == nullptr)
		{
			_root = new Node(kv);
			// 根节点必须是黑色
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;

		while (cur)
		{
			// 小于往左走
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)   // 大于往右走
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		// 其他结点初始颜色为红色
		cur->_col = RED;

		// 链接
		if (cur->_kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		// 如果我们parent是黑色，不用处理，就结束了

		// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定
		// 用while循环是因为我们要不断的向上调整
		while (parent && parent->_col == RED)
		{
			// 首先我们要找到grandfather
			Node* grandfather = parent->_parent;
			
			// 接下来通过grandfather找到uncle

			//如果parent是grandfather->_left
			if (parent == grandfather->_left)
			{
				// 说明uncle在右边
				Node* uncle = grandfather->_right;

				// uncle存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 满足上述情况，开始调整颜色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上调整
					cur = grandfather;
					parent = cur->_parent;

					// 但是走到这里有一个问题，如果当前parent就是根，
					// 并且parent是红色，我们要把它变为黑色，
					// 处理方式是：出循环后，暴力将_root->_col变为黑色
				}
				else    // uncle不存在 或 uncle存在且为黑色
				{
					// 判断要怎样旋转

					// 右单旋
					if (cur == parent->_left)
					{
						//     g
						//   p
						// c
						RotateR(grandfather);
						// 调整颜色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else // 左右双旋
					{
						//     g
						//   p
						//		c
						RotateL(parent);
						RotateR(grandfather);
						// 调整颜色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					// 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出
					break;
				}
			}
			else //(parent == grandfather->_right)  // 如果parent是grandfather->_right
			{
				// 说明uncle在左边
				Node* uncle = grandfather->_left;

				// uncle存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 满足上述情况，开始调整颜色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else    // uncle不存在 或 uncle存在且为黑色
				{
					// 判断要怎样旋转

					// 左单旋
					if (cur == parent->_right)
					{
						// g
						//	  p
						//       c
						RotateL(grandfather);
						// 调整颜色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else // 右左双旋
					{
						// g
						//	  p
						// c
						RotateR(parent);
						RotateL(grandfather);
						// 调整颜色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}

		// 这里保证根为黑色
		_root->_col = BLACK;

		return true;
	}

	// 左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		// 重新链接
		parent->_right = curleft;
		if (curleft) // 如果curleft存在
		{
			curleft->_parent = parent;
		}

		cur->_left = parent;

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

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

			cur->_parent = ppnode;
		}
	}

	// 右单旋
	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 (ppnode == nullptr)
		{
			cur->_parent = nullptr;
			_root = cur;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
			cur->_parent = ppnode;
		}
	}

	// 检查是否构建正确
	bool CheckColour(Node* root, int blacknum, int benchmark)
	{
		if (root == nullptr)
		{
			if (blacknum != benchmark)
				return false;

			return true;
		}

		if (root->_col == BLACK)
		{
			++blacknum;
		}

		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "出现连续红色节点" << endl;
			return false;
		}

		return CheckColour(root->_left, blacknum, benchmark)
			&& CheckColour(root->_right, blacknum, benchmark);
	}

	bool IsBalance()
	{
		return IsBalance(_root);
	}

	bool IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;

		if (root->_col != BLACK)
		{
			return false;
		}

		// 基准值
		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;

			cur = cur->_left;
		}

		return CheckColour(root, 0, benchmark);
	}

private:
	Node* _root = nullptr;
};

三、map与set整体框架的搭建与解析

代码：

namespace jyf
{
	template<class k, class v>
	class map
	{
	public:

	private:
		RBTree<k, pair<k, v>> _t;
	};
}

namespace jyf
{
	template<class k>
	class set
	{
	public:

	private:
		RBTree<k, k> _t;
	};
}

解析：

首先无论是map还是set都有两个模板参数，第一个是key，这个key是多存的，它的作用体现在像find()这样的函数中，我们后面在做解析。

这里先看第二个参数，传给了RBTree的T，而T就是结点中储存的东西，也就是说，你是set，那么节点中就储存的是key, 你是map，那么节点中就储存的是pair<k, v>。

在这里插入图片描述

四、如何取出进行比较？

1. met与set的数据是不同的

我们要明白一个我问题，met与set结点中存储的数据是不一样的，因此，如果节点中还存储的是pair就不对了，因此，我们结点之中存储的数据因该是T类型的数据，如果是set就是key,如果是map就是pair。

在这里插入图片描述

2. 取出数据进行比较

1）问题发现

再insert函数中，我们之前的红黑树是这样实现的，比如这个找到插入位置的逻辑：

在这里插入图片描述
在这张图片里面，我们之前使用pair，但是现在对于map和set存储的数据不同，因此需要用data来比较。

但是！！！
对于map来说，它的value是pair，但是pair的比较逻辑能满足我们的需要吗？

在这里插入图片描述

可以看到，pair的比较逻辑是先比first，first一样就比second，但是，我们这里不需要比较second，key_value的模型中，只需要比较key不同，因此我们需要一种方法，重新定义我们的比较。

怎么重新比较呢？
这里我们通过观察发现，对于set来说，它的data是key，可以直接比较，唯一有问题的是map，因此我们采取的方式是仿函数。

2）仿函数解决

我们可以多定义一个模板参数KeyOfT，这个模板参数用来定义仿函数，他的作用是取出Set或Map中的Key。

对于Set，它的data直接就是key：

struct SetKeyOfT
{
	const K& operator()(const K& key)
	{
		return key;
	}
};

对于Map，它的data是一个pair，我们需要pair的first，也就是key：

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

在这里插入图片描述

至此，我们在取出数据的时候，只要定义出一个对象，重载operator()，用()将data包起来，就得到了我们想要的数据。

可以说，这里set迁就了map~

五、封装插入

完成了上述步骤，我们就可以实现封装map与set的插入了~

对于set:

bool insert(const K& key)
{
	return _t.Insert(key);
}

对于map:

bool insert(const pair<K,V>& kv)
{
	return _t.Insert(kv);
}

插入结果：
在这里插入图片描述

在这里插入图片描述

六、迭代器的实现

要实现迭代器，就要先理解迭代器是怎么用的：
下面是一个模板表示迭代器的使用：

it = s.begin();
while (it != s.end())
{
    cout << *it << endl;
    ++it;
}

为了实现这个过程，我们需要重载很多东西。

我们先将框架搭出来：

template<class T>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T> Self;
	Node* _node;

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

1. operator* 与operator->

RBTree中：

T& operator* ()
{
	return _node->_data;
}

T* operator-> ()
{
	return &(_node->_data);
}

2. operator!=

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

3. operator++

对于树的迭代器，++与- -就非常重要了，这里有很多坑~

首先对于一个红黑树，他走的是中序的排序，图如下：

在这里插入图片描述

那么，it.begin()是谁呢？
我们说中序是左-根-右，也就是说，begin应该是上图中的1。

其次，如果我们进行++操作，迭代器会到那里去呢？
这里分以下几种情况：

  1. 如果右不为空

那么下一个访问的，将是右树的最左：

在这里插入图片描述

  1. 如果右为空

这里又分两种情况：

  • cur是parent的左——下一个访问parent
    在这里插入图片描述

  • cur是parent的右——下一个访问没有被访问的祖先
    在这里插入图片描述

通过观察这两种情况我们可以发现：
也就是说，当右为空的时候，下一个访问的是孩子是父亲的左侧的那一个祖先。

代码总结：

Self& operator++ ()
{
	if (_node->_right != nullptr)
	{
		Node* curleft = _node->_right;
		while (curleft->_left)
		{
			curleft = curleft->_left;
		}
		_node = curleft;
	}
	else
	{
		// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点
		Node* cur = _node;
		Node* parent = _node->_parent;

		while (parent)
		{
			if (parent->_left == cur)
			{
				break;
			}
			else
			{
				cur = parent;
				parent = parent->_parent;
			}
		}

		_node = parent;
	}

	return *this;
}

4. operator- -

原理与++是一样的，只不过原本++的顺序是中序，即左-根-右，- - 是反过来的，因此是右-根-左

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;
			while (parent && cur == parent->_left)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

5. 套用普通迭代器

RBTree中：

经过前面的分析，begin就是树最左边的结点，end我们设置为nullptr。

	typedef __TreeIterator<T> iterator;
public:

	iterator begin()
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}
		return iterator(leftMin);
	}

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

set与map中，我们要封装这个方法：

iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

测试普通迭代器：

jyf::map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(2, 2));

jyf::map<int, int>::iterator mit = m.begin();

while (mit != m.end())
{
	mit->first = 1;
	mit->second = 2;

	cout << mit->first << ":" << mit->second << endl;
	++mit;
}
cout << endl;

for (const auto& kv : m)
{
	cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

jyf::set<int> s;
s.insert(5);
s.insert(2);
s.insert(2);
s.insert(12);
s.insert(22);
s.insert(332);
s.insert(7);

auto it = s.begin();
while (it != s.end())
{
	// Ӧ޸
	if (*it % 2 == 0)
	{
		*it += 10;
	}

	cout << *it << " ";
	++it;
}
cout << endl;

for (const auto& e : s)
{
	cout << e << " ";
}
cout << endl;

结果为：
在这里插入图片描述

七、const迭代器

我们知道set是不允许修改的，map的key不允许修改，而value允许修改，再通过观察库中的实现，我们可以发现:
在这里插入图片描述

set实现不能修改的原因是——interator迭代器与const_iterator都是const迭代器。

而map实现key不能修改，value可以修改的方法是，在定义map的value的时候，pair<K, V>修改为pair<const K, V>

具体的逻辑我们下一次在进行讲解~

八、查找

查找是通过key来查找的，而不是通过value来查找的，这也就解释了为什么最开始定义模板参数还要多定义一个key。

同样，为了取出对应的值，我们也需要仿函数来包上data。

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

	return nullptr;
}

总结

红黑树在 STL 的应用
set 与 map 的实现：

set 节点存储 key（rbTree<Key, Key> 模型）。

map 节点存储 pair<const Key, T>（rbTree<Key, pair<Key, Value>> 模型）。

rbTree 的设计：
节点使用 __rb_tree_node，value 的具体含义根据容器类型不同而不同。

在这里插入图片描述


http://www.kler.cn/a/408538.html

相关文章：

  • repmgr安装及常用运维指令
  • Flutter：AnimatedIcon图标动画，自定义Icon通过延时Interval，实现交错式动画
  • 无线图传下的低延迟视频传输播放技术探讨
  • 【Ubuntu24.04】服务部署（Docker）
  • 从零开始-VitePress 构建个人博客上传GitHub自动构建访问
  • 【操作系统】每日 3 题（三十五）
  • 前端：JavaScript （学习笔记）【2】
  • 每日计划-1124
  • 嵌入式Linux——文件类型
  • 【jvm】java对象的访问定位
  • MATLAB的语音信号采集与处理分析
  • Puppeteer 和 Cheerio 在 Node.js 中的应用
  • React学习06- API扩展
  • 如何理解tensor中张量的维度
  • Web 毕设篇-适合小白、初级入门练手的 Spring Boot Web 毕业设计项目：电影院后台管理系统（前后端源码 + 数据库 sql 脚本）
  • 亚太杯数学建模C题思路与算法(2024)
  • 手机文件可以打印出来吗
  • linux 运维常用命令
  • 使用NAS开启无纸化办公，Docker部署开源文档管理系统『Paperless-ngx』
  • kali中信息收集的一些常用工具
  • hugo文章支持数学公式
  • 第三十章 TCP 客户端 服务器通信 - 作业服务器资源
  • 【c++篇】掌握动态内存的奥妙
  • 丑数 详解
  • 修改ffmpeg实现https-flv内容加密
  • apache、iis屏蔽限制ip访问(适用虚拟主机)