C++【STL---set&map底层红黑树（RBTree）】

1、什么是红黑树？

        红黑树是搜索二叉树的一种，它不像AVL树那样使用平衡因子严格的限制树的高度。它是通过节点的颜色来实现：树的最长路径不超过左端路径的二倍，从而接近平衡的；

红黑树的特点：

        1、根节点必须是黑色的；

        2、每条路径上的黑色节点的数量必须是相等的；

        3、不能出现连续相同的两个红色节点；

        4、节点的颜色不是红色就是个黑色；

        5、每条路径都是以空节点进行结束的，所谓的路径包含叶子节点到空节点的那一段；

 2、为什么要有红黑树？

        个人观点：因为AVL树太过严格，每次插入或者删除之后基本都要经历旋转调整，过程过于复杂；而红黑树要求最长路径不超过最短路径的二倍，这在某种程度上也要求了树的高度；从而保证了红黑树和AVL树的查找效率也在同一个量级。但是其插入或者删除的过程并非像AVL树那样复杂。

3、红黑树的构建

        关于一切数据结构的构建，都逃不开”先描述，再组织“这六个大字；描述一个红黑树节点，再通过红黑树该有的特性对节点进行链接。

3.1、节点描述

        使用枚举来给定节点的颜色；

enum Colour
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;
	
	RBTreeNode(const pair<K,V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

3.2、插入过程

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		else
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first < kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(kv);
			cur->_col = RED;//插入红色节点；
			if (parent->_kv.first < kv.first)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			cur->_parent = parent;

			//进行颜色调整
			while (parent && parent->_col == RED)
			{
				Node* grandFather = parent->_parent;
				if (parent == grandFather->_left)
				{
					Node* uncle = grandFather->_right;
					//叔叔节点存在且为红
					if (uncle && uncle->_col == RED)
					{
						//父亲叔叔变黑 爷爷变红
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandFather->_col = RED;

						//继续向上处理
						cur = grandFather;
						parent = cur->_parent;
					}
					//叔叔节点不存在 或者 叔叔节点存在且为黑
					else 
					{
						//旋转加变色
						if (cur == parent->_left)
						{
							//右单旋
							RotateR(grandFather);
							grandFather->_col = RED;
							parent->_col = BLACK;
						}
						else
						{
							//左右双旋
							RotateL(parent);
							RotateR(grandFather);
							cur->_col = BLACK;
							grandFather->_col = RED;
						}

						break;
					}
					
				}
				//parent == grandFather->_right
				else
				{
					Node* uncle = grandFather->_left;
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandFather->_col = RED;

						cur = grandFather;
						parent = cur->_parent;

					}
					else
					{
						if (cur == parent->_right)
						{
							RotateL(grandFather);
							parent->_col = BLACK;
							grandFather->_col = RED;
						}
						else
						{
							RotateR(parent);
							RotateL(grandFather);
							cur->_col = BLACK;
							grandFather->_col = RED;
						}

						break;
					}

				}
			}

			_root->_col = BLACK;

			return true;
		}
	}
private:
    Node* root = nullptr;
};

        这里先给出代码，下面进行逻辑的梳理，整个红黑树的插入过程可以简单分为三个部分：

        下面简单的展示一些具体的过程：

        当叔叔节点存在且为红的操作为直接变色向上叠加，过程简单。下面主要展示叔叔节点不存在或者存在且为黑色的旋转加变色的过程；

叔叔节点不存在：

叔叔节点存在且为黑（以左单旋和右左双旋为例）：

双旋到底先进行左还是右，主要是通过g\p\cur节点的位置来进行判断；

3.2、测试函数

	bool IsBalanceTree()
	{
		return IsBalance(_root);
	}
