• C++之＜set和map模拟实现＞

    目录

    🌈前言

    本篇文章进行STL中map和set的补充！！！

    🌅set和map模拟实现

    注意：模拟实现，需要掌握【map和set的原理】和【RBTree的实现】

    🌷1、红黑树的迭代器

    迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以前问题：

    • begin()和end()

    1. STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()为红黑树中最小节点(即最左侧节点)的位置

    2. end()在最大节点(最右侧节点)的下一个位置，只需要让end()为空就行了，简化操作

    3. 注意：库中实现begin和end是使用带头节点来进行控制左闭右开的，头节点的左节点指向begin()，右节点指向end()，这样的操作更复杂

    库实现的方式：
    在这里插入图片描述

    • operator++ 和 operator–
    1. 因为红黑树是中序遍历的，使用operator++需要遵循（左-根-右）进行自增，两种情况：

    • 根的右子树不为空时，说明右子树没找完，继续找根右子树的最左节点

    • 根的右子树为空时，说明可能已经找完一个子树或局部子树，向上找祖先的左节点

    // 注意：self为迭代器的类型重命名，pNode为指向RBTree节点的指针
self& operator++()
	{
		// 右子树不为空，需要一直往上找，因为中序是左 根 右，右完了那么左节点和中间的根节点也遍历完了，控制cur和它的父节点
		if (pNode->right == nullptr)
		{
			Node* cur = pNode;
			Node* parent = cur->parent;

			while (parent != nullptr && cur == parent->right)
			{
				cur = cur->parent;
				parent = parent->parent;
			}
			pNode = parent;
		}
		else // 右子树为空，则继续找这个节点的右子树的最左节点
		{
			Node* subLeft = pNode->right;

			while (subLeft->left)
			{
				subLeft = subLeft->left;
			}
			pNode = subLeft;
		}
		return *this;
	}

	self operator++(int)
	{
		self tmp(*this);
		++(*this);

		return tmp;
	}

    • 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

    在这里插入图片描述

    1. 因为红黑树是中序遍历的，使用operator–也需要遵循（左-根-右）进行自减，两种情况：

    • 根的左子树不为空时，说明左子树没找完，继续找根左子树的最右节点

    • 根的左子树为空时，说明可能已经找完一个子树或局部子树，向上找祖先的右节点

    注意：operator–和operator++的操作是相反的，可以认为是右 根 左这样走的，右完了到根最后到左

    // 注意：self为迭代器的类型重命名，pNode为指向RBTree节点的指针
self& operator--()
	{
		// ++反过来走就是--
		if (pNode->left == nullptr)
		{
			Node* cur = pNode;
			Node* parent = cur->parent;

			while (parent != nullptr && cur == parent->left)
			{
				cur = cur->parent;
				parent = parent->parent;
			}
			pNode = parent;
		}
		else
		{
			Node* subRight = pNode->left;

			while (subRight->right)
			{
				subRight = subRight->right;
			}
			pNode = subRight;
		}
		return *this;
	}

	self operator--(int)
	{
		self tmp(*this);
		--(*this);

		return tmp;
	}

    • 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

    在这里插入图片描述

    完整迭代器代码：

    // RBTreeNode<...>是红黑树的节点类

template <typename T, typename Sef, typename Ptr>
struct RBTree_Iterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTree_Iterator<T, Sef, Ptr> self;

	RBTree_Iterator(Node* _pNode)
		: pNode(_pNode)
	{}

	RBTree_Iterator(const self& s)
		: pNode(s.pNode)
	{}

	Sef operator*() { return pNode->data; }
	Ptr operator->() { return &(pNode->data); }

	self& operator++()
	{
		// 右子树不为空，需要一直往上找，因为中序是左 根 右，右完了那么左节点和中间的根节点也遍历完了，控制cur和它的父节点
		if (pNode->right == nullptr)
		{
			Node* cur = pNode;
			Node* parent = cur->parent;

			while (parent != nullptr && cur == parent->right)
			{
				cur = cur->parent;
				parent = parent->parent;
			}
			pNode = parent;
		}
		else // 右子树为空，则走这个节点的右子树的最左节点
		{
			Node* subLeft = pNode->right;

			while (subLeft->left)
			{
				subLeft = subLeft->left;
			}
			pNode = subLeft;
		}
		return *this;
	}

	self operator++(int)
	{
		self tmp(*this);
		++(*this);

		return tmp;
	}

	self& operator--()
	{
		// ++反过来走就是--
		if (pNode->left == nullptr)
		{
			Node* cur = pNode;
			Node* parent = cur->parent;

			while (parent != nullptr && cur == parent->left)
			{
				cur = cur->parent;
				parent = parent->parent;
			}
			pNode = parent;
		}
		else
		{
			Node* subRight = pNode->left;

			while (subRight->right)
			{
				subRight = subRight->right;
			}
			pNode = subRight;
		}
		return *this;
	}

	self operator--(int)
	{
		self tmp(*this);
		--(*this);

		return tmp;
	}

	bool operator==(const self& s) { return pNode == s.pNode; }
	bool operator!=(const self& s) { return pNode != s.pNode; }
