C++ 红黑树：红黑树的插入及应用(map与set的封装)

红黑树

红黑树的概念

红黑树的性质

红黑树节点的定义

一、如果默认给黑色

二、如果默认给红色

红黑树的插入操作

1.按搜索树的规则进行插入

2.检测新节点插入后，红黑树的性质是否造到破坏

情况一：cur为红，parent为红，grandfather为黑，uncle存在且为红

情况二：cur 为红，parent 为红，grandfater 为黑，uncle不存在 / uncle存在且为黑

①cur 为红，parent 为红，grandfater 为黑，uncle不存在

②cur 为红，parent 为红，grandfater 为黑，uncle存在且为黑

③情况二的变形：双旋的情况

3.红黑树的插入的完整代码

红黑树的验证(红黑树插入实现的完整代码)

RBTree.h

test.cpp

红黑树与AVL树的比较

性能比较

红黑树模拟实现STL中的map与set

单树构建

红黑树模板参数的作用

结构改造与仿函数

myMap.h

mySet.h

RBTree.h

改造的过程中的问题(仿函数的使用)

编辑仿函数的使用

myMap.h

mySet.h

RBTree.h

迭代器的实现

myMap.h

RBTree.h

operator++ 和operator--的实现

map模拟实现细节

operator[] 的实现

map和set模拟实现的完整代码

myMap.h

mySet.h

RBTree.h

test.cpp

红黑树

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树的性质

左根右
红黑树是二叉搜索树，节点值满足左子树小于根节点、根节点小于右子树的大小关系，方便查找等操作。
根叶黑
根节点和叶子节点（空节点）颜色为黑色，这有助于统一规则来维护树的平衡。
不红红
红黑树中不能有相邻的红色节点，防止树的局部过度生长而失去平衡。
黑路同
从根节点到叶子节点的所有路径上，黑色节点的数量是一样的，以此来限制路径长度差，保证树接近平衡。

有了这些性质，红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的2倍。

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

因为 “黑路同” 的性质，无论哪条路径，黑色节点数量是固定的。在最短路径全是黑色节点的情况下，节点数量就是黑色节点的数量。

而在最长路径的极端情况（一黑一红交替）下，节点数量最多也就是黑色节点数量的两倍（每一个黑色节点后最多跟一个红色节点）。

所以综合来看，满足红黑树的这些性质（左根右、根叶黑、不红红、黑路同），就能保证其最长路径中节点个数不会超过最短路径节点个数的 2 倍。

注意：我们在数黑色节点个数的时候，每一条路径都需要算进去，把空节点当成黑色的叶子节点。

为什么要把空节点当成黑色节点也算成每条路径上的个数？？？

红黑树的核心平衡规则是 “黑路同”，即从根节点到每个叶子节点的所有路径上，黑色节点的数量是相同的。如果不算空节点，这个规则就会被破坏。
例如，考虑一个简单的红黑树结构，根节点为黑色，它有左右两个子树。左子树是一个完整的二叉树结构，右子树的最底层节点没有子节点（即有空节点）。如果我们在计算路径上黑色节点数量时不算空节点，那么从根节点到左子树最底层叶子节点的路径上黑色节点数量可能和到右子树非空节点的路径上黑色节点数量相同，但这忽略了右子树其实还可以延伸到空节点。算上空节点后，才能保证在任何情况下，所有路径（不管是否有实际节点延伸）上的黑色节点数量都能统一衡量，从而真正维护 “黑路同” 的性质。

红黑树节点的定义

我们这里实现 key-value 型的，在红黑树的节点中，就是多了一个标记颜色，通过标记颜色来调整红黑树的结构。

这里和AVL树一样还是给出三叉链的形式，因为当插入节点时候，如果破坏了红黑树的性质需要去找该节点的父节点及祖父节点。

