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

【C++笔记】红黑树封装map和set深度剖析

article 2025/1/19 14:04:53

【C++笔记】红黑树封装map和set深度剖析

在这里插入图片描述

🔥个人主页：大白的编程日记

🔥专栏：C++笔记

文章目录

  • 【C++笔记】红黑树封装map和set深度剖析
    • 前言
    • 一. 源码及框架分析
      • 1.1 源码框架分析
    • 二. 模拟实现map和set
      • 2.1封装map和set
    • 三.迭代器
      • 3.1思路分析
      • 3.2 代码实现
    • 四.operator[]
      • 4.1思路分析
    • 五.源码
    • 后言

前言

哈喽，各位小伙伴大家好!上期我们讲了红黑树。今天我们来讲一下用红黑树封装map和set。话不多说，我们进入正题！向大厂冲锋
在这里插入图片描述

一. 源码及框架分析

我们看一下源码是如何实现红黑树封装map和set。

参考SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等几个头文件中。

// set
#ifndef __SGI_STL_INTERNAL_TREE_H
#include <stl_tree.h>
#endif
#include <stl_set.h>
#include <stl_multiset.h>
// map
#ifndef __SGI_STL_INTERNAL_TREE_H
#include <stl_tree.h>
#endif
#include <stl_map.h>
#include <stl_multimap.h>
// stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
	// typedefs:
	typedef Key key_type;
	typedef Key value_type;
private:
	typedef rb_tree<key_type, value_type,
		identity<value_type>, key_compare, Alloc> rep_type;
	rep_type t; // red-black tree representing set
};
// stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
	// typedefs:
	typedef Key key_type;
	typedef T mapped_type;
	typedef pair<const Key, T> value_type;
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing map
};
// stl_tree.h
struct __rb_tree_node_base
{
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color;
base_ptr parent;
base_ptr left;
base_ptr right;
};
// stl_tree.h
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc
	= alloc>
class rb_tree {
protected:
	typedef void* void_pointer;
	typedef __rb_tree_node_base* base_ptr;
	typedef __rb_tree_node<Value> rb_tree_node;
	typedef rb_tree_node* link_type;
	typedef Key key_type;
	typedef Value value_type;
public:
	// insert⽤的是第⼆个模板参数左形参
	pair<iterator, bool> insert_unique(const value_type& x);
	// erase和find⽤第⼀个模板参数做形参
	size_type erase(const key_type& x);
	iterator find(const key_type& x);
protected:
	size_type node_count; // keeps track of size of tree
	link_type header;
};
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_node<Value>* link_type;
Value value_field;
};

1.1 源码框架分析

  • 通过下图对框架的分析，我们可以看到源码中rb_tree用了⼀个巧妙的泛型思想实现，rb_tree是实现key的搜索场景，还是key/value的搜索场景不是直接写死的，而是由第⼆个模板参数Value决定_rb_tree_node中存储的数据类型。
  • set实例化rb_tree时第二个模板参数给的是key，map实例化rb_tree时第二个模板参数给的是pair<const key, T>，这样⼀颗红黑树既可以实现key搜索场景的set，也可以实现key/value搜索场景的map。
  • 要注意一下，源码里面模板参数是用T代表value，而内部写的value_type不是我们我们日常key/value场景中说的value，源码中的value_type反而是红黑树结点中存储的真实的数据的类型。
  • rb_tree第二个模板参数Value已经控制了红黑树结点中存储的数据类型，为什么还要传第一个模板参数Key呢？尤其是set，两个模板参数是⼀样的，这是很多同学这时的⼀个疑问。要注意的是对于map和set，find/erase时的函数参数都是Key，所以第⼀个模板参数是传给find/erase等函数做形参的类型的。对于set而言两个参数是⼀样的，但是对于map而言就完全不一样了，map insert的是pair对象，但是find和ease的是Key对象。

所以我们可以通过模版参数来控制红黑树底层的结构。
所以不用实现两颗红黑树，但是本质还是编译器根据模版参数生成两颗不同的红黑树。

二. 模拟实现map和set

这里借鉴源码的底层实现。
我们也自己模拟实现出我们的mymap和myset.