public:
	Node* pNode;
};

    • 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

    🌷2、改造红黑树

    前言：set和map的实现是需要共用红黑树的，我们不可能set和map实现都各写一份

    【RBTree的实现】

    我们开始对RBTree进行改造：

    • 首先set的底层值是(key, key)类型的，而map是(key, value) 键值对
    1. 我们需要将红黑树节点类的模板参数改成一个，因为我们无法区分节点值的类型是key还是键值对
    enum Color
{
	RED,
	BLACK
};

// T -- 泛化的类型，可能为key也可能为pair< , >
template <typename 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;
	Color 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
    1. 我们需要将红黑树的模板参数增加一个compare，用于控制值比较，并且值比较的地 方也要跟着改，如果不增加这个，编译器将无法进行值比较
    // 注意KeyOfT是通过set或map里面封装一个仿函数类传过来的
template <typename K, typename T, class KeyOfT>
class RBTree
{
private:
	Node* root;
	KeyOfT kot; // 控制比较时的类型，里面重载了仿函数
public:
	bool insert(const T& data)
	{
		if (root == nullptr)
		{
			root = new Node(data);
			root->col = BLACK;
			return true;
		}

		// 按搜索树规则插入
		Node* cur = root;
		Node* parent = nullptr;

		while (cur != nullptr)
		{
			// 这里的值比较全部都要进行更改，否则无法进行比较
			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 false;
		}

		cur = new Node(data);
		// 如果插入节点是红色，可能破坏规则2  ---  如果插入节点是黑色，一定会破坏规则3（3很难处理）
		cur->col = RED;
		if (kot(parent->data) > kot(data)) {
			parent->left = cur;
		}
		else {
			parent->right = cur;
		}
		cur->parent = parent;


		// 存在连续红色节点时，需要一直向上调整
		while (parent != nullptr && parent->col == RED) // 因为插入节点是红色，如果parent也是红色（连续红节点），那么需要调整
		{
			Node* grandfather = parent->parent; // cur的祖父

			// 找叔叔时需要判断在祖父的哪一边
			if (grandfather->left == parent)
			{
				Node* uncle = grandfather->right;

				// 情况一：grandfather为黑，parent为红，uncle为红，cur为红 -- 需要调整g，p，u的颜色
				if (uncle && uncle->col == RED)
				{
					parent->col = BLACK;
					uncle->col = BLACK;
					grandfather->col = RED;

					// 调整的这颗树可能为局部子树，需要继续向上处理，祖父的父亲可能为红节点, 更新cur,parent
					cur = grandfather;
					parent = cur->parent;
				}
				// 情况二：grandfather为黑，parent为红，uncle为nullptr/黑，cur为红 -- 需要旋转+变色处理
				else
				{
					// 右旋，插入节点为parent的左边，祖父为旋转点，parent为祖父的左边，uncle为祖父的右边
					if (cur == parent->left)
					{
						//     g
						//   p
						// c
						RotateR(grandfather);
						// 更新颜色 -- 旋转后parent为根，根要变黑（根变黑后所有子树的路径的黑节点数量都加1） -- grandfather为根的子树，变红
						parent->col = BLACK;
						grandfather->col = RED;
					}
					else // 第三种情况，左右双旋，cur插入parent的右边，且parent为g的左边，，形成折线
					{
						//    g
						// p
						//    c
						RotateL(parent);
						RotateR(grandfather);

						// 更新颜色
						grandfather->col = RED;
						cur->col = BLACK;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->left;

				if (uncle != nullptr && uncle->col == RED)
				{
					parent->col = BLACK;
					uncle->col = BLACK;
					grandfather->col = RED;

					cur = grandfather;
					parent = cur->parent;
				}
				else
				{
					// 左旋，插入节点为parent的右边，祖父为旋转点，parent为祖父的右边，uncle为祖父的左边
					// g
					//    p
					//      c
					if (cur == parent->right)
					{
						RotateL(grandfather);
						// 更新颜色
						parent->col = BLACK;
						grandfather->col = RED;
					}
					else // 右左双旋，cur插入parent的左边，且parent为g的右边，形成折线
					{
						// g
						//    p
						// c
						RotateR(parent);
						RotateL(grandfather);

						// 更新颜色
						grandfather->col = RED;
						cur->col = BLACK;
					}
					break;
				}
			}
		}
		root->col = BLACK; // 调整完后，根节点可能是红，需要调整为黑
		return true;
	}
}

    • 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

    注意：除了inset和erase，后续的find也要跟着改

    1. 根据map的特性，封装红黑树时，inset的返回值类型应该是键值对（pair），这里关乎于operator[]的实现问题，也要进行更改…
    pair<iterator, bool> insert(const T& data)
	{
		if (root == nullptr)
		{
			root = new Node(data);
			root->col = BLACK; // 根节点始终为黑色
			return make_pair(iterator(root), true); // 插入成功，返回一个键对值
		}

		// 按搜索树规则插入
		Node* cur = root;
		Node* newNode = cur; // 插入后，需要调整颜色，可能改变cur的位置，需要保存
		Node* parent = nullptr;

		while (cur != nullptr)
		{
			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(root), false); // 插入失败，返回插入位置的迭代器的pair
			}
		}