//节点的颜色
enum Color
{
	BLACK,
	RED,
};
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv; //保存每个节点的值
	Color _col; //每个节点都需要标记颜色
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)   //默认给成红色
	{}
};

思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？

一、如果默认给黑色

若新插入节点默认设为黑色，很可能破坏红黑树 “黑路同” 性质(当插入是根节点时不会破坏，所以叫很可能)，使某路径黑色节点数变多，导致整个树平衡被破坏，且几乎所有路径相关节点都需调整，维护难度和工作量极大。

二、如果默认给红色

新插入节点默认设为红色时：

若父节点是黑色，不破坏现有性质，无需调整。
若父节点是红色，虽违反 “不红红” 性质，但仅需对这条有问题的路径做调整，比如旋转、变色等，相比默认黑色时对所有路径调整，难度和工作量小很多。

所以从维护平衡及减少调整工作量看，节点默认颜色设为红色更合理。

红黑树的插入操作

1.按搜索树的规则进行插入

二叉搜索树的实现，我们已经写了无数遍了，红黑树的插入和二叉搜索的插入是一样的。

enum Color
{
	BLACK,
	RED,
};
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv; //保存每个节点的值
	Color _col; //每个节点都需要标记颜色
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		//1、先按搜索树的规则进行插入
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;  // 插入的根节点变成黑色
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//新增节点,给红色
		cur->_col = RED;
		//如果红黑树的性质遭到破坏...进行处理
		//....
		return true;
	}
private:
	Node* _root = nullptr;
};

2.检测新节点插入后，红黑树的性质是否造到破坏

我们要控制最长路径不超过最短路径的2倍，主要是控制红黑树的这几条性质就可以了，不违反这些规则就搞定了。

cur为当前节点，parent 为父节点，grandfather 为祖父节点，uncle 为叔叔节点

如果插入节点的时候，破坏了红黑树的性质，调整红黑树的关键看叔叔节点。

为什么当红黑树被破坏需要调整时，关键是看叔叔节点呢？？

基于红黑树的性质和结构

红黑树有 “不红红” 的性质，即不能出现连续的红色节点。当插入一个节点（设为cur）后，如果cur和它的父节点（parent）都是红色，就违反了这个性质，需要进行调整来恢复红黑树的平衡。
在红黑树的结构中，parent节点是grandfather节点（祖父节点）的子节点，uncle节点是grandfather节点的另一个子节点（parent的兄弟节点）。uncle节点的颜色能反映出grandfather节点这一层及其子节点的颜色分布情况，这对于恢复平衡至关重要。

叔叔节点颜色决定调整策略

叔叔节点为红色时：
如果uncle节点是红色，这意味着在grandfather节点这一层，有两个红色子节点（parent和uncle）。这种情况下，红黑树在这局部区域的颜色分布是比较 “红” 的。
为了恢复平衡，我们可以将parent和uncle节点都变为黑色，grandfather节点变为红色。这样做不会改变从根节点到叶子节点的任何路径上的黑色节点数量（因为黑色节点数量的变化是在同一层内部进行调整的），很好地维护了 “黑路同” 的性质。同时，也解决了cur和parent同为红色的问题，恢复了 “不红红” 的性质。
叔叔节点为黑色时：
当uncle节点是黑色时，说明grandfather节点这一层及其子节点的颜色分布不均匀。这种不均匀可能是由于新插入节点cur的位置导致了局部结构失衡。
此时不能简单地通过变色来解决问题。因为如果只进行变色，可能会改变路径上的黑色节点数量，破坏 “黑路同” 的性质。所以需要进行旋转操作来调整树的结构。旋转的方向（左旋或右旋）和后续的变色操作取决于cur、parent和grandfather节点之间的位置关系。通过旋转和适当的变色，可以重新调整节点的位置关系，使红黑树恢复平衡，满足 “不红红” 和 “黑路同” 等性质。