private:
	//红黑树的判断
	bool CheckColour(Node* root,int blackNum,int benchmark)
	{
		if (root == nullptr)
		{
			if (blackNum != benchmark)
				return false;
			return true;
		}
			
		//检查连续的红节点
		/*if (root->_col == RED)
		{
			//左孩子和右孩子可能不存在，所以下面的检查存在问题
			if (root->_left->_col == RED || root->_right->_col == RED)
			{
				return false;
			}
		}*/

		//检查连续的红节点
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "位置出现连续的红色节点" << endl;
			return false;
		}
		
		//检查黑色节点的数量
		if (root->_col == BLACK)
		{
			++blackNum;
		}

		return CheckColour(root->_left, blackNum,benchmark)
			&& CheckColour(root->_left, blackNum, benchmark);

	}

	bool IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}

		//利用红黑树的要求进行判断
		if (root->_col != BLACK)
		{
			return false;
		}

		int benchmark = 0;
		Node* cur = root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;
			cur = cur->_left;
		}

		return CheckColour(root,0,benchmark);
	}

#pragma once
#include<iostream>
using namespace std;

enum Colour
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;
	
	RBTreeNode(const pair<K,V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		else
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first < kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(kv);
			cur->_col = RED;//插入红色节点；
			if (parent->_kv.first < kv.first)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			cur->_parent = parent;

			//进行颜色调整
			while (parent && parent->_col == RED)
			{
				Node* grandFather = parent->_parent;
				if (parent == grandFather->_left)
				{
					Node* uncle = grandFather->_right;
					//叔叔节点存在且为红
					if (uncle && uncle->_col == RED)
					{
						//父亲叔叔变黑 爷爷变红
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandFather->_col = RED;

						//继续向上处理
						cur = grandFather;
						parent = cur->_parent;
					}
					//叔叔节点不存在 或者 叔叔节点存在且为黑
					else 
					{
						//旋转加变色
						if (cur == parent->_left)
						{
							//右单旋
							RotateR(grandFather);
							grandFather->_col = RED;
							parent->_col = BLACK;
						}
						else
						{
							//左右双旋
							RotateL(parent);
							RotateR(grandFather);
							cur->_col = BLACK;
							grandFather->_col = RED;
						}

						break;
					}
					
				}
				//parent == grandFather->_right
				else
				{
					Node* uncle = grandFather->_left;
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandFather->_col = RED;

						cur = grandFather;
						parent = cur->_parent;

					}
					else
					{
						if (cur == parent->_right)
						{
							RotateL(grandFather);
							parent->_col = BLACK;
							grandFather->_col = RED;
						}
						else
						{
							RotateR(parent);
							RotateL(grandFather);
							cur->_col = BLACK;
							grandFather->_col = RED;
						}

						break;
					}

				}
			}

			_root->_col = BLACK;

			return true;
		}
	}
	bool IsBalanceTree()
	{
		return IsBalance(_root);
	}
private:
	//红黑树的判断
	bool CheckColour(Node* root,int blackNum,int benchmark)
	{
		if (root == nullptr)
		{
			if (blackNum != benchmark)
				return false;
			return true;
		}
			
		//检查连续的红节点
		/*if (root->_col == RED)
		{
			//左孩子和右孩子可能不存在，所以下面的检查存在问题
			if (root->_left->_col == RED || root->_right->_col == RED)
			{
				return false;
			}
		}*/

		//检查连续的红节点
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "位置出现连续的红色节点" << endl;
			return false;
		}
		
		//检查黑色节点的数量
		if (root->_col == BLACK)
		{
			++blackNum;
		}

		return CheckColour(root->_left, blackNum,benchmark)
			&& CheckColour(root->_left, blackNum, benchmark);

	}

	bool IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}

		//利用红黑树的要求进行判断
		if (root->_col != BLACK)
		{
			return false;
		}

		int benchmark = 0;
		Node* cur = root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;
			cur = cur->_left;
		}

		return CheckColour(root,0,benchmark);
	}

	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curLeft = cur->_left;//可能为空，后面需要判断；
		Node* ppNode = parent->_parent;

		parent->_right = curLeft;
		if (curLeft)
		{
			curLeft->_parent = parent;
		}

		cur->_left = parent;
		parent->_parent = cur;


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

	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curRight = cur->_right;
		Node* ppNode = parent->_parent;

		parent->_left = curRight;
		if (curRight)
		{
			curRight->_parent = parent;
		}
		cur->_right = parent;
		parent->_parent = cur;

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

	}

	
private:
	Node* _root = nullptr;
};