		cur = new Node(data);
		// 如果插入节点是红色，可能破坏规则2  ---  如果插入节点是黑色，一定会破坏规则3（3很难处理）
		cur->col = RED;
		if (kot(parent->data) > kot(data)) {
			parent->left = cur;
		}
		else {
			parent->right = cur;
		}
		cur->parent = parent;


		// 存在连续红色节点时，需要一直向上调整
		while (parent != nullptr && parent->col == RED) // 因为插入节点是红色，如果parent也是红色（连续红节点），那么需要调整
		{
			Node* grandfather = parent->parent; // cur的祖父

			// 找叔叔时需要判断在祖父的哪一边
			if (grandfather->left == parent)
			{
				Node* uncle = grandfather->right;

				// 情况一：grandfather为黑，parent为红，uncle为红，cur为红 -- 需要调整g，p，u的颜色
				if (uncle && uncle->col == RED)
				{
					parent->col = BLACK;
					uncle->col = BLACK;
					grandfather->col = RED;

					// 调整的这颗树可能为局部子树，需要继续向上处理，祖父的父亲可能为红节点, 更新cur,parent
					cur = grandfather;
					parent = cur->parent;
				}
				// 情况二：grandfather为黑，parent为红，uncle为nullptr/黑，cur为红 -- 需要旋转+变色处理
				else
				{
					// 右旋，插入节点为parent的左边，祖父为旋转点，parent为祖父的左边，uncle为祖父的右边
					if (cur == parent->left)
					{
						//     g
						//   p
						// c
						RotateR(grandfather);
						// 更新颜色 -- 旋转后parent为根，根要变黑（根变黑后所有子树的路径的黑节点数量都加1） -- grandfather为根的子树，变红
						parent->col = BLACK;
						grandfather->col = RED;
					}
					else // 第三种情况，左右双旋，cur插入parent的右边，且parent为g的左边，，形成折线
					{
						//    g
						// p
						//    c
						RotateL(parent);
						RotateR(grandfather);

						// 更新颜色
						grandfather->col = RED;
						cur->col = BLACK;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->left;

				if (uncle != nullptr && uncle->col == RED)
				{
					parent->col = BLACK;
					uncle->col = BLACK;
					grandfather->col = RED;

					cur = grandfather;
					parent = cur->parent;
				}
				else
				{
					// 左旋，插入节点为parent的右边，祖父为旋转点，parent为祖父的右边，uncle为祖父的左边
					// g
					//    p
					//      c
					if (cur == parent->right)
					{
						RotateL(grandfather);
						// 更新颜色
						parent->col = BLACK;
						grandfather->col = RED;
					}
					else // 右左双旋，cur插入parent的左边，且parent为g的右边，形成折线
					{
						// g
						//    p
						// c
						RotateR(parent);
						RotateL(grandfather);

						// 更新颜色
						grandfather->col = RED;
						cur->col = BLACK;
					}
					break;
				}
			}
		}
		root->col = BLACK; // 调整完后，根节点可能是红，需要调整为黑
		return make_pair(iterator(root), true);
	}

    • 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

    注意：插入新的节点后，需要保存一份新节点的地址，否则后面旋转调整会改变，就找不到原来的地址了，inset的返回值需要返回原插入位置的迭代器

    🌸3、set的模拟实现

    • set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来：
    #include "RBTree.h"

namespace MySet
{
	template <typename K>
	class set
	{
	public:
		// 仿函数，用于模板类型传参，控制RBtree中key数据的比较类型
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		// 迭代器
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
	public:
		iterator begin() const
		{
			return rb.begin();
		}

		iterator end() const
		{
			return rb.end();
		}
	public:
		pair<iterator, bool> insert(const K& key)
		{
			pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = rb.insert(key);
			return pair<iterator, bool>(iterator(ret.first.pNode) , ret.second);
		}

		iterator find(const K& key)
		{
			return rb.find(key);
		}
	private:
		// set对应红黑树的参数类型为set
		RBTree<K, K, SetKeyOfT> rb;
	};
}

    • 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

    🌸4、map的模拟实现

    • map的底层结构就是红黑树，因此在map中直接封装一棵红黑树，然后将其接口包装下即可:
    #include "RBTree.h"

namespace MyMap
{
	template <typename K, typename V>
	class map
	{
	public:
		// 仿函数，用于模板类型传参，控制RBtree中key数据的比较类型
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, const pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
	public:
		iterator begin()
		{
			return rb.begin();
		}
		iterator end()
		{
			return rb.end();
		}
	public:
		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return rb.insert(kv);
		}
		iterator find(const K& key)
		{
			return rb.find(key);
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = rb.insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		// map对应红黑树的参数类型为map>
		RBTree<K, pair<K, V>, MapKeyOfT> rb;
	};
}


    • 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

    🌳5、完整改造红黑树的代码

    #pragma once

#include 
using namespace std;

enum Color
{
	RED,
	BLACK
};

// T -- 泛化的类型，可能为key也可能为pair< , >
template <typename 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;
	Color col;
};

template <typename T, typename Sef, typename Ptr>
struct RBTree_Iterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTree_Iterator<T, Sef, Ptr> self;