因此，在插入节点破坏红黑树性质后，叔叔节点的颜色就像是一个 “指示器”，它能够帮助我们确定应该采取何种策略（变色还是旋转）来快速、有效地恢复红黑树的平衡。

情况一：cur为红，parent为红，grandfather为黑，uncle存在且为红

具象图：

插入节点破坏红黑树性质，叔叔节点为红色时：

不能动新插入的 cur 节点颜色，否则类似直接插入黑色节点，易违 “黑路同” 性质。
把 parent 和 uncle 变黑，能让相关两条路径各增一个黑节点，维持 “黑路同”。
祖父节点多为非根情况，不变色会使它所在路径多一个黑节点，所以要变红，保证无连续红节点且黑节点数不变。

若祖父是根，变色后把根变回黑色就行。若祖父不是根，再看祖父的父亲颜色，黑则结束，红则继续往上处理。

可能需要继续往上处理：

抽象图：

通过上面这些情况，当父亲为红色，且叔叔存在为红，就可以构出抽象图了。

注意：需要注意的是，当和下面抽象图反方向的位置时，处理也是一样的。三者的相对位置没有改变。

情况二：cur 为红，parent 为红，grandfater 为黑，uncle不存在 / uncle存在且为黑

第二种情况下，也细分成两种情况下，在这种情形中，会导致存在连续的红色节点，需要通过旋转 + 变色处理。

①cur 为红，parent 为红，grandfater 为黑，uncle不存在

处理过程：旋转 + 变色，始终保持两棵子树中存在一个黑节点，父亲变黑，祖父变红

②cur 为红，parent 为红，grandfater 为黑，uncle存在且为黑

处理过程：旋转 + 变色，父亲变黑，祖父变红

③情况二的变形：双旋的情况

叔叔不存在的时候：

叔叔存在且为黑色的时候：

以上就是插入的全部情形，这样我们的插入就可以很轻松实现了。

双旋情况下，我们可以简洁的处理

当我们完成了左单旋之后，交换parent 和 cur 两个指针，注意交换的是指针，然后按照情形二单旋的情况处理。

3.红黑树的插入的完整代码

	bool Insert(const pair<K, V>& kv)
	{
		//1、先按搜索树的规则进行插入
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//新增节点,给红色
		cur->_col = RED;
		while (parent && parent->_col == RED) // 父亲可以不存在，所以跳出循环
		{
			//红黑树的条件关键看叔叔，先找叔叔
			Node* grandfather = parent->_parent; //一定有祖父节点
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//情况一：叔叔存在且红色
				if (uncle && uncle->_col == RED) //叔叔可能不存在就走else
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;  //父节点不存在呢？？？所以前面while循环控制
				}
				else
				{
					//情况二：叔叔不存在/存在且为黑色，双旋变成单旋
					if (cur == parent->_right)
					{
						RotateL(parent);
						swap(parent, cur);
					}
					//第二种情况(也有可能是第三种情况变化过来的)
					RotateR(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}
			}
			else
			{
				//反方向~处理，一样的
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//叔叔节点不存在/叔叔节点是黑色
					if (parent->_left == cur)
					{
						RotateR(parent);
						swap(parent, cur);
					}
					RotateL(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}
			}
		}
		_root->_col = BLACK;  //管他根是红色黑色，直接变成黑色
		return true;
	}

红黑树的验证(红黑树插入实现的完整代码)

RBTree.h