2.1封装map和set

  • 参考源码框架，map和set复用之前我们实现的红黑树。
  • 我们这里相比源码调整⼀下，key参数就用K，value参数就用V，红黑树中的数据类型，我们使用T。
  • 其次因为RBTree实现了泛型不知道T参数导致是K，还是pair<K, V>，那么insert内部进行插入逻辑比较时，就没办法进行比较，因为pair的默认支持的是key和value⼀起参与比较，我们需要时的任何时候只比较key，所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给RBTree的KeyOfT，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进行比较，具体细节参考如下代码实现。

set.h:

template<class k>
class set
{
public:
	struct SetKeyofT
	{
		const k& operator()(const k& key)
		{
			return key;
		}
	};
	bool insert(const k& kv)
	{
		return _t.Insert(kv);
	}
private:
	qcj::RBTree<k,  const k, SetKeyofT> _t;
};

map.h:

template<class k,class v>
class map
{
public:
	struct MapKeyofT
	{
		const k& operator()(const pair<k, v>& key)
		{
			return key.first;
		}
	};
	bool insert(const pair<k, v>& kv) 
	{
		return _t.Insert(kv);
	}
private:
	qcj::RBTree<k, pair< const k, v>, MapKeyofT> _t;
};

insert:

bool Insert(const T& x) 
{
	if (_root == nullptr)//插入根节点
	{
		_root = new node(x);
		_root->col = BLACK;
		return true;
	};
	node* cur = _root;
	node* parent = nullptr;//保留父亲节点
	KeyofT kot;
	while (cur)
	{
		/*介质不冗余*/
		if (kot(x) < kot(cur->_date))
		{
			parent = cur;
			cur = cur->left;
		}
		else if (kot(x) > kot(cur->_date))
		{
			parent = cur;
			cur = cur->right;
		}
		else
		{
			return false;
		}
	}
	cur = new node(x);
	cur->col = RED;
	if (kot(x) > kot(parent->_date))
	{
		parent->right = cur;
	}
	else//相等插入左子树
	{
		parent->left = cur;
	}
	cur->parent = parent;
	while (parent&&parent->parent&&parent->col == RED)
	{
		node* grandfather = parent->parent;
		if (parent == grandfather->left)
		{
			node* uncle = grandfather->right;
			//         g
		    //       p    u
		    //     c  c
			//u存在且为红
			if (uncle&&uncle->col==RED)
			{
				parent->col = uncle->col=BLACK;
				grandfather->col = RED;
				cur = grandfather;
				parent = cur->parent;
			}
			//u不存在或存在为黑
			else
			{
				//         g
				//       p    
				//     c
				if (cur == parent->left)
				{
					RoRateR(grandfather);
					parent->col = BLACK;
					grandfather->col = RED;
				}
				//         g
				//       p    
				//         c
				else
				{
					RoRateL(parent);
					RoRateR(grandfather);
					cur->col = BLACK;
					grandfather->col = RED;
				}
				break;
			}
		}
		else
		{
			node* uncle = grandfather->left;
			//         g
			//       u   p    
			//          c  c
			//u存在且为红
			if (uncle && uncle->col == RED)
			{
				parent->col = uncle->col = BLACK;
				grandfather->col = RED;
				cur = grandfather;
				parent = cur->parent;
			}
			//u不存在或存在为黑
			else
			{
				//         g
				//            p    
				//              c
				if (cur == parent->right)
				{
					RoRateL(grandfather);
					parent->col = BLACK;
					grandfather->col = RED;
				}
				//         g
				//            p    
				//          c
				else
				{
					RoRateR(parent);
					RoRateL(grandfather);
					cur->col = BLACK;
					grandfather->col = RED;
				}
				break;
			}
		}
	}
	_root->col = BLACK;//循环结束把根变黑
	return true;
}

find：

node* Find(const k& x)
{
	node* ret = nullptr;
	node* cur = _root;
	while (cur)
	{
		if (x < kot(cur))
		{
			cur = cur->left;
		}
		else if (x > kot(cur))
		{
			cur = cur->right;
		}
		else
		{
			ret = cur;//保留当前节点
			cur = cur->left;//继续向左子树查找中序的第一个
		}
	}
	return ret;
}

这里通过仿函数就取出key控制了比较逻辑。

三.迭代器