	RBTree_Iterator(Node* _pNode)
		: pNode(_pNode)
	{}

	RBTree_Iterator(const self& s)
		: pNode(s.pNode)
	{}

	Sef operator*() { return pNode->data; }
	Ptr operator->() { return &(pNode->data); }

	self& operator++()
	{
		// 右子树不为空，需要一直往上找，因为中序是左 根 右，右完了那么左节点和中间的根节点也遍历完了，控制cur和它的父节点
		if (pNode->right == nullptr)
		{
			Node* cur = pNode;
			Node* parent = cur->parent;

			while (parent != nullptr && cur == parent->right)
			{
				cur = cur->parent;
				parent = parent->parent;
			}
			pNode = parent;
		}
		else // 右子树为空，则走这个节点的右子树的最左节点
		{
			Node* subLeft = pNode->right;

			while (subLeft->left)
			{
				subLeft = subLeft->left;
			}
			pNode = subLeft;
		}
		return *this;
	}

	self operator++(int)
	{
		self tmp(*this);
		++(*this);

		return tmp;
	}

	self& operator--()
	{
		// ++反过来走就是--
		if (pNode->left == nullptr)
		{
			Node* cur = pNode;
			Node* parent = cur->parent;

			while (parent != nullptr && cur == parent->left)
			{
				cur = cur->parent;
				parent = parent->parent;
			}
			pNode = parent;
		}
		else
		{
			Node* subRight = pNode->left;

			while (subRight->right)
			{
				subRight = subRight->right;
			}
			pNode = subRight;
		}
		return *this;
	}