#pragma once
enum Color
{
	BLACK,
	RED,
};
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv; //保存每个节点的值
	Color _col; //每个节点都需要标记颜色
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		//1、先按搜索树的规则进行插入
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//新增节点,给红色
		cur->_col = RED;
		while (parent && parent->_col == RED) // 父亲可以不存在，所以跳出循环
		{
			//红黑树的条件关键看叔叔，先找叔叔
			Node* grandfather = parent->_parent; //一定有祖父节点
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//情况一：叔叔存在且红色
				if (uncle && uncle->_col == RED) //叔叔可能不存在就走else
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;  //父节点不存在呢？？？所以前面while循环控制
				}
				else
				{
					//情况二：叔叔不存在/存在且为黑色，双旋变成单旋
					if (cur == parent->_right)
					{
						RotateL(parent);
						swap(parent, cur);
					}
					//第二种情况(也有可能是第三种情况变化过来的)
					RotateR(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}
			}
			else
			{
				//反方向~处理，一样的
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//叔叔节点不存在/叔叔节点是黑色
					if (parent->_left == cur)
					{
						RotateR(parent);
						swap(parent, cur);
					}
					RotateL(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}
	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		subR->_left = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subR;
		//1,parent是原来这棵树的根，现在subR是根
		//2,parent 为根的树只是整颗树中的子树，改变链接关系，那么subR就要顶替它的位置
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
			subR->_parent = ppNode;
		}
		//parent->_bf = subR->_bf = 0;
	}
	//右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		subL->_right = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subL;
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;
			subL->_parent = ppNode;
		}
		//subL->_bf = parent->_bf = 0;
	}
	//中序遍历
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
	void InOrder()
	{
		_InOrder(_root);
	}
	//检测是否是红黑树
	bool _IsValidRBTree(Node* root, size_t k, const size_t blackCount)
	{
		//走到null之后，判断k和black是否相等
		if (nullptr == root)
		{
			if (k != blackCount)
			{
				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
				return false;
			}
			return true;
		}
		// 统计黑色节点的个数
		if (BLACK == root->_col)
			++k;
		// 检测当前节点与其双亲是否都为红色
		Node* parent = root->_parent;
		if (parent && RED == parent->_col && RED == root->_col)
		{
			cout << "违反性质三：没有连在一起的红色节点" << endl;
			return false;
		}
		return _IsValidRBTree(root->_left, k, blackCount) &&
			_IsValidRBTree(root->_right, k, blackCount);
	}
	bool IsValidRBTree()
	{
		Node* root = _root;
		// 空树也是红黑树
		if (nullptr == root)
			return true;
		// 检测根节点是否满足情况
		if (BLACK != root->_col)
		{
			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
			return false;
		}
		// 获取任意一条路径中黑色节点的个数
		size_t blackCount = 0;
		Node* cur = root;
		while (cur)
		{
			if (BLACK == cur->_col)
				blackCount++;
			cur = cur->_left;
		}
		// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
		size_t k = 0;
		return _IsValidRBTree(root, k, blackCount);
	}