3.1思路分析

  • operator++
  • operator- -
  • 迭代器的key修改问题

    如果我们这样实现的迭代器是可以修改的key的。
    但是红黑树的key是不能被修改的。那怎么办呢？
    我们只需要把红黑树的第二个模版参数的key改为
    const key即可这样迭代器的模版参数T的key也是const的了
    set的iterator也不支持修改，我们把set的第⼆个模板参数改成const K即可， 
qcj::RBTree<k, pair< const k, v>, MapKeyofT> _t;
qcj::RBTree<k,  const k, SetKeyofT> _t;

  • 对比库里的迭代器
    为了实现反向迭代器我们可以在operator- -多加一个判断。
    同时还需要在迭代器里面加一个_root节点
    在这里插入图片描述

  • 运算符重载
    运算符重载比较简单具体参考下面的代码

3.2 代码实现

template<class T,class Ref,class Ptr>
struct RBTreeIteraor
{
	using node= RBNode<T>;
	using self= RBTreeIteraor< T, Ref, Ptr >;
	node* _node;
	node* _root;
	RBTreeIteraor(node* Node,node* root)
		:_node(Node)
		,_root(root)
	{}
	self& operator++()
	{
		if (_node == nullptr)
		{
			node* cur = _root;
			while (cur->right)
			{
				cur = cur->right;
			}
		}
		else if (_node->right!=nullptr)
		{
			node* cur = _node->right;
			while (cur->left)
			{
				cur = cur->left;
			}
			_node = cur;
		}
		else
		{
			node* parent = _node->parent;
			while (parent&&_node != parent->left)
			{
				_node = parent;
				parent = _node->parent;
			}
			_node = parent;
		}
		return *this;
	}
	self& operator--()
	{
		if (_node == nullptr)
		{
			node* cur = _root;
			while (cur->right)
			{
				cur = cur->right;
			}
			_node = cur;
		}
		else if (_node->left != nullptr)
		{
			node* cur = _node->left;
			while (cur->right)
			{
				cur = cur->right;
			}
			_node = cur;
		}
		else
		{
			node* parent = _node->parent;
			while (parent && _node != parent->right)
			{
				_node = parent;
				parent = _node->parent;
			}
			_node = parent;
		}
		return *this;
	}
	Ref operator*()
	{
		return _node->_date;
	}
	Ptr operator->()
	{
		return &_node->_date;
	}
	bool operator==(const self& tmp) const
	{
		return _node==tmp._node;
	}
	bool operator!=(const self& tmp) const
	{
		return _node != tmp._node;
	}
};

四.operator[]

4.1思路分析

对于map我们还需要支持operator[]。
对于operator[]我们前面已经讲过底层实现了。
参考博文：map的operator[]底层剖析
主要就是insert来支持的。改一下返回值即可。
让insert返回迭代器和bool的pair即可。
返回insert迭代器的second也就是value即可。

v& operator[](const k& key)
{
	pair<iterator, bool> ret = _t.Insert(make_pair(key, v()));
	return ret.first->second;
}

五.源码

  • set.h
#pragma once
#include"RBTree.h"
namespace qcj
{
	template<class k>
	class set
	{
	public:
		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();
		}
		iterator end()
		{
			return _t.End();
		}
		const_iterator begin() const
		{
			return _t.Begin();
		}
		const_iterator end() const
		{
			return _t.End();
		}
		pair<iterator, bool> insert(const k& kv)
		{
			return _t.Insert(kv);
		}
		iterator find(const k& key)
		{
			return _t.find(key);
		}
	private:
		qcj::RBTree<k,  const k, SetKeyofT> _t;
	};
	void Print(const set<int>& s)
	{
		set<int>::iterator it = s.end();
		while (it != s.begin())
		{
			--it;
			// 不⽀持修改
			//*it += 2;
			cout << *it << " ";
		}
		cout << endl;
	}
	void test_set()
	{
		set<int> s;
		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
		for (auto e : a)
		{
			s.insert(e);
		}
		for (auto e : s)
		{
			e += 1;
			cout << e << " ";
		}
		cout << endl;
	}

}
  • map.h