	self operator--(int)
	{
		self tmp(*this);
		--(*this);

		return tmp;
	}

	bool operator==(const self& s) { return pNode == s.pNode; }
	bool operator!=(const self& s) { return pNode != s.pNode; }
public:
	Node* pNode;
};

// 红黑树的规则：1.根节点是黑色的，黑节点的左右孩子可能为红也可能为黑
//			   2.如果一个节点为红色，则它的左右孩子节点为黑色（没有连续的红节点）
//			   3.对于每个节点，从该节点到其所有后代叶节点的路径上，均包含相同的数目的黑色节点（每条路径包含相同数目的黑色节点）
//			   4.叶节点(nullptr)是黑色的

// KeyOfT -- 取出红黑树节点中对应的key这个值
template <typename K, typename T, class KeyOfT>
class RBTree
{
private:
	typedef RBTreeNode<T> Node;
public:
	// 正向迭代器
	typedef RBTree_Iterator<T, T&, T*> iterator;
	typedef RBTree_Iterator<T, const T&, const T*> const_iterator;

	iterator begin() // 找左子树中最左的节点就是begin
	{ 
		Node* cur = root;

		while (cur->left)
		{
			cur = cur->left;
		}
		return iterator(cur);
	}
	iterator end() { return iterator(nullptr); }
	const_iterator begin() const
	{
		Node* cur = root;

		while (cur->left)
		{
			cur = cur->left;
		}
		return const_iterator(cur);
	}

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

	iterator find(const K& key)
	{
		Node* cur = root;
		while (cur)
		{
			if (kot(cur->data) > key)
				cur = cur->left;
			else if (kot(cur->data) < key)
				cur = cur->right;
			else
				return iterator(cur);
		}
		return iterator(end());
	}
public:
	RBTree()
		: root(nullptr)
	{}

	RBTree(const RBTree& rb)
		: root(nullptr)
	{
		root = Building_Tree(rb.root);
	}

	RBTree& operator=(const RBTree& rb)
	{
		Destory(root);
		root = Building_Tree(rb.root);
		return *this;
	}

	~RBTree()
	{
		Destory(root);
	}

