C++红黑树封装set和map（很详细）

前言

        在前面，我们学习了红黑树。（没学过红黑树直接看会很吃力）set和map的底层就是红黑树，现在我们要用这棵树来封装STL里面的容器：set和map。

        下面是之前讲过的红黑树，他只是普通的“Key”模型,适合封装set容器

        RBTree.h代码如下（这是之前的，还没封装好，后续会给上总代码）

#pragma once
 
enum color
{
	RED,
	BLACK
};
 
template<class K>
struct RBTreeNode
{
	RBTreeNode<K>* _parent;
	RBTreeNode<K>* _left;
	RBTreeNode<K>* _right;
	K _key;
	color _col;
	RBTreeNode(const K& key)
		:_key(key)
		,_parent(nullptr)
		,_left(nullptr)
		,_right(nullptr)
		,_col(RED)
	{}
};
 
template<class K>
class RBTree
{
	typedef RBTreeNode<K> Node;
public:
	bool Insert(const K& key)
	{
		Node* cur = _root;
		Node* parent = _root;
		if (_root == nullptr)
		{
			_root = new Node(key);
			_root->_col = BLACK;
			return true;
		}
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		if (parent->_key > key)
		{
			parent->_left = new Node(key);
			cur = parent->_left;
		}
		else
		{
			parent->_right = new Node(key);
			cur = parent->_right;
		}
		cur->_parent = parent;
		while (parent && parent->_col == RED)
		{
			Node* grandparent = parent->_parent;
 
			if (grandparent->_left == parent)
			{
				//     g
				//   p   u
				// c
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)
				{
					//变颜色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandparent->_col = RED;
					//往上更新
					cur = grandparent;
					parent = grandparent->_parent;
				}
				else
				{
					//     g
					//   p   u
					// c
					if(cur == parent->_left)
					{
						RotateR(grandparent);
						grandparent->_col = RED;
						parent->_col = BLACK;
						break;
					}
					//      g
					//   p     u
					//    c
					else
					{
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
				}
			}
			else  //grandparent->_right == parent
			{
				//     g
				//   u   p
				//         c
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					cur = grandparent;
					parent = grandparent->_parent;
				}
				else
				{
					//     g
					//   u   p
					//         c
					if (parent->_right == cur)
					{
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
					else
					{
						//     g
						//   u   p
						//      c
						RotateR(parent);
						RotateL(grandparent);
 
						cur->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
 
	bool Check(Node* root,int BlackNum,int valRef)
	{
		if (root == nullptr)
		{
			if(BlackNum == valRef)
			{
				return true;
			}
			else
			{
				cout << "每条路径黑色结点个数不等" << endl;
				return false;
			}
		}
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "有连续的红色节点" << endl;
			return false;
		}
		if (root->_col == BLACK)
		{
			BlackNum++;
		}
		return Check(root->_left,BlackNum,valRef) && Check(root->_right, BlackNum, valRef);
	}
 
	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col == RED)
			return false;
		int valRef = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				valRef++;
			cur = cur->_left;
		}
		int BlackNum = 0;
		return Check(_root,BlackNum,valRef);
	}
 
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		subL->_right = parent;
		Node* grandparent = parent->_parent;
		parent->_parent = subL;
		if (grandparent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
			return;
		}
		if (grandparent->_left == parent)
		{
			grandparent->_left = subL;
		}
		else
		{
			grandparent->_right = subL;
		}
		subL->_parent = grandparent;
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		subR->_left = parent;
		Node* grandparent = parent->_parent;
		parent->_parent = subR;
		if (grandparent == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
			return;
		}
		if (grandparent->_left == parent)
		{
			grandparent->_left = subR;
		}
		else
		{
			grandparent->_right = subR;
		}
		subR->_parent = grandparent;
	}
	Node* _root = nullptr;
};

一、修改模型

如果要封装map的“Key，Value” 容器，那么我们需要重新copy一份红黑树，改成“Key，Value” 模型去封装map，这样似乎也太笨了一点，我们看看写库函数的大佬是如何处理的。如何用一棵树封装map和set

这里提出了库里面的关键信息，其他内容看不懂没关系，只需要知道红黑树结点类型只有Value，通过类型Value来判断是“Key”还是“Key，Value”

1.set传递的第二个参数

我们再看一下set容器所传递的内容是什么，可以看到对Key  typedef了一下，给到红黑树的第二个参数value_type就是Key。这个value_type会传递给上面的Value。（注意看这里的私有成员是rb_tree类型的 t，调用的是上面图片的rb_tree）

2.map传递的第二个参数 

map容器 typedef 的value_type是pair<const Key,T>类型，因此map传递给红黑树的第二个参数为pair<const Key,T>类型。