#pragma once
#include"RBTree.h"
namespace qcj 
{
	template<class k,class v>
	class map
	{
	public:
		struct MapKeyofT
		{
			const k& operator()(const pair<k, v>& key)
			{
				return key.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();
		}
		iterator end()
		{
			return _t.End();
		}
		const_iterator begin() const
		{
			return _t.Begin();
		}
		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)
		{
			return _t.find(key);
		}
		v& operator[](const k& key)
		{
			pair<iterator, bool> ret = _t.Insert(make_pair(key, v()));
			return ret.first->second;
		}
	private:
		qcj::RBTree<k, pair< const k, v>, MapKeyofT> _t;
	};
	void test_map()
	{
		map<int,int> dict;
		dict.insert({1,1});
		dict.insert({2,2 });
		dict.insert({3,3 });
		dict.insert({ 4,4 });
		dict.insert({ 5,5 });
		dict.insert({ 6,6 });
		map<int,int>::iterator it = dict.end();
		while (it != dict.begin())
		{
			--it;
			// 不能修改first，可以修改second
			//it->first += 'x';
			it->second += 1;
			cout << it->first << ":" << it->second << endl;
		}
		cout << endl;
	}
}
  • RBTree.h
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace qcj
{
	enum coloros
	{
		RED,
	    BLACK
	};
	template<class T>
	struct RBNode
	{
		using node= RBNode<T>;
		T _date;
		node* left;//左节点
		node* right;//右节点
		node* parent;//父亲节点
		coloros col;//颜色
		RBNode(const T& date)
			:_date(date)
			, left(nullptr)
			, right(nullptr)
			, parent(nullptr)
		{}
	};
	template<class T,class Ref,class Ptr>
	struct RBTreeIteraor
	{
		using node= RBNode<T>;
		using self= RBTreeIteraor< T, Ref, Ptr >;
		node* _node;
		node* _root;
		RBTreeIteraor(node* Node,node* root)
			:_node(Node)
			,_root(root)
		{}
		self& operator++()
		{
			if (_node == nullptr)
			{
				node* cur = _root;
				while (cur->right)
				{
					cur = cur->right;
				}
			}
			else if (_node->right!=nullptr)
			{
				node* cur = _node->right;
				while (cur->left)
				{
					cur = cur->left;
				}
				_node = cur;
			}
			else
			{
				node* parent = _node->parent;
				while (parent&&_node != parent->left)
				{
					_node = parent;
					parent = _node->parent;
				}
				_node = parent;
			}
			return *this;
		}
		self& operator--()
		{
			if (_node == nullptr)
			{
				node* cur = _root;
				while (cur->right)
				{
					cur = cur->right;
				}
				_node = cur;
			}
			else if (_node->left != nullptr)
			{
				node* cur = _node->left;
				while (cur->right)
				{
					cur = cur->right;
				}
				_node = cur;
			}
			else
			{
				node* parent = _node->parent;
				while (parent && _node != parent->right)
				{
					_node = parent;
					parent = _node->parent;
				}
				_node = parent;
			}
			return *this;
		}
		Ref operator*()
		{
			return _node->_date;
		}
		Ptr operator->()
		{
			return &_node->_date;
		}
		bool operator==(const self& tmp) const
		{
			return _node==tmp._node;
		}
		bool operator!=(const self& tmp) const
		{
			return _node != tmp._node;
		}
	};
	template<class k, class T, class KeyofT>
	class RBTree
	{
		using node = RBNode<T>;
	public:
		RBTree() = default;
		using Iterator = RBTreeIteraor<T, T&, T*>;
		using Const_Iterator = RBTreeIteraor<T, const T&, const T*>;
		Iterator Begin()
		{
			node* cur = _root;
			while (cur&&cur->left)
			{
				cur = cur->left;
			}
			return Iterator(cur,_root );
		}
		Iterator End()
		{
			return Iterator(nullptr,_root);
		}
		Const_Iterator Begin() const
		{
			node* cur = _root;
			while (cur&&cur->left)
			{
				cur = cur->left;
			}
			return { cur,_root };
		}
		Const_Iterator End() const
		{
			return { nullptr,_root };
		}
		void Destory(const node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			Destory(root->left);
			Destory(root->right);
			delete root;
		}
		~RBTree()
		{
			Destory(_root);
			_root = nullptr;
		}
		RBTree<k,T,KeyofT>& operator = (RBTree<k, T, KeyofT> tmp)
		{
			swap(_root, tmp._root);
			return *this;
		}
		RBTree(const RBTree<k, T, KeyofT>& x)
		{
			_root = Copy(x._root,nullptr);
		}
		node* Copy(node* x,node* parent)
		{
			if (x == nullptr)
			{
				return x;
			}
			node* root = new node(x->_date);
			root->parent = parent;
			root->left = Copy(x->left,root);
			root->right = Copy(x->right,root);
			return root;
		}
		void RoRateR(node* parent)//右单旋
		{
			node* subL = parent->left;
			node* subLR = subL->right;
			node* pparnet = parent->parent;
			parent->left = subLR;
			if (subLR)
			{
				subLR->parent = parent;//修改父节点
			}
			subL->right = parent;
			parent->parent = subL;
			if (pparnet == nullptr)//parent就是根节点
			{
				_root = subL;
				subL->parent = nullptr;
			}
			else
			{
				if (pparnet->left == parent)//确定parent节点是左还是右
				{
					pparnet->left = subL;
				}
				else
				{
					pparnet->right = subL;
				}
				subL->parent = pparnet;//修改父节点
			}
		}
		void RoRateL(node* parent)//左单旋
		{
			node* subR = parent->right;
			node* subRL = subR->left;
			node* pparnet = parent->parent;
			parent->right = subRL;
			if (subRL)//防止subRL为空
			{
				subRL->parent = parent;//修改父节点
			}
			subR->left = parent;
			parent->parent = subR;
			if (pparnet == nullptr)//parent就是根节点
			{
				_root = subR;
				subR->parent = nullptr;
			}
			else
			{
				if (pparnet->left == parent)//确定parent节点是左还是右
				{
					pparnet->left = subR;
				}
				else
				{
					pparnet->right = subR;
				}
				subR->parent = pparnet;//修改父节点
			}
		}
		pair<Iterator,bool> Insert(const T& x) 
		{
			if (_root == nullptr)//插入根节点
			{
				_root = new node(x);
				_root->col = BLACK;
				return make_pair(Iterator(_root, _root), true);
			};
			node* cur = _root;
			node* parent = nullptr;//保留父亲节点
			KeyofT kot;
			while (cur)
			{
				/*介质不冗余*/
				if (kot(x) < kot(cur->_date))
				{
					parent = cur;
					cur = cur->left;
				}
				else if (kot(x) > kot(cur->_date))
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					return make_pair(Iterator(cur, _root), true);
				}
			}
			cur = new node(x);
			cur->col = RED;
			if (kot(x) > kot(parent->_date))
			{
				parent->right = cur;
			}
			else//相等插入左子树
			{
				parent->left = cur;
			}
			cur->parent = parent;
			while (parent&&parent->parent&&parent->col == RED)
			{
				node* grandfather = parent->parent;
				if (parent == grandfather->left)
				{
					node* uncle = grandfather->right;
					//         g
				    //       p    u
				    //     c  c
					//u存在且为红
					if (uncle&&uncle->col==RED)
					{
						parent->col = uncle->col=BLACK;
						grandfather->col = RED;
						cur = grandfather;
						parent = cur->parent;
					}
					//u不存在或存在为黑
					else
					{
						//         g
						//       p    
						//     c
						if (cur == parent->left)
						{
							RoRateR(grandfather);
							parent->col = BLACK;
							grandfather->col = RED;
						}
						//         g
						//       p    
						//         c
						else
						{
							RoRateL(parent);
							RoRateR(grandfather);
							cur->col = BLACK;
							grandfather->col = RED;
						}
						break;
					}
				}
				else
				{
					node* uncle = grandfather->left;
					//         g
					//       u   p    
					//          c  c
					//u存在且为红
					if (uncle && uncle->col == RED)
					{
						parent->col = uncle->col = BLACK;
						grandfather->col = RED;
						cur = grandfather;
						parent = cur->parent;
					}
					//u不存在或存在为黑
					else
					{
						//         g
						//            p    
						//              c
						if (cur == parent->right)
						{
							RoRateL(grandfather);
							parent->col = BLACK;
							grandfather->col = RED;
						}
						//         g
						//            p    
						//          c
						else
						{
							RoRateR(parent);
							RoRateL(grandfather);
							cur->col = BLACK;
							grandfather->col = RED;
						}
						break;
					}
				}
			}
			_root->col = BLACK;//循环结束把根变黑
			return make_pair(Iterator(cur, _root), true);
		}
		bool check(node* cur,size_t tmp,size_t sum)
		{
			if (cur == nullptr)
			{
				if (tmp != sum)
				{
					cout << "存在黑色结点的数量不相等的路径" << endl;
					return false;
				}
				return true;
			}
			if (cur->col == RED)
			{
				if (cur->parent->col == RED)
				{
					cout << cur->_key << ":" << "存在连续红节点" << endl;
					return false;
				}
			}
			else
			{
				sum++;
			}
			return check(cur->left, tmp, sum) && check(cur->right, tmp, sum);
		}
		bool ISRBTree()
		{
			 return _ISRBTree(_root);
		}
		bool _ISRBTree(node* cur)
		{
			if (cur == nullptr)
			{
				return true;
			}
			if (cur->col == RED)
			{
				return false;
			}
			size_t t = 0;
			while (cur)
			{
				if (cur->col == BLACK)
				{
					t++;
				}
				cur = cur->left;
			}
			return check(_root,t,0);
		}
		node* Find(const k& x)
		{
			node* ret = nullptr;
			node* cur = _root;
			while (cur)
			{
				if (x < kot(cur))
				{
					cur = cur->left;
				}
				else if (x > kot(cur))
				{
					cur = cur->right;
				}
				else
				{
					ret = cur;//保留当前节点
					cur = cur->left;//继续向左子树查找中序的第一个
				}
			}
			return ret;
		}
		void Inorder()
		{
			_Inorder(_root);
			cout << endl;
		}
		bool IsBalanceTree()
		{
			return _IsBalanceTree(_root);
		}
	    void _Inorder(const node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Inorder(root->left);
			cout << root->_key << ":" << root->_value << endl;
			_Inorder(root->right);
		}
		size_t Size()
		{
			return _Size(_root);
		}
		size_t _Size(const node* parent)
		{
			if (parent)
			{
				return 1 + _Size(parent->left) + _Size(parent->right);
			}
			else
			{
				return 0;
			}
		}
		size_t Height()
		{
			return _Height(_root);
		}
		size_t _Height(const node* parent)
		{
			if (parent)
			{
				return 1 + max(_Height(parent->left), _Height(parent->right));
			}
			else
			{
				return 0;
			}
		}
		bool Empty()
		{
			return _root == nullptr;
		}
	private:
		node* _root = nullptr;
	};
}

