#include <iostream>

using namespace std;

namespace bit
{
	enum Color
	{
		RED,
		BLACK
	};

	template<class K,class V>
	struct RBTreeNode
	{
		RBTreeNode<K,V>* _left = nullptr;
		RBTreeNode<K,V>* _right = nullptr;
		RBTreeNode<K,V>* _parent = nullptr;
		Color _col = RED;
		pair<K, V> _value;
		RBTreeNode(const pair<K,V>& value)
			:_value(value)
		{}
	};

	template<class K,class V>
	class RBTree
	{
		typedef RBTreeNode<K, V> Node;
	private:
		Node* _root = nullptr;

		void RotateR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;

			Node* pparent = parent->_parent;

			parent->_left = subLR;
			if (subLR)
				subLR->_parent = parent;

			subL->_right = parent;
			parent->_parent = subL;

			if (pparent == nullptr)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				subL->_parent = pparent;
				if (pparent->_left == parent)
				{
					pparent->_left = subL;
				}
				else
				{
					pparent->_right = subL;
				}
			}


		}

		void RotateL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			Node* pparent = parent->_parent;

			parent->_right = subRL;
			if (subRL)
				subRL->_parent = parent;

			subR->_left = parent;
			parent->_parent = subR;

			if (pparent == nullptr)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				subR->_parent = pparent;
				if (pparent->_left == parent)
				{
					pparent->_left = subR;
				}
				else
				{
					pparent->_right = subR;
				}
			}
		}

		void inorder(Node* root)
		{
			if (root == nullptr)
				return;

			inorder(root->_left);
			cout << root->_value.first << ":" << root->_value.second << endl;
			inorder(root->_right);
		}

	public:
		void InOrder()
		{
			inorder(_root);
		}

		bool insert(const pair<K, V>& value)
		{
			if (_root == nullptr)//空树就直接申请节点，将根节点处理成黑色
			{
				_root = new Node(value);
				_root->_col = BLACK;
				return true;
			}

			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (value.first > cur->_value.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (value.first < cur->_value.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;//已经存在就插入失败
				}
			}

			cur = new Node(value);
			cur->_parent = parent;

			if (value.first > parent->_value.first)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}


			while (parent && parent->_col == RED)
			{
				Node* grandparent = parent->_parent;
				if (parent == grandparent->_left)//parent在左侧
				{
					Node* uncle = grandparent->_right;

					if (uncle && uncle->_col == RED)//叔叔存在且为红
					{
						parent->_col = uncle->_col = BLACK;
						grandparent->_col = RED;
						cur = grandparent;
						parent = cur->_parent;
					}
					else//叔叔不存在或者叔叔为黑色，则进行旋转 + 变色
					{
						if (cur == parent->_left)//进行右单旋即可
						{
							RotateR(grandparent);
							parent->_col = BLACK;
							grandparent->_col = RED;
						}
						else
						{
							RotateL(parent);
							RotateR(grandparent);
							cur->_col = BLACK;
							grandparent->_col = RED;
						}

						break;
					}
				}
				else//parent在右侧
				{
					Node* uncle = grandparent->_left;

					if (uncle && uncle->_col == RED)//叔叔存在且为红
					{
						parent->_col = uncle->_col = BLACK;
						grandparent->_col = RED;
						cur = grandparent;
						parent = cur->_parent;
					}
					else//叔叔不存在或者叔叔为黑色
					{
						if (cur == parent->_right)
						{
							RotateL(grandparent);
							parent->_col = BLACK;
							grandparent->_col = RED;
						}
						else
						{
							RotateR(parent);
							RotateL(grandparent);
							cur->_col = BLACK;
							grandparent->_col = RED;
						}
						break;
					}


				}
			}

			_root->_col = BLACK;

			return true;
		}

	};
}

---

关于红黑树的删除，这里就不进行讲解了，感兴趣的同学可以去看看算法导论和殷人昆老师的数据结构教材，里面可以找到答案。