	pair<iterator, bool> insert(const T& data)
	{
		if (root == nullptr)
		{
			root = new Node(data);
			root->col = BLACK; // 根节点始终为黑色
			return make_pair(iterator(root), true); // 插入成功，返回一个键对值
		}

		// 按搜索树规则插入
		Node* cur = root;
		Node* newNode = cur; // 插入后，需要调整颜色，可能改变cur的位置，需要保存
		Node* parent = nullptr;

		while (cur != nullptr)
		{
			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(root), false); // 插入失败，返回插入位置的迭代器的pair
			}
		}

		cur = new Node(data);
		// 如果插入节点是红色，可能破坏规则2  ---  如果插入节点是黑色，一定会破坏规则3（3很难处理）
		cur->col = RED;
		if (kot(parent->data) > kot(data)) {
			parent->left = cur;
		}
		else {
			parent->right = cur;
		}
		cur->parent = parent;


		// 存在连续红色节点时，需要一直向上调整
		while (parent != nullptr && parent->col == RED) // 因为插入节点是红色，如果parent也是红色（连续红节点），那么需要调整
		{
			Node* grandfather = parent->parent; // cur的祖父

			// 找叔叔时需要判断在祖父的哪一边
			if (grandfather->left == parent)
			{
				Node* uncle = grandfather->right;

				// 情况一：grandfather为黑，parent为红，uncle为红，cur为红 -- 需要调整g，p，u的颜色
				if (uncle && uncle->col == RED)
				{
					parent->col = BLACK;
					uncle->col = BLACK;
					grandfather->col = RED;

					// 调整的这颗树可能为局部子树，需要继续向上处理，祖父的父亲可能为红节点, 更新cur,parent
					cur = grandfather;
					parent = cur->parent;
				}
				// 情况二：grandfather为黑，parent为红，uncle为nullptr/黑，cur为红 -- 需要旋转+变色处理
				else
				{
					// 右旋，插入节点为parent的左边，祖父为旋转点，parent为祖父的左边，uncle为祖父的右边
					if (cur == parent->left)
					{
						//     g
						//   p
						// c
						RotateR(grandfather);
						// 更新颜色 -- 旋转后parent为根，根要变黑（根变黑后所有子树的路径的黑节点数量都加1） -- grandfather为根的子树，变红
						parent->col = BLACK;
						grandfather->col = RED;
					}
					else // 第三种情况，左右双旋，cur插入parent的右边，且parent为g的左边，，形成折线
					{
						//    g
						// p
						//    c
						RotateL(parent);
						RotateR(grandfather);

						// 更新颜色
						grandfather->col = RED;
						cur->col = BLACK;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->left;

				if (uncle != nullptr && uncle->col == RED)
				{
					parent->col = BLACK;
					uncle->col = BLACK;
					grandfather->col = RED;

					cur = grandfather;
					parent = cur->parent;
				}
				else
				{
					// 左旋，插入节点为parent的右边，祖父为旋转点，parent为祖父的右边，uncle为祖父的左边
					// g
					//    p
					//      c
					if (cur == parent->right)
					{
						RotateL(grandfather);
						// 更新颜色
						parent->col = BLACK;
						grandfather->col = RED;
					}
					else // 右左双旋，cur插入parent的左边，且parent为g的右边，形成折线
					{
						// g
						//    p
						// c
						RotateR(parent);
						RotateL(grandfather);

						// 更新颜色
						grandfather->col = RED;
						cur->col = BLACK;
					}
					break;
				}
			}
		}
		root->col = BLACK; // 调整完后，根节点可能是红，需要调整为黑
		return make_pair(iterator(root), true);
	}
private:
	// 左旋，右边高，左边矮
	void RotateL(Node* parent)
	{
		Node* subR = parent->right;
		Node* subRL = subR->left;

		parent->right = subRL;
		if (subRL != nullptr)
			subRL->parent = parent;

		Node* PpNode = parent->parent;

		subR->left = parent;
		parent->parent = subR;

		if (parent == root)
		{
			root = subR;
			root->parent = nullptr;
		}
		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 != nullptr)
			subLR->parent = parent;

		Node* PpNode = parent->parent;

		subL->right = parent;
		parent->parent = subL;

		if (parent == root)
		{
			root = subL;
			root->parent = nullptr;
		}
		else
		{
			if (PpNode->left == parent) {
				PpNode->left = subL;
			}
			else {
				PpNode->right = subL;
			}
			subL->parent = PpNode;
		}
	}

	Node* Building_Tree(Node* _root)
	{
		if (_root == nullptr)
			return nullptr;

		Node* newTree = new Node(root->data);
		newTree->col = _root->col;

		newTree->left = Building_Tree(_root->left);
		newTree->right = Building_Tree(_root->right);

		return newTree;
	}

	void Destory(Node* _root)
	{
		if (_root == nullptr)
			return;

		Destory(_root->left);
		Destory(_root->right);

		delete _root;
	}
private:
	Node* root;
	KeyOfT kot; // 控制比较时的类型，里面重载了仿函数
};

    • 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
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396
    • 397
    • 398
    • 399
    • 400
    • 401
    • 402
    • 403
    • 404
    • 405
    • 406
    • 407
    • 408
    • 409
    • 410
    • 411
    • 412
    • 413
    • 414
    • 415
    • 416
    • 417
    • 418
    • 419
    • 420
    • 421
    • 422
    • 423
    • 424
    • 425
    • 426
    • 427
    • 428
    • 429
    • 430
    • 431
    • 432
    • 433
    • 434
  • 相关阅读:
    小白学爬虫：通过关键词搜索1688商品列表数据接口|1688商品列表数据接口|1688商品列表数据采集|1688API接口
    云计算——ACA学习 云计算架构
    游戏中的随机——“动态平衡概率”算法
    CUDA小白 - NPP(4) 图像处理 Data Exchange and Initialization（2）
    Java精进-手写持久层框架
    移动跨平台技术方案浅析
    开发模式-敏捷开发
    BP神经网络对指纹识别的应用（Matlab代码实现）
    VR危险环境模拟介绍|VR虚拟现实设备
    计算机毕业设计ssm校园花卉销售系统ef5ox系统+程序+源码+lw+远程部署
  • 原文地址：https://blog.csdn.net/weixin_59400943/article/details/126447260