在这里插入图片描述

后言

这就是红黑树封装map和set深度剖析。大家自己好好消化！今天就分享到这！感谢各位的耐心垂阅！咱们下期见！拜拜~


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

相关文章：

  • Redis可视化工具--RedisDesktopManager的安装
  • GPT-5 传言：一场正在幕后发生的 AI 变革
  • Mysql常见问题处理集锦
  • 关于AWS网络架构的思考
  • python爬虫爬取淘宝商品比价||淘宝商品详情API接口
  • nginx 配置域名前缀访问 react 项目
  • 高性能、并发安全的 Go 嵌入式缓存库 如何使用？
  • 浅谈云计算22 | Kubernetes容器编排引擎
  • ASP.NET Core全球化与本地化：打造多语言应用
  • vulnhub靶场【jangow】靶机，考察反弹shell的流量及端口的选择
  • Transformer之Encoder
  • 如何在openEuler中编译安装Apache HTTP Server并设置服务管理（含Systemd和Init脚本）
  • 【Linux】线程全解：概念、操作、互斥与同步机制、线程池实现
  • linux下springboot项目nohup日志或tomcat日志切割处理方案
  • Redis集群部署详解：主从复制、Sentinel哨兵模式与Cluster集群的工作原理与配置
  • leetcode707-设计链表
  • 电脑风扇声音大怎么办? 原因及解决方法
  • github 端口22 超时问题解决
  • AWS物联网连接的数据记录器在冰川环境中的性能比较：Campbell CR1000X与ESP32开源
  • 【react】使用antd Table渲染数据遇到的报错问题
  • 用Cursor生成一个企业官网前端页面（生成腾讯、阿里官网静态页面）
  • redis安装教程（windows）
  • 从零到一：Spring Boot 与 RocketMQ 的完美集成指南
  • 25/1/18 嵌入式笔记 STM32F103
  • Golang——常用库sync
  • QT 使用QSqlTableModel对数据库进行创建，插入，显示