如此一来，可以通过一颗红黑树来实现“Key”和“Key，Value”模型。 那么他具体是怎么实现的，我们还需要进一步分析

3.修改RBTree.h与添加map.h和set.h

根据库里面的内容，我们也对自己的RBTree.h代码进行修改

RBTreeNode结点，根据库里面的，将模板类型K改成了T，K _key改成T _data更容易理解，_data是什么，我们不知道，要看你具体传什么内容，可能是单个key，可能是pair。

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

对于RBTree也要进行改造，模板参数添加上T类型， 插入具体的我只改了一点点，防止文章过与冗余，后面都要弄成data。（后续会给上总代码，大家先理解就好）

template<class K,class T>  //添加了T
class RBTree
{
	typedef RBTreeNode<T> Node;
    bool Insert(const T& data)  //修改部分
	{
		Node* cur = _root;
		Node* parent = _root;
		if (_root == nullptr)
		{
			_root = new Node(data);  //修改部分
			_root->_col = BLACK;
			return true;
		}
    .........//后续还有很多内容，这里就不多改造了
    }
}

写出set.h     （仿函数不添加，防止混乱）跟库里面的一样，传递的第二个参数为K类型

#pragma once
#include"RBTree.h"
namespace kky
{
	template<class K>
	class set
	{
	private:
        RBTree<K, K> _t;
	};
}

写出map.h      跟库里面的一样，传递的第二个参数为pair类型

#pragma once
#include"RBTree.h"
namespace kky
{
	template<class K,class V>
	class map
	{
	private:
		RBTree<K, pair<const K, V>> _t;
	};
}

这里有点绕，现在我们再来捋一捋。

你是map，那么你传递的第二个参数T是pair，通过T构建出来的结点也是pair类型，里面存放的_data自然是pair类型。

你是set，你传递的第二个参数T是K，通过T构建出来的结点也是K类型，里面存放的_data自然是K类型。

4.仿函数取出set中的key和map中的key 

  • 那么现在问题又来了，这样就可以构建出来了吗？我们代码逻辑部分会不会有点问题？

大家看下面的代码，这是一个插入时的比较代码，看存放的数据比当前结点大还是小，如果大，往右走，如果小往左走，后面就是找到合适的地方再进行插入。

对于set来说，这句代码没有问题，可以这样比较。

对于map呢？map中的pair支不支持比较呢？我们去C++文档里面查一下，如下发现pair支持比较大小，但是他是first小就小，first如果相等，那么second小就小（这里代码使用了复用，仔细分析一下就是这个意思）

但是我们需要的不是这样啊，map我们只比较key，不比较value，如果key相等，就不要处理了，返回false（set和map的key不能重复）。库函数的比较我们用不上，我们需要自己写仿函数去判断。

现在的重点是将_data里面的key取出来比较。库里面是选择添加一个类型KeyOfValue。如下

那么具体是如何做到添加一个类模板对象，就做到可以如此比较的呢？ （这里不懂没关系，下面我们还有图）

首先在set和map创建上KeyofValue类，目的是通过仿函数取出Key

set.h 添加上SetKeyofT，函数内部就是走个过场，直接取出key。并传递给RBTree，当做第三个参数。

public:
    struct SetKeyofT
    {
	    const K& operator()(const K& key)
	    {
	    	return key;
	    }
    };
private:
    RBTree<K, K,SetKeyofT> _t;

map.h 添加上MapKeyofT，目的是取出pair里面的first（也就是key），并将MapKeyofT传递给RBTree，当做第三个参数。 

public:
	struct MapKeyofT
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};
private:
	RBTree<K, pair<const K, V>,MapKeyofT> _t;

RBTree.h 修改  ，添加了第三个模板参数KeyofT，并使用KeyofT构建对象koft，对需要进行_data比较的地方，都是用koft仿函数处理。

template<class K,class T,class KeyOfT>
class RBTree
{
    KeyOfT koft;  //构建对象
	typedef RBTreeNode<T> Node;
public:
    pair<Node*,bool> Insert(const T& data)
    {
	    Node* cur = _root;
	    Node* parent = _root;
	    if (_root == nullptr)
	    {
		    _root = new Node(data);
		    _root->_col = BLACK;
		    return make_pair(_root,true) ;
	    }
	    while (cur)
	    {
		    if (koft(cur->_data) < koft(data))
		    {
			    parent = cur;
			    cur = cur->_right;
		    }
		    else if (koft(cur->_data) > koft(data))
		    {
			    parent = cur;
			    cur = cur->_left;
		    }
	        else
	        {
		        return make_pair(cur, false);
	        }
        }
        if (koft(parent->_data) > koft(data))
        {
	        parent->_left = new Node(data);
	        cur = parent->_left;
        }
        //后续内容没有比较，无需修改
    }
};

那么现在我们再画图捋一捋，

你是map，构建出的树第三个参数就是MapKeyofT，因此使用koft去调用_data数据，你获取的就是_data里面的first。

你是set，构建出的树第三个参数就是SetKeyofT，因此使用koft去调用_data数据，你获取的就是_data本身（这里的_data就是key）。

相当于set是陪太子读书，因为太子（map）需要使用koft去取出第一个数据，那么你set也得去这样取，就算你本身就是key，也这样跟这太子取，谁让他map是太子呢？

（这里逻辑其实并不复杂，只是有点点绕，大家不懂可以发评论问我）

注意：图片中的Insert函数返回类型大家看不懂可以忽略,当做bool就好，这是为了后续实现operator[]使用的（后面会讲）

到了现在，我们只需在set和map里面添加上insert函数就行，因为我们现在已经有了_t这颗树，因此调用_t树的Insert函数就好。

set.h 添加

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

map.h 添加 

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

现在就可以插入运行一下，看看我们封装得咋样了（iterator也不用管，后续会讲解，这里只做打印） 

二、迭代器

1.迭代器基础

那么插入的基本逻辑，我们已经实现了，现在开搞迭代器，家人们，又是大坑来了，我们耐下性子慢慢来。

首先，map和set的迭代器只需要第二个参数------T  就可以了。他的成员函数只有红黑树结点_node，通过结点_node来进行构造迭代器，operator* 、 operator->、!=、==都很简单，这里我们不多赘述，代码如下

template<class T>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T> Self;
	__TreeIterator(Node* node)
		:_node(node)
	{}
	T& operator*()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}
    bool operator!=(const Self& s)
    {
	    return _node != s._node;
    }

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

2.迭代器++

  • 那么迭代器中很重要的++呢？

大家知道，在之前我们学习string、vector、list的时候，他们都是线性表，++往后面走就可以了，现在学到的set和map是树形结构，他的++应该如何走？ 

如图，it 在1的位置，那么it++，应该到6的地方去，那么我们可以知道，当前节点的右子树不为空，我们++需要到右子树的最左结点去。那么如果我们现在在6的地方，再++应该去到8的地方，那么我们又可以知道，当parent->right==cur时，我们需要再往上面走，一直走到parent->left == cur的时候才停止，再去遍历parent节点。不理解没关系，我们后面画图分析

为什么会这样？因为中序是左根右，当前结点已经遍历完了，证明左和根已经遍历完毕，需要遍历右边，当右边遍历完毕，证明该树遍历完毕，也就是遍历完了父亲的左子树（该树就是左子树），应该去遍历父亲节点

关键点是如果当前节点右为空，看当前节点是父亲的左还是右，是左就遍历父亲，是右就往上面走，知道当前节点是父亲的左。

 根据我们的分析，++代码如下 _node为迭代器成员变量

Self& operator++()
{
	if (_node->_right)  //右树存在  找右树最左节点
	{
		Node* cur = _node->_right;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		_node = cur;
	}
	else    //右树不存在  往上迭代
	{
		Node* cur = _node;
		Node* parent = _node->_parent;
		while (parent && parent->_right == cur)
		{
			cur = parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}

3.迭代器--

迭代器--跟++不能说一模一样，只能说毫无差距，他们是相反的，直接上代码

Self& operator--()
{
	if (_node->_left)
	{
		Node* cur = _node->_left;
		while (cur->_right)
		{
			cur = cur->_right;
		}
		_node = cur;
	}
	else
	{
		Node* cur = _node;
		Node* parent = _node->_parent;
		while (parent && parent->_left == cur)
		{
			cur = parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}

4.添加begin()、end()

RBTree.h添加迭代器和begin()、end()

typedef __TreeIterator<T> iterator;
iterator begin()
{
	Node* cur = _root;
	while (cur && cur->_left)
	{
		cur = cur->_left;
	}
	return iterator(cur);
}

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

set.h 

typedef RBTree<T>::iterator iterator;
iterator begin()
{
	return _t.begin();
}

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

 map.h

typedef RBTree<pair<const K, V>>::iterator iterator;
iterator begin()
{
	return _t.begin();
}

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

但是当我们编译时却报错了这是为什么呢？

首先，这个iterator是RBTree里面的，而RBTree里面的iterator也是typedef过的，是__TreeIterator里面的。

因此在set里面的RBTree<K, K, SetKeyofT>::iterator是内嵌类型，还没有实例化，编译器在编译时不知道他是什么类型，根本就不认识他，我们需要给set里面的RBTree<K, K, SetKeyofT>::iterator给添加上typename，告诉编译器这里是类型，你现在先不急着去找他，等到对象实例化的时候，你再去取出他的类型。如下

typedef typename RBTree<K,K,SetKeyofT>::iterator iterator;

现在迭代器才算构建好，set和map可以运行了。

三、map的operator[] 

再把operator[]给实现一下，C++文档里面的operator[]如下

这里有点绕，看不懂很正常，我们拆分一下 ，如下

根据我们的分析，operator[]首先会执行插入，无论成功还是失败会取到该树的迭代器的Value。还有一点就是insert的返回类型为pair<iterator,bool>，之前为了代码简单，我们写的insert返回类型是bool。

因此我们需要修改insert的返回类型，同时修改函数内部return 后接上的内容，如下，下面还有的return也需要修改，这里不过多展开，不多赘述。

 set.h也修改                                                                             map.h也修改

并在map.h里面添加上，我们写绕一点，更容易理解，库里面的大佬写法学不会。

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

测试一下结果，nice完成啦！！！！

四、const迭代器

1.set的const迭代器 

我们的代码还有一点点问题，如下，set的key竟然可以修改，这并不是我们想要的。

库里面set是如下处理的，首先在RBTree里添加了const迭代器，然后set里面的普通迭代器和const迭代器都是调用的RBTree里的const迭代器，目的就是不要修改key值。

至于为什么需要const迭代器，这是STL的规定，因为之前的容器都有const迭代器。

map是的处理如下，普通的就是普通的，const就是const的，普通的key不可以修改，value可以修改，const迭代器key和value都不可以修改

那么现在我们的目的是要把const迭代器搞出来。

在红黑树的迭代器中，我们只有T& 和T*要去取出节点里面的值，那么为了防止修改，只需要给这两个地方添加上const就可以了。但是如果仅仅给T传参的时候传const T，那么肯定是不符合要求的，因为这样我们创建的结点Node的类型也是const T，那岂不是会让Node里面的_data或者其他内容无法修改，这肯定不行我们想要的。

因此我们可以借鉴库里的方法，类模板传递三个参数，修改方法如下，普通的就传递<T,T*,T&>，const的就传递<T,const T*,const T&>，这样就符合我们的要求了，是普通迭代器里面的内容就可以修改，const的无法修改

同时还得在RBTree里添加const版本的begin()和end()。 如下

const_iterator begin() const 
{
	Node* cur = _root;
	while (cur && cur->_left)
	{
		cur = cur->_left;
	}
	return const_iterator(cur);
}

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

同时在set里面修改一下，将iterator和const_iterator都typedef为RBTree里的const_iterator，这样就都没办法修改了，还有一点，我们并不需要再重写const_iterator的const版本的begin()和const版本的end()，因为虽然看着返回值是iterator，实际上被我们typedef成了const_iterator。只需要在结尾添加上const即可

现在我们就不能修改了。

但是现在我们取消了修改，代码还是报错了

报错内容为insert的时候类型匹配不上（注意，这里返回类型K写出了，应该为bool）

为什么会报这种错误呢 ？

看下面分析，set里的iterator被我们typedef了，他的本质是const_iterator 模板类型为<T,const T*,const T&>，而RBTree里面的iterator就是iterator模板类型为<T, T*,T&>，他们类型不一样。（这里并不是权限缩小的问题，是类模板参数不一样）

有点难理解没关系，我们再看下面，这样看是不是就更清楚了他们类型不一样

2.解决方案1（解决了set）（建议直接看解决方案2）

  • 那么对于这个报错我们可以如何修改呢？

其实很简单，只需要将RBTree里面的返回类型和返回结果修改一下就好，如下

虽然看起来有那么一点点非主流，但是这确实是一个可行方案，并且很容易理解 。

  •  那么为什么这样修改就可以运行了呢？

这就要提到pair的构造了，下面我们将pair的构造展开

现在分析一下，为什么pair<Node*,bool>能够初始化pair<const_iterator,bool>（第一个参数表面上是iterator，本质是const_iterator）？

因为const_iterator也是可以通过Node*来构造。这是我们迭代器的构造函数啊,如下

下面我们再捋一捋流程图，看看是怎么构造的，首先，set调用了插入，会调用RBTree的插入，返回回来类型，发现pair的类型不同，不能拷贝构造，于是他会尝试看能不能进行构造，发现__TreeIterator有这么一个类，并且可以构造，于是就完成了iterator的构造了。

3.map的const迭代器  

map的普通迭代器是key不能修改，而value可以修改，const迭代器是key和value都不可以修改，因此他不能像set一样，普通是const，const也是const。

我们在map里面添加上如下方框框起来的代码。

4.解决方案2（解决map和set）

再去看一看能不能运行map的const迭代器，并且查看map的second是否可以修改 

  •  那我们再仔细看看为何报错？

他们的区别是多了两个const

也就是这一句

我们翻译一下，他的意思就是不能从普通迭代器变成const迭代器，所针对的就是如下代码，从iterator到const_iterator这条路行不通

那么我们应该如何修改呢？

首先我们应该要想到构造函数，我们写出一个从iterator到const_iterator的构造函数就好了。具体如何写，我们还是可以参考一下库里面的内容。

库里面是如何操作的？

首先用类模板的第一个参数构造typedef一个iterator。这代表着无论你传递的Ref和Ptr是普通的还是const版本的，经过我只取第一个参数typedef的操作，我都能保证他是普通的，那么我用普通迭代器来进行构造。

1.如果你传递的Ref和Ptr是普通的，我就相当于拷贝构造。

2.如果你传递的Ref和Ptr是const的，我就相当于从普通版本，构造成了const版本。

这样就符合我们的条件了。

那我们跟着库里面进行编写代码 ，写出如下代码。

 再查看就不报错了，只有不能修改的错误，我们代码删除就好了

测试运行，大功告成！！！ 

五、总结 

回到之前的问题，为什么map和set的封装第一个参数需要K，能不能不要K？

先说答案，不能。虽然我们在insert插入函数里面并没有用到K类型，但如果是Find函数呢，你肯定是德通过Key类型去传递参数查找吧，我们所传递的第三个参数KeyOfT，他仅仅能取出第二参数T里面的内容，他不能推断T里面的参数类型，因此第一个参数K不能省略

map和set的封装并不比红黑树简单，需要肚兜理解，并且我们实现的还仅仅是简单版本，还有反向迭代器和除插入之外的函数都没有完成，但这一部分，也是足够我们学习红黑树和map、set的性质了。希望与大家共勉！！！

最后附上总代码 

RBTree.h

#pragma once

enum color
{
	RED,
	BLACK
};

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

template<class T,class Ptr,class Ref>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, T*, T&> iterator;
	typedef __TreeIterator<T,Ptr,Ref> Self;

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

	//iterator为普通迭代器，如果传入的Ptr和Ref是const版本
	//那么我们现在就是在用普通迭代器去构造const迭代器
	__TreeIterator(const iterator& it) 
		:_node(it._node)
	{}

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

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

	Self& operator++()
	{
		if (_node->_right)
		{
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Self& operator--()
	{
		if (_node->_left)
		{
			Node* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_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;
	}

	Node* _node;
};


// set->RBTree<K,K,SetKeyOfT> _t;
// map->RBTree<K.pair<K,T>,MapKeyOfT> _t;
template<class K,class T,class KeyOfT>
class RBTree
{
	KeyOfT koft;
	typedef RBTreeNode<T> Node;
public:
	typedef __TreeIterator <T,const T*,const T&> const_iterator;
	typedef __TreeIterator<T,T*,T&> iterator;
	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}

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

	const_iterator begin() const 
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return const_iterator(cur);
	}

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

	pair<iterator,bool> Insert(const T& data)
	{
		Node* cur = _root;
		Node* parent = _root;
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(_root,true) ;
		}
		while (cur)
		{
			if (koft(cur->_data) < koft(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (koft(cur->_data) > koft(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(cur, false);
			}
		}
		if (koft(parent->_data) > koft(data))
		{
			parent->_left = new Node(data);
			cur = parent->_left;
		}
		else
		{
			parent->_right = new Node(data);
			cur = parent->_right;
		}
		cur->_parent = parent;
		while (parent && parent->_col == RED)
		{
			Node* grandparent = parent->_parent;

			if (grandparent->_left == parent)
			{
				//     g
				//   p   u
				// c
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)
				{
					//变颜色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandparent->_col = RED;
					//往上更新
					cur = grandparent;
					parent = grandparent->_parent;
				}
				else
				{
					//     g
					//   p   u
					// c
					if(cur == parent->_left)
					{
						RotateR(grandparent);
						grandparent->_col = RED;
						parent->_col = BLACK;
						break;
					}
					//      g
					//   p     u
					//    c
					else
					{
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
				}
			}
			else  //grandparent->_right == parent
			{
				//     g
				//   u   p
				//         c
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					cur = grandparent;
					parent = grandparent->_parent;
				}
				else
				{
					//     g
					//   u   p
					//         c
					if (parent->_right == cur)
					{
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
					else
					{
						//     g
						//   u   p
						//      c
						RotateR(parent);
						RotateL(grandparent);

						cur->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
				}
			}
		}
		_root->_col = BLACK;
		return make_pair(cur, false);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool Check(Node* root,int BlackNum,int valRef)
	{
		if (root == nullptr)
		{
			if(BlackNum == valRef)
			{
				return true;
			}
			else
			{
				cout << "每条路径黑色结点个数不等" << endl;
				return false;
			}
		}
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "有连续的红色节点" << endl;
			return false;
		}
		if (root->_col == BLACK)
		{
			BlackNum++;
		}
		return Check(root->_left,BlackNum,valRef) && Check(root->_right, BlackNum, valRef);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col == RED)
			return false;
		int valRef = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				valRef++;
			cur = cur->_left;
		}
		int BlackNum = 0;
		return Check(_root,BlackNum,valRef);
	}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_data << " ";
		_InOrder(root->_right);
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		subL->_right = parent;
		Node* grandparent = parent->_parent;
		parent->_parent = subL;
		if (grandparent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
			return;
		}
		if (grandparent->_left == parent)
		{
			grandparent->_left = subL;
		}
		else
		{
			grandparent->_right = subL;
		}
		subL->_parent = grandparent;
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		subR->_left = parent;
		Node* grandparent = parent->_parent;
		parent->_parent = subR;
		if (grandparent == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
			return;
		}
		if (grandparent->_left == parent)
		{
			grandparent->_left = subR;
		}
		else
		{
			grandparent->_right = subR;
		}
		subR->_parent = grandparent;
	}
	Node* _root = nullptr;
};

 set.h

#pragma once
#include"RBTree.h"
namespace kky
{
	template<class K>
	class set
	{
	public:
		struct SetKeyofT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
		//对类模板取内嵌类型，需要加typename告诉编译器这是类型,等对象实例化
		typedef typename RBTree<K,K,SetKeyofT>::const_iterator iterator;
		typedef typename RBTree<K,K,SetKeyofT>::const_iterator const_iterator;
		iterator begin() const
		{
			return _t.begin();
		}

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

		pair<iterator, bool> Insert(const K& key)
		{
			return _t.Insert(key);
		}
		bool IsBalance()
		{
			return _t.IsBalance();
		}
		void InOrder()
		{
			_t.InOrder();
		}
	private:RBTree<K, K,SetKeyofT> _t;
	};
}

map.h

#pragma once
#include"RBTree.h"
namespace kky
{
	template<class K,class V>
	class map
	{
	public:
		struct MapKeyofT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
		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);
		}
		bool IsBalance()
		{
			return _t.IsBalance();
		}
		void InOrder()
		{
			_t.InOrder();
		}
		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;
	};
}

Test.cpp

#include<iostream>
#include<vector>
#include<ctime>
using namespace std;
#include"RBTree.h"
#include"map.h"
#include"set.h"

void set_test()
{
	//const int N = 10;
	//vector<int> v;
	//v.reserve(N);
	//srand(time(0));
	//for (size_t i = 0; i < N; i++)
	//{
	//	v.push_back(rand() + i);
	//}
	//kky::set<int> rbt;
	//for (auto e : v)
	//{
	//	if (e == 24473)
	//	{
	//		int i = 0;
	//	}
	//	rbt.Insert(e);
	//	rbt.IsBalance();
	//}
	//rbt.InOrder();
	//cout << rbt.IsBalance() << endl;

	kky::set<int> rbt;
	rbt.Insert(4);
	rbt.Insert(6);
	rbt.Insert(5);
	rbt.Insert(3);
	kky::set<int>::const_iterator it = rbt.begin();
	while (it != rbt.end())
	{
		cout << *it << endl;
		++it;
	}
}

void map_test()
{
	string arr[] = {"香蕉","苹果","橘子","香蕉","苹果" ,"香蕉","苹果" ,"香蕉" };
	kky::map<string,int> rbt;
	for (auto e : arr)
	{
		rbt[e]++;
	}
	kky::map<string,int>::const_iterator it = rbt.begin();
	while (it != rbt.end())
	{
		cout << it->first<<" "<<it->second << endl;
		++it;
	}
	//kky::map<string, string> dict;
	//dict.Insert(make_pair("sort", "排序"));
	//dict.Insert(make_pair("sort", "xx"));
	//dict.Insert(make_pair("left", "左"));
	//dict.Insert(make_pair("right", "右"));
	//kky::map<string,string>::iterator it = dict.begin();
	//while (it != dict.end())
	//{
	//	cout << it->first<<" "<<it->second << endl;
	//	++it;
	//}
}

int main()
{
	set_test();
	map_test();
}

最后感谢大家的观看 ！！！！

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

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

相关文章

技术博客：Vue中各种混淆用法汇总

技术博客：Vue中各种混淆用法汇总

技术博客&#xff1a;Vue中各种混淆用法汇总 摘要 本文主要介绍了在Vue中使用的一些常见混淆用法&#xff0c;包括new Vue()、export default {}、createApp()、Vue.component、Vue3注册全局组件、Vue.use()等&#xff0c;以及如何使用混淆器对代码进行加固&#xff0c;保护应…
阅读更多...
Opencv库如何检测图片中鸡蛋数量

Opencv库如何检测图片中鸡蛋数量

Opencv库检测图片中鸡蛋数量 由于需要写一个检测鸡蛋数量的程序&#xff0c;用了几个opencv中的经典方法&#xff0c;实现了图片中鸡蛋的检测。在一步步实现的同时&#xff0c;同时说明每个方法的用途。希望能给学习opencv的小伙伴一些帮助。下图为原始图和实现后的检测边框。…
阅读更多...
csdn-添加目录

csdn-添加目录

只需一句&#xff0c;根据文章标题层级自动生成目录 在文章内添加下面这句会自动生成目录 [TOC](此处填写目录的标题)
阅读更多...
【CMake入门】第一节——CMake的安装与简单样例

【CMake入门】第一节——CMake的安装与简单样例

CMake——Cross platform Make CMake是一个开源的跨平台自动化建构系统&#xff0c;用来管理程序构建&#xff0c;不相依于特定编译器&#xff0c;不用亲自编写Makefile。需要编写CMakeList.txt文件来定制整个编译流程可以自动化编译源代码、创建库、生成可执行二进制文件等 …
阅读更多...
msvcr110.dll丢失的解决方法有哪些-常见方法教程

msvcr110.dll丢失的解决方法有哪些-常见方法教程

我们在日常使用电脑中经常遇到各种问题&#xff0c;比如系统文件丢失是最常见的&#xff0c;其中msvcr110.dll丢失也是非常常见的问题&#xff0c;那么msvcr110.dll文件为什么会丢失&#xff0c;丢失对电脑有什么影响呢&#xff0c;丢失了有什么解决方法&#xff1f;今天小编就…
阅读更多...
【MySQL】聚合函数和分组（查找）

【MySQL】聚合函数和分组（查找）

聚合函数分组分组聚合如何显示每个部门的平均工资和最高工资显示每个部门的每种岗位的平均工资和最低工资显示平均工资低于2000的部门和它的平均工资(SMITH员工不参与)where 和 having 的区别 聚合函数 函数说明COUNT([DISTINCT] expr)返回查询到的数据的 数量SUM([DISTINCT] …
阅读更多...
深度学习助力手写识别OCR软件的发展与应用

深度学习助力手写识别OCR软件的发展与应用

随着人工智能和深度学习技术的不断发展&#xff0c;手写识别OCR软件的技术也在不断进步。目前&#xff0c;市场上已经有一些基于深度学习的手写识别OCR软件&#xff0c;可以对手写文字进行自动识别和转换。 首先&#xff0c;我们来介绍一下基于深度学习的手写识别OCR软件的基本…
阅读更多...
C语言能判断一个变量是int还是float吗？

C语言能判断一个变量是int还是float吗？

C语言能判断一个变量是int还是float吗&#xff1f; 在开始前我有一些资料&#xff0c;是我根据自己从业十年经验&#xff0c;熬夜搞了几个通宵&#xff0c;精心整理了一份「C语言从专业入门到高级教程工具包」&#xff0c;点个关注&#xff0c;全部无偿共享给大家&#xff01;&…
阅读更多...
Qnx boot workflow

Qnx boot workflow

S820A QNX Hypervisor Software User Guide 80-CF838-1 Rev. Img 生成脚本： target/hypervisor/host/create_images.sh tools/build/image-builder.sh The QVM config file for the guest is instantiated within the host rootfs build file, located at root/target/hyp…
阅读更多...
python和php语言编写大型爬虫那个更适用 ？

python和php语言编写大型爬虫那个更适用 ？

以我多年从事爬虫行业的经验来说&#xff0c;其实python和php两种语言都可以用于编写大型爬虫项目&#xff0c;但是因为Python语言简洁方便&#xff0c;第三方库相比有很多&#xff0c;数据处理能力也很强&#xff0c;所以受到大多数程序员的追捧。 Python和PHP都可以用于编写…
阅读更多...
多平台展示预约的服装小程序效果如何

多平台展示预约的服装小程序效果如何

线下实体服装店非常多&#xff0c;主要以同城生意为主&#xff0c;但随着电商经济增长&#xff0c;传统线下自然流量变少&#xff0c;商家们会选择线上入驻平台开店获得更多线上用户&#xff0c;包括自建私域小程序等。 而除了直接卖货外&#xff0c;线上展示预约在服装行业也…
阅读更多...
人工智能-机器翻译：技术发展与代码实战

人工智能-机器翻译：技术发展与代码实战

在本文中&#xff0c;我们深入探讨了机器翻译的历史、核心技术、特别是神经机器翻译&#xff08;NMT&#xff09;的发展&#xff0c;分析了模型的优化、挑战及其在不同领域的应用案例。同时&#xff0c;我们还提出了对未来机器翻译技术发展的展望和潜在的社会影响。 关注TechLe…
阅读更多...
class049 滑动窗口技巧与相关题目【算法】

class049 滑动窗口技巧与相关题目【算法】

class049 滑动窗口技巧与相关题目【算法】 算法讲解049【必备】滑动窗口技巧与相关题目 code1 209. 长度最小的子数组 // 累加和大于等于target的最短子数组长度 // 给定一个含有 n 个正整数的数组和一个正整数 target // 找到累加和 > target 的长度最小的子数组并返回…
阅读更多...
docker配置阿里云镜像加速器

docker配置阿里云镜像加速器

docker配置阿里云镜像加速器 1.注册一个阿里云账户 https://cr.console.aliyun.com/ 2.获取加速器地址链接 可直接复制&#xff0c;位置如下: 3.配置脚本 这个位置可以直接复制脚本&#xff0c;大家操作的时候直接复制自己的就好 sudo mkdir -p /etc/docker sudo tee /et…
阅读更多...
应用于指纹门锁上的安全芯片ACM32FP421系列，内核性能高，安全性高，内建 AES、CRC、TRNG 等算法模块

应用于指纹门锁上的安全芯片ACM32FP421系列，内核性能高，安全性高，内建 AES、CRC、TRNG 等算法模块

ACM32FP421 芯片的内核基于 ARMv8-M 架构&#xff0c;支持 Cortex-M33 和 Cortex-M4F 指令集。内核支持一 整套 DSP 指令用于数字信号处理&#xff0c;支持单精度 FPU 处理浮点数据&#xff0c;同时还支持 Memory Protection Unit &#xff08;MPU&#xff09;用于提升应用的安…
阅读更多...
数字化未来，亚马逊鲲鹏系统引领全新购物下单体验

数字化未来，亚马逊鲲鹏系统引领全新购物下单体验

随着科技的不断发展&#xff0c;人们的购物方式也在发生翻天覆地的变化。在这个数字化时代&#xff0c;亚马逊鲲鹏系统应运而生&#xff0c;成为一款集注册、买家号智能养号、自动下单、自动留评、QA等功能于一体的综合软件&#xff0c;为用户提供了全新的购物体验。 首先&…
阅读更多...
RocketMQ-源码架构二

RocketMQ-源码架构二

梳理一些比较完整&#xff0c;比较复杂的业务线 消息持久化设计 RocketMQ的持久化文件结构 消息持久化也就是将内存中的消息写入到本地磁盘的过程。而磁盘IO操作通常是一个很耗性能&#xff0c;很慢的操作&#xff0c;所以&#xff0c;对消息持久化机制的设计&#xff0c;是…
阅读更多...
单片机的基本概念——什么是单片机、单片机的分类以及单片机的发展历史、发展趋势

单片机的基本概念——什么是单片机、单片机的分类以及单片机的发展历史、发展趋势

什么是单片机 本文主要涉及了什么是单片机、单片机的分类、单片机发展史以及单片机的发展趋势的一些内容 文章目录 什么是单片机一、 什么是单片机1.1 微型计算机1.2 单板机1.3 单片机1.3.1 单片机的分类 二、 单片机的发展历史2.1 发展阶段2.2 单片机的特点2.3 单片机的发展趋…
阅读更多...
ACM32F403/F433 12 位多通道，支持 MPU 存储保护功能，应用于工业控制，智能家居等产品中

ACM32F403/F433 12 位多通道，支持 MPU 存储保护功能，应用于工业控制，智能家居等产品中

ACM32F403/F433 芯片的内核基于 ARMv8-M 架构&#xff0c;支持 Cortex-M33 和 Cortex-M4F 指令集。芯片内核 支持一整套DSP指令用于数字信号处理&#xff0c;支持单精度FPU处理浮点数据&#xff0c;同时还支持Memory Protection Unit &#xff08;MPU&#xff09;用于提升应用的…
阅读更多...
【Kubernetes】kubeadm安装k8s1.25.0高可用集群

【Kubernetes】kubeadm安装k8s1.25.0高可用集群

k8s集群搭建&#xff08;v1.25.0&#xff09; 一、初始化实验环境二、安装containerd服务2.1、安装containerd2.2、安装docker2.3、配置镜像加速器三、安装初始化k8s需要的软件包四、kubeadm初始化k8s集群4.1、设置容器运行时4.2、生成并修改配置文件4.2、初始化安装4.3、修改c…
阅读更多...
最新文章

Copyright @ 2022~2023