private:
	Node* _root = nullptr;
};
void TestRBTree()
{
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	//int a[] = { 5, 30, 70, 11, 2, 1, 18, 100, 10000 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOrder();
	cout << endl;
	//检测是否是红黑树
	cout << t.IsValidRBTree() << endl;
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#include "RBTree.h"
int main() 
{
	TestRBTree();
	return 0;
}

红黑树与AVL树的比较

时间复杂度：

红黑树增删查改在特殊情况（全黑等）下时间复杂度是 O(logN)，最短路径也是，最长路径为 2 X O(logN) 。理论上红黑树效率似乎比 AVL 树低，AVL树增删查改时间复杂度稳定在O(logN)，因其平衡要求更严格，靠多旋转维持(AVL树的旋转次数比红黑树更多)。
实际应用情况：
插入删除同样多节点时，红黑树比 AVL 树旋转少，实现也更容易控制。
虽理论上红黑树最长路径是最短路径两倍，但现在硬件运算速度快，logN 通常较小，所以实际应用中二者基本没差异了，所以红黑树使用的更多。

性能比较

我们已经学会了红黑树和AVL树，这段代码比较两者在插入时的效率。

#include <iostream>
using namespace std;
#include "RBTree.h"
#include "AVLTree.h"
#include <vector>
#include <time.h>
void TestRB_AVLTree() 
{
	const int n = 100000; //10w的随机数的插入
	vector<int> v;
	v.reserve(n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i) 
	{
		v.push_back(rand());
	}
	RBTree<int, int> rbtree;
	AVLTree<int, int> avltree;
	size_t begin1 = clock();
	for (auto& e : v) 
	{
		rbtree.Insert(make_pair(e, e));
	}
	size_t end1 = clock();
	size_t begin2 = clock();
	for (auto& e : v) 
	{
		avltree.Insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "红黑树：" << end1 - begin1 << endl;
	cout << "AVL树：" << end2 - begin2 << endl;
}
int main() 
{
	TestRB_AVLTree();
	return 0;
}

红黑树模拟实现STL中的map与set

我们实现了红黑树的插入之后，就可以来模拟实现map和set了，map和set的底层就是红黑树实现的。

单树构建

本来要写两颗红黑树，但是实际上一棵红黑树就可以了。

map的底层传给红黑树的是 key 和 pair，而 set 的底层传给红黑树的是 key 和 key，本质是复用一颗红黑树。

红黑树模板参数的作用

Key：一般代表键（key）的类型，用于在红黑树中进行节点的比较、排序等操作，以确定节点在树中的位置。
Value：通常是红黑树节点实际存储的数据类型，对于 map 来说可能是键值对类型（如 pair<K, V>），对于 set 来说可能就是元素本身（也就是 K 类型）。

是不是发现感觉第一个参数没有什么用，其实不能去掉，当我们去查找的使用就需要用到 key类型来查找。

结构改造与仿函数

myMap.h

namespace myMap
{
	template<class K, class V> 
	class map 
	{
	public:

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

mySet.h

namespace mySet
{
	template<class K>
	class set
	{
	public:


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

RBTree.h

改造的过程中的问题(仿函数的使用)

第二个模板参数决定了是 map 还是 set，传过去的是 pair 说明是map，传过去的是 key 说明是set, 红黑树插入的时候要进行比较，但是我们不确定的时候如何进行比较，如果是key直接比较没有问题，但是 pair 无法比较。

针对map和set需要给出不同的比较方式，这个时候仿函数就派上用场了。

仿函数的使用

myMap.h

namespace myMap
{
	template<class K, class V> 
	class map 
	{
	public:
		//仿函数
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	private:
		RBTree<K, pair<K, V>, MapKeyOfT> _t;
	};
}

mySet.h

namespace mySet
{
	template<class K>
	class set
	{
	public:
		//仿函数
		struct SetKeyOfT
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};
}

RBTree.h

迭代器的实现

我们直接拿map来实现，map实现了，set 也是同理。

myMap.h

当编译器处理到这样的代码时，如果没有 typename 关键字，编译器会默认认为 RBTree<K, pair<K, V>, MapKeyOfT>::iterator 是一个静态成员（比如静态变量或者静态函数等）而不是一个类型。因为在模板类的范围内，成员的类型在未完全实例化之前，编译器是不确定其到底是一个类型还是其他的成员形式（比如静态成员函数、静态变量等）。

而加上 typename 关键字后，就明确地告诉编译器 RBTree<K, pair<K, V>, MapKeyOfT>::iterator 是一个类型，让编译器按照处理类型的方式来对待它，这样就可以正确地进行类型定义（通过 typedef），从而使得代码能够顺利编译通过。

namespace myMap
{
	template<class K, class V> 
	class map 
	{
	public:
		//仿函数
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
		//迭代器
		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		//插入
		bool Insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv); //插入的本质就是在调用红黑树的插入
		}
	private:
		RBTree<K, pair<K, V>, MapKeyOfT> _t;
	};
	void test_map()
	{
		map<int, int> m;
		m.Insert(make_pair(1, 1));
		m.Insert(make_pair(3, 3));
		m.Insert(make_pair(7, 7));
		m.Insert(make_pair(4, 4));
		m.Insert(make_pair(11, 11));
		m.Insert(make_pair(2, 2));
	}
}

RBTree.h

红黑树的迭代器中的 begin，拿到的是红黑树中最左的那个节点，我们这里 end 给 nullptr值。

//迭代器
template<class T>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef  __TreeIterator<T> Self;
	Node* _node;
	__TreeIterator(Node* node)
		:_node(node)
	{}
	T& operator*()
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &_node->_data;
	}
	Self& operator++()
	{
		return *this;
	}
	Self& operator--()
	{
		return *this;
	}
	bool operator==(const Self& s)
	{
		return s._node == _node;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};

template<class K, class T, class KOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	//迭代器
	typedef __TreeIterator<T> iterator;
	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}
	iterator end()
	{
		return iterator(nullptr);
	}
	//插入操作...下面代码省略

operator++ 和operator--的实现

operator++的实现

其逻辑主要分两种情况：

情况一：当前节点有右子树

若当前节点（通过_node获取并赋值给cur）存在右子树，就先找到右子树的最左节点。具体做法是先将右子节点赋值给subL，然后通过循环不断查找subL的左子节点直至不存在左子节点，此时subL就是右子树的最左节点，最后将该最左节点赋值给_node，确定下一个要访问的节点。

情况二：当前节点没有右子树

当当前节点没有右子树时，先获取其父节点（赋值给parent），接着通过循环沿着父节点链向上查找，直到找到一个节点，其不是其父节点的右子节点（或者到达根节点，此时parent为空），最后将找到的这个节点赋值给_node，以此确定下一个要访问的节点。

Self& operator++()
{
	Node* cur = _node;
	//右不为空，就是右子树的最左节点
	if (cur->_right)
	{
		Node* subL = cur->_right;
		while (subL->_left)
		{
			subL = subL->_left;
		}
		//赋值
		_node = subL;
	}
	else
	{
		Node* parent = cur->_parent;
		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}

operator--的实现

operator-- 的实现和operator++ 的实现逻辑类似，就是方向是相反的。

根据红黑树画图理解一下子就理解了。

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

map模拟实现细节

operator[] 的实现

operator[]的本质是调用 insert。

这里介绍了operator[]的本质以及operator[]的使用情况，如何理解等：C++STL之 set 和 map：介绍及基本使用-CSDN博客

传过去的是key值，insert调用返回的是pair<iterator,bool>类型，这样我们就可以利用operator[]来统计次数。

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

map和set模拟实现的完整代码

myMap.h

#pragma once
namespace myMap
{
	template<class K, class V> //知道了int int 类型
	class map
	{
	public:
		//仿函数
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
		//迭代器
		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		//operator[]
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
			return ret.first->second;
		}
		//插入
		pair<iterator, bool> Insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RBTree<K, pair<K, V>, MapKeyOfT> _t;//模板参数就是告诉红黑树是什么类型
	};
	void test_map()
	{
		map<int, int> m;
		m.Insert(make_pair(1, 1));
		m.Insert(make_pair(3, 3));
		m.Insert(make_pair(7, 7));
		m.Insert(make_pair(4, 4));
		m.Insert(make_pair(11, 11));
		m.Insert(make_pair(2, 2));
		map<int, int>::iterator it = m.begin();
		while (it != m.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;
		//统计次数
		cout << "统计次数" << endl;
		string strs[] = { "西瓜","香蕉","西瓜","苹果","西瓜","西瓜","西瓜","苹果" };
		map<string, int> countMap;
		for (auto& str : strs)
		{
			countMap[str]++;
		}
		for (auto& e : countMap)
		{
			cout << e.first << e.second << endl;
		}
	}
}

mySet.h

#pragma once
namespace mySet
{
	template<class K>
	class set
	{
	public:
		//仿函数
		struct SetKeyOfT
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};
		//迭代器
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		//插入
		pair<iterator, bool> Insert(const K& k)
		{
			return _t.Insert(k);
		}
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};
	void test_set()
	{
		set<int> s;
		s.Insert(1);
		s.Insert(3);
		s.Insert(5);
		s.Insert(7);
		s.Insert(2);
		set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
}

RBTree.h

#pragma once
enum Color
{
	BLACK,
	RED,
};
template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Color _col; //每个节点都需要标记颜色
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};

//迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef  __TreeIterator<T, Ref, Ptr> Self;
	Node* _node;
	__TreeIterator(Node* node)
		:_node(node)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	Self& operator++()
	{
		Node* cur = _node;
		//右不为空，就是右子树的最左节点
		if (cur->_right)
		{
			Node* subL = cur->_right;
			while (subL->_left)
			{
				subL = subL->_left;
			}
			//赋值
			_node = subL;
		}
		else
		{
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	Self& operator--()
	{
		Node* cur = _node;
		if (cur->_left)
		{
			Node* subR = cur->left;
			while (subR->_right)
			{
				subR = subR->_right;
			}
			_node = subR;
		}
		else
		{
			Node* parent = cur->_parent;
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	bool operator==(const Self& s)
	{
		return s._node == _node;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};

template<class K, class T, class KOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	//迭代器
	typedef __TreeIterator<T, T&, T*> iterator;
	typedef __TreeIterator<T, const T&, const T*> const_iterator;
	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}
	const_iterator begin() const
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return const_iterator(cur);
	}
	iterator end()
	{
		return iterator(nullptr);
	}
	const_iterator end() const
	{
		return const_iterator(nullptr);
	}
	//插入
	pair<iterator, bool> Insert(const T& data)
	{
		//1、先按搜索树的规则进行插入
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}
		KOfT koft;
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (koft(data) > koft(cur->_data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (koft(data) < koft(cur->_data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}
		cur = new Node(data);
		//保存新增的节点
		Node* newnode = cur;
		if (koft(data) > koft(parent->_data))
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//新增节点,给红色
		cur->_col = RED;
		while (parent && parent->_col == RED)
		{
			//红黑树的条件关键看叔叔，先找叔叔
			Node* grandfather = parent->_parent; //一定有祖父节点
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//情况一：叔叔存在且红色
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;  //父节点不存在呢？？？所以前面while循环控制
				}
				else
				{
					//情况二：叔叔不存在/存在且为黑色，双旋变成单旋
					if (cur == parent->_right)
					{
						RotateL(parent);
						swap(parent, cur);
					}
					//第二种情况(也有可能是第三种情况变化过来的)
					RotateR(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}
			}
			else
			{
				//反方向~
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//叔叔节点不存在/叔叔节点是黑色
					if (parent->_left == cur)
					{
						RotateR(parent);
						swap(parent, cur);
					}
					RotateL(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}
			}
		}
		_root->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}
	iterator Find(const K& key)
	{
		KOfT koft;
		Node* cur = _root;
		while (cur)
		{
			if (key > koft(cur->_data))
			{
				cur = cur->_right;
			}
			else if (key < koft(cur->_data))
			{
				cur = cur->_left;
			}
			else
			{
				return iterator(cur);
			}
		}
		return iterator(nullptr);
	}
	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		subR->_left = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subR;
		//1,parent是原来这棵树的根，现在subR是根
		//2,parent 为根的树只是整颗树中的子树，改变链接关系，那么subR就要顶替它的位置
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
			subR->_parent = ppNode;
		}
		//parent->_bf = subR->_bf = 0;
	}
	//右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		subL->_right = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subL;
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;
			subL->_parent = ppNode;
		}
		//subL->_bf = parent->_bf = 0;
	}
private:
	Node* _root = nullptr;
};

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#include "RBTree.h"
#include "myMap.h"
#include "mySet.h"
int main()
{
	mySet::test_set();
	myMap::test_map();
	return 0;
}