• 【STL】用一棵红黑树封装map和set

    ⭐博客主页：️CS semi主页
    ⭐欢迎关注：点赞收藏+留言
    ⭐系列专栏：C++进阶
    ⭐代码仓库：C++进阶
    家人们更新不易，你们的点赞和关注对我而言十分重要，友友们麻烦多多点赞＋关注，你们的支持是我创作最大的动力，欢迎友友们私信提问，家人们不要忘记点赞收藏＋关注哦！！！

    用一棵红黑树封装map和set

    一、红黑树原码

    传送

    二、红黑树模板参数控制

    set是Key模型的容器，map是key-value模型的容器，而我们是需要用一种模板来进行实现set和map，所以，我们使用了key-value模型来进行模拟实现set和map，我们将第二个模版参数改成class T，这样能够以示区分原来的红黑树的模版。

    在这里插入图片描述

    这个T既可能是K值，也可能是key与value共同构成的键值对，我们看一下set容器的实现形式：
    在这里插入图片描述

    我们再来写一下map的实现形式：

    在这里插入图片描述

    三、红黑树结点当中存储的数据

    那我们红黑树中的结点也是需要进行一下更改的，我们看下图，MySet中第二个模板参数传到RBTree中是传的是Key，而MyMap中第二个模板参数传到RBTree中的是pair，这是kv的键值对，而RBTreeNode中接收的是第二个模板参数，我们以下列一下K和T不同的模板形式：

    set：K和T都代表着Key。
    map：K代表键值Key，T代表键值对pair。

    所以我们只需要使用第二个模板参数T就可以实现红黑树结点根据不同的容器进行模板实例化，但有同学要问了，为什么我们不能直接在set和map中只使用一个模版参数T呢？而偏偏要使用两个模板参数K和T？
    似乎是没什么问题的，对set来讲有没有这个第一个参数K都不影响的，而对于大部分的map情况中也是没有什么影响的，而具有最重大影响的是map的find和erase这两个接口函数，这两个接口函数是需要用到第一个参数K的，所以为了保持所有的接口都能用，只能委屈一下set，让set多一个模板参数K。

    在这里插入图片描述

    //红黑树结点的定义
template<class T>
struct RBTreeNode
{
	//构造函数
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}

	//三叉链
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//存储的数据
	T _data;

	//结点的颜色
	int _col; //红/黑
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    四、红黑树结点中仿函数

    一个很简单的现象，参数T：set的上层是K，直接能进行比较，而map上层是pair，而我们进行比较map的时候是很难进行pair比较的，因为比较不了，所以我们需要将pair中的K特地摘出来进行比较，那么这个比较就需要通过一个仿函数进行摘出来K进行比较键值对。

    仿函数：我们之前写过这种类似的仿函数模型，其实就是要实现一个operator()的功能，这个类就有了类似函数的行为，就是一个仿函数类了。

    Map：
    在这里插入图片描述

    我们Map写了以后，我们思考一下Set写不写？
    看似似乎并不用写这个Set，因为我们的Key能直接拿到，但是这只是我们人的视角下是肯定可以的，但是编译器能那么聪明吗？我们了解到，编译器是没有办法进行判断我们传过来的是Map还是Set，所以我们需要委屈一下Set，把Set的仿函数也书写一下：
    小故事：今天女朋友说要去逛街买包，你敢不去吗？也就是Set是一个陪逛街的身份，但它必须陪着Map逛街。
    在这里插入图片描述

    在这里插入图片描述

    这样我们根据上面的逻辑图看实例化，是在RBTree中加入一个仿函数，将Set和Map的仿函数比较过程进行传参并实例化，那我们下面用一个Find子函数进行解析一下：

    	// 红黑树的查找
	Node* Find(const K& key)
	{
		KeyOfT kot;
		Node* cur = _root;
		while (cur)
		{
			// 当前结点的值大于寻找的结点的值
			if (key < kot(cur->_data))
			{
				cur = cur->_left;
			}
			else if (key > kot(cur->_data))
			{
				cur = cur->_right;
			}
			else
			{
				// 找到了
				return cur;
			}
		}
		return nullptr;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    在这里插入图片描述

    五、正向迭代器

    红黑树的正向迭代器实际上就是对结点指针进行了封装，因此在正向迭代器当中实际上就只有一个成员变量，那就是正向迭代器所封装结点的指针。

    // 正向迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node; //结点类型
	typedef __TreeIterator<T, Ref, Ptr> Self; //正向迭代器类型

	Node* _node;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    我们在之前写过有关T，Ref和Ptr，所以我们先介绍一下，T就是我们的模版参数，Ref是解引用操作，Ptr是指针操作。

    1、框架+构造函数

    // 正向迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node; //结点类型
	typedef __TreeIterator<T, Ref, Ptr> Self; //正向迭代器类型
	// 构造函数
	__TreeIterator(Node* node)
		:_node(node)
	{}
	Node* _node;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    解释一下：T是第一个模版参数，定义类型的，Ref是解引用操作的模版参数，Ptr是指针指向的模版参数。

    2、Ref

    要对于一个结点解引用的操作，我们直接返回这个结点的值即可。

    	// 正向迭代器解引用操作
	Ref operator*()
	{
		return _node->_data;
	}

    • 1
    • 2
    • 3
    • 4
    • 5

    3、Ptr

    要对于一个结点进行->的操作的时候，我们直接返回这个结点数据的指针即可。

    	// 正向迭代器指向操作
	Ptr operator->()
	{
		return &_node->_data;
	}

    • 1
    • 2
    • 3
    • 4
    • 5

    4、重载operator==和operator!=

    直接使用Self类型进行判断这两个迭代器是否相同。

    	// 判断两个正向迭代器是否不同
	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	// 判断两个正向迭代器是否相同
	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    5、operator++ 【重点讲解】

    我们要实现这个operator++，我们首先需要了解这个红黑树的遍历打印是中序遍历打印，也就是先左子树，再根，再右子树，所以我们如下两种情况：

    （1）情况1：当前结点的右子树有结点

    找该节点的右子树的最左节点。

    在这里插入图片描述

    （2）情况2：当前结点的右子树为空

    ++操作后在该结点的祖先结点中，找到孩子不在父亲右的祖先。

    在这里插入图片描述

    （3）代码

    	// 正向迭代器++操作
	Self operator++()
	{
		// 结点的右子树不为空，找右子树的最左结点
		if (_node->_right != nullptr)
		{
			Node* R_left = _node->_right;
			while (R_left->_left != nullptr)
			{
				R_left = R_left->_left;
			}
			_node = R_left;
		}
		// 结点的右子树为空，找祖先结点不为右的结点
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent&& cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    6、operator–

    即遍历当前结点的前一个结点，与++正好相反。

    1、如果当前结点的左子树不为空，则–操作后应该找到其左子树当中的最右结点。
    2、如果当前结点的左子树为空，则–操作后应该在该结点的祖先结点中，找到孩子不在父亲左的祖先。

    （1）情况1：当前节点的左子树有节点

    –是找左子树的最右结点。
    在这里插入图片描述

    （2）情况2：当前结点的左子树没结点

    在这里插入图片描述

    （3）代码

    	// 正向迭代器--操作
	Self operator--()
	{
		// 结点的左子树不为空，找左子树中的最右节点
		if (_node->_left != nullptr)
		{
			Node* L_right = _node->_left;
			while (L_right->_right != nullptr)
			{
				L_right = L_right->_right;
			}
			_node = L_right;
		}
		// 节点的左子树为空，找祖先结点中，找到孩子不在父亲左的祖先
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    7、正向迭代器在RBTree中的实现

    正向迭代器分为begin()和end()，所以我们分析一下begin()和end()：

    我们要将iterator放到public当中，让外部可以拿到。

    （1）begin()

    begin()就是我们前面所提的红黑树的第一个位置，而第一个位置则是整颗红黑树，begin函数返回中序序列当中第一个结点的正向迭代器，即最左结点。

    	typedef __TreeIterator<T, T&, T*> iterator;
	// 最左节点
	iterator begin()
	{
		Node* left = _root;
		while (left && left->_left != nullptr)
		{
			left = left->_left;
		}
		// 返回最左结点的迭代器
		return iterator(left);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    （2）end()

    end()就是我们前面所提到的红黑树的最末尾的位置的下一个位置，那么就是nullptr！

    	typedef __TreeIterator<T, T*, T&> iterator;
	// end()是整个树的最末尾结点的后一个位置
	iterator end()
	{
		return iterator(nullptr);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    （3）代码

    template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;

public:
	typedef __TreeIterator<T, T*, T&> iterator;

	// 最左节点
	iterator begin()
	{
		Node* left = _root;
		while (left && left->_left != nullptr)
		{
			left = left->_left;
		}
		// 返回最左结点的迭代器
		return iterator(left);
	}

	// end()是整个树的最末尾结点的后一个位置
	iterator end()
	{
		return iterator(nullptr);
	}
private:
	Node* _root;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    8、缺陷和改进

    我们大家不知道发现了没有，上述所写的end()是指向的最后一个结点的下一个位置，即nullptr，但我们的C++SGI版本中不是这样写的，其end()是指向最后一个元素的，所以我们来看一下SGI版本下的end()封装是怎么封装的：

    在这里插入图片描述

    我们看，在这个版本中，多了个header结点刚刚好是13根节点的父节点，这个header结点的左边指向这棵红黑树的最左节点象征着begin()，这个header结点的右边指向这棵红黑树的最右结点象征着rbegin()。实现end()和rend()时，直接用头结点构造出正向和反向迭代器即可。此后，通过对逻辑的控制，就可以实现end()进行–操作后得到最后一个结点的正向迭代器。

    六、反向迭代器

    1、反向迭代器的实现

    反向迭代器我们根本都不需要一步一步写下来了，我们只需要用正向迭代器进行封装反向迭代器即可，如下代码：

    在这里插入图片描述

    //反向迭代器 -- 根据正向迭代器封装
template<class Iterator>
struct ReverseIterator
{
	typedef ReverseIterator<Iterator> Self; //反向迭代器的类型

	// 这里为了能够让反向迭代器能够拿到正向迭代器的解引用和指针
	typedef typename Iterator::reference Ref; //结点指针的解引用*
	typedef typename Iterator::pointer Ptr; //结点指针->

	//构造函数
	ReverseIterator(Iterator rit)
		:_rit(rit)
	{}

	// 和正向迭代器一样
	Ref operator*()
	{
		return *_rit;
	}

	// 和正向迭代器一样
	Ptr operator->()
	{
		return _rit.operator->(); 
	}

	  // ++操作就是正向迭代器的--操作
	Self& operator++()
	{
		--_rit;
		return *this;
	}

	// --操作就是正向迭代器的++操作
	Self& operator--()
	{
		++_rit;
		return *this;
	}

	// 不等号一样
	bool operator!=(const Self& s) const
	{
		return _rit != s._rit;
	}

	// 等号也一样
	bool operator==(const Self& s) const
	{
		return _rit == s._rit;
	}
	
	Iterator _rit;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    2、RBTree中使用反向迭代器

    template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;

public:
	typedef __TreeIterator<T, T*, T&> iterator;
	typedef ReverseIterator<iterator> reverse_iterator;

	// 最左节点
	iterator begin()
	{
		Node* left = _root;
		while (left && left->_left != nullptr)
		{
			left = left->_left;
		}
		// 返回最左结点的迭代器
		return iterator(left);
	}

	// end()是整个树的最末尾结点的后一个位置
	iterator end()
	{
		return iterator(nullptr);
	}

	// 最右结点
	reverse_iterator rbegin()
	{
		Node* right = _root;
		while (right && right->_left != nullptr)
		{
			right = right->_right;
		}
		// 返回最右结点的迭代器
		return reverse_iterator(iterator(right));
	}

	// end()是整个树的最末尾结点的后一个位置
	reverse_iterator rend()
	{
		return reverse_iterator(iterator(nullptr));
	}
private:
	Node* _root;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    七、代码汇总

    Set.h:

    #include"MyRBTree.h"

namespace JRH
{
	template<class K, class T>
	class MySet
	{
		// 仿函数
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; //正向迭代器
		typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器

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

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

		// rbegin()
		reverse_iterator rbegin()
		{
			return _t.rbegin();
		}

		// rend()
		reverse_iterator rend()
		{
			return _t.rend();
		}

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

		// 删除
		void erase(const K& key)
		{
			return _t.Erase(key);
		}

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

	private:
		RBTree<K, K, SetKeyOfT> _t;
	};
}




    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    map.h

    #include"MyRBTree.h"

namespace JRH
{
	template<class K, class V>
	class MyMap

	{	//仿函数
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv) //返回键值对当中的键值Key
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; //正向迭代器
		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器

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

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

		// rbegin()
		reverse_iterator rbegin()
		{
			return _t.rbegin();
		}

		// rend()
		reverse_iterator rend()
		{
			return _t.rend();
		}

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

		// 删除
		void erase(const K& key)
		{
			return _t.Erase(key);
		}

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

		//[]运算符重载函数
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			iterator it = ret.first;
			return it->second;
		}

	private:
		RBTree<K, pair<K, V>, MapKeyOfT> _t;
	};
}




    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76

    正向和反向迭代器：

    // 正向迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node; //结点类型
	typedef __TreeIterator<T, Ref, Ptr> Self; //正向迭代器类型

	// 为了让下面反向迭代器拿到
	typedef typename Ref reference;
	typedef typename Ptr pointer;
	// 构造函数
	__TreeIterator(Node* node)
		:_node(node)
	{}

	// 正向迭代器解引用操作
	Ref operator*()
	{
		return _node->_data;
	}

	// 正向迭代器指向操作
	Ptr operator->()
	{
		return &_node->_data;
	}

	// 判断两个正向迭代器是否不同
	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	// 判断两个正向迭代器是否相同
	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}

	// 正向迭代器++操作
	Self operator++()
	{
		// 结点的右子树不为空，找右子树的最左结点
		if (_node->_right != nullptr)
		{
			Node* R_left = _node->_right;
			while (R_left->_left != nullptr)
			{
				R_left = R_left->_left;
			}
			_node = R_left;
		}
		// 结点的右子树为空，找祖先结点不为右的结点
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent&& cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	// 正向迭代器--操作
	Self operator--()
	{
		// 结点的左子树不为空，找左子树中的最右节点
		if (_node->_left != nullptr)
		{
			Node* L_right = _node->_left;
			while (L_right->_right != nullptr)
			{
				L_right = L_right->_right;
			}
			_node = L_right;
		}
		// 节点的左子树为空，找祖先结点中，找到孩子不在父亲左的祖先
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Node* _node;
};


//反向迭代器 -- 根据正向迭代器封装
template<class Iterator>
struct ReverseIterator
{
	typedef ReverseIterator<Iterator> Self; //反向迭代器的类型

	// 这里为了能够让反向迭代器能够拿到正向迭代器的解引用和指针
	typedef typename Iterator::reference Ref; //结点指针的解引用*
	typedef typename Iterator::pointer Ptr; //结点指针->

	//构造函数
	ReverseIterator(Iterator rit)
		:_rit(rit)
	{}

	// 和正向迭代器一样
	Ref operator*()
	{
		return *_rit;
	}

	// 和正向迭代器一样
	Ptr operator->()
	{
		return _rit.operator->(); 
	}

	  // ++操作就是正向迭代器的--操作
	Self& operator++()
	{
		--_rit;
		return *this;
	}

	// --操作就是正向迭代器的++操作
	Self& operator--()
	{
		++_rit;
		return *this;
	}

	// 不等号一样
	bool operator!=(const Self& s) const
	{
		return _rit != s._rit;
	}

	// 等号也一样
	bool operator==(const Self& s) const
	{
		return _rit == s._rit;
	}
	
	Iterator _rit;
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155

    RBtree改装：

    #include

#include
using namespace std;

enum Col
{
	BLACK,
	RED
};

//红黑树结点的定义
template<class T>
struct RBTreeNode
{
	//构造函数
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}

	//三叉链
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//存储的数据
	T _data;

	//结点的颜色
	int _col; //红/黑
};



template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;

public:
	typedef __TreeIterator<T, T&,T*> iterator;
	typedef ReverseIterator<iterator> reverse_iterator;

	// 构造函数
	RBTree()
		:_root(nullptr)
	{}

	//赋值运算符重载
	RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
	{
		swap(_root, t._root);
		return *this;
	}

	//析构函数
	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

	// 最左节点
	iterator begin()
	{
		Node* left = _root;
		while (left && left->_left != nullptr)
		{
			left = left->_left;
		}
		// 返回最左结点的迭代器
		return iterator(left);
	}

	// end()是整个树的最末尾结点的后一个位置
	iterator end()
	{
		return iterator(nullptr);
	}

	// 最右结点
	reverse_iterator rbegin()
	{
		Node* right = _root;
		while (right && right->_left != nullptr)
		{
			right = right->_right;
		}
		// 返回最右结点的迭代器
		return reverse_iterator(iterator(right));
	}

	// end()是整个树的最末尾结点的后一个位置
	reverse_iterator rend()
	{
		return reverse_iterator(iterator(nullptr));
	}

	// 红黑树的查找
	Node* Find(const K& key)
	{
		KeyOfT kot;
		Node* cur = _root;
		while (cur)
		{
			// 当前结点的值大于寻找的结点的值
			if (key < kot(cur->_data))
			{
				cur = cur->_left;
			}
			else if (key > kot(cur->_data))
			{
				cur = cur->_right;
			}
			else
			{
				// 找到了
				return cur;
			}
		}
		return nullptr;
	}

	// 插入
	pair<iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;

		// 一棵空树
		if (_root == nullptr)
		{
			// 创建新结点 + 颜色初始化为黑色
			_root = new Node(data);
			_root->_col = BLACK; // 根节点得是黑的
			return make_pair(iterator(_root), true);
		}

		// 先找到 -- 利用二叉搜索树的方法进行查找
		Node* cur = _root;
		Node* parent = nullptr;
		// 左小右大
		while (cur)
		{
			// 当前结点值大于待插入结点值，往左子树走
			if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			// 当前结点值小于待插入结点值，往右子树走
			else if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			// 待插入结点的值和当前结点的值相等，插入失败
			else
			{
				return make_pair(iterator(cur), false);
			}
		}

		// 将当前结点的值插入进去
		cur = new Node(data); // new一个新的结点
		cur->_col = RED;
		Node* newnode = cur; // 记录新插入的结点
		// 新插入的节点值小于父节点的节点值，插入到parent的左边
		if (kot(data) < kot(parent->_data))
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		// 新插入的节点值小于父节点的节点值，插入到parent的左边
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		// 新插入结点的父节点是红色的，需要做出调整
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent; // parent是红色，则其父结点一定存在
			// 以grandparent左右孩子为分界线，分成if和else
			if (parent == grandfather->_left) // 左孩子
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)// 情况一：uncle存在且为红色
				{
					// 颜色调整
					grandfather->_col = RED;
					uncle->_col = parent->_col = BLACK;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else// 情况二：uncle存在且为黑色 / 情况三：uncle不存在
				{
					// 用左右孩子分为两半，一半是if用来表示在左孩子，一半是else用来表示在右孩子
					if (cur == parent->_left)
					{
						//   g
						//  p
						// c
						// 右单旋
						RoateR(grandfather);

						// 颜色调整
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//    g
						//  p
						//      c
						// 左右双旋
						RoateLR(grandfather);

						// 颜色调整
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else // 右孩子
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)// 情况一：uncle存在且为红色
				{
					// 颜色调整
					grandfather->_col = RED;
					uncle->_col = parent->_col = BLACK;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else// 情况二：uncle存在且为黑色 / 情况三：uncle不存在
				{
					// 用左右孩子分为两半，一半是if用来表示在左孩子，一半是else用来表示在右孩子
					if (cur == parent->_right)
					{
						//   g
						//     p
						//      c
						// 左单旋
						RoateL(grandfather);

						// 颜色调整
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//    g
						//      p
						//    c
						// 右左双旋
						RoateRL(grandfather);

						// 颜色调整
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}

	// 左单旋
	void RoateL(Node* parent)
	{
		// 三叉链
		Node* subr = parent->_right;
		Node* subrl = subr->_left;
		Node* ppnode = parent->_parent;

		// subrl与parent的关系
		parent->_right = subrl;
		if (subrl)
			subrl->_parent = parent;

		// subl和parent的关系
		subr->_left = parent;
		parent->_parent = subr;

		// ppnode和subr的关系
		if (ppnode == nullptr)
		{
			_root = subr;
			subr->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subr;
			}
			else
			{
				ppnode->_right = subr;
			}
			subr->_parent = ppnode;
		}
	}

	// 右单旋
	void RoateR(Node* parent)
	{
		// 三叉链
		Node* subl = parent->_left;
		Node* sublr = subl->_right;
		Node* ppnode = parent->_parent;


		//sublr和parent之间的关系
		parent->_left = sublr;
		if (sublr)
			sublr->_parent = parent;

		//subl和parent的关系
		subl->_right = parent;
		parent->_parent = subl;


		//ppnode 和 subl的关系
		if (ppnode == nullptr)
		{
			_root = subl;
			subl->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subl;
			}
			else
			{
				ppnode->_right = subl;
			}
			subl->_parent = ppnode;
		}
	}

	// 左右双旋
	void RoateLR(Node* parent)
	{
		RoateL(parent->_left);
		RoateR(parent);
	}

	// 右左双旋
	void RoateRL(Node* parent)
	{
		RoateR(parent->_right);
		RoateL(parent);
	}


private:
	//析构函数子函数
	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}

	Node* _root;
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
  • 相关阅读:
    Vue3 echarts v-show无法重新渲染的问题
    网关gateway - 自定义实现动态路由信息存储记载
    项目管理PMP好考吗，没有经验？
    rabbitMQ学习笔记
    LeetCode 891. 子序列宽度之和
    mac安装nvm
    copy模块的copy()和deepcopy()
    RoHS认证测试的3种方法，RoHS测试，RoHS检测，RoHS认证是什么
    NAND Flash原理
    qt mingw 生成DUMP文件，和pdb文件
  • 原文地址：https://blog.csdn.net/m0_70088010/article/details/133436373