//枚舉紅黑顏色
enum colour 
{
	RED,
	BLACK,
};
//定義紅黑樹(shù)結(jié)點(diǎn)結(jié)構(gòu)
template<class K,class V>
struct RBTreeNode 
{
	//構(gòu)造
	RBTreeNode(const pair<K, V>& kv = {0,0})
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_col(BLACK)
	{ }
	//定義三叉鏈
	RBTreeNode<K, V>* _left; //左孩子
	RBTreeNode<K, V>* _right;//右孩子
	RBTreeNode<K, V>* _parent;  //父親
	pair<K, V> _kv;  //pair對(duì)象
	//節(jié)點(diǎn)的顏色
	colour _col;  //定義枚舉變量
};
//定義紅黑樹(shù)
template<class K, class V>
class RBTree 
{
		typedef RBTreeNode<K, V> Node;
	public:
		//構(gòu)造
		RBTree() 
			:_root(nullptr)
		{}
	private:
		Node* _root;  //定義樹(shù)的根節(jié)點(diǎn)
};

pair<Node*, bool> Insert(const pair<K, V>& kv)
{
	if (!_root) //空樹(shù)處理
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return { _root, true };
	}
	//二叉搜索樹(shù)的插入邏輯
	Node* cur = _root, * parent = nullptr;
	while (cur)
	{
		if (cur->_kv.first < kv.first)//插入結(jié)點(diǎn)比當(dāng)前結(jié)點(diǎn)大 
		{
			parent = cur;
			cur = cur->_right; 
		}
		else if (cur->_kv.first > kv.first) //插入結(jié)點(diǎn)比當(dāng)前結(jié)點(diǎn)小 
		{
			parent = cur;
			cur = cur->_left; 
		}
		else 
		{
			return { cur, false }; //插入失敗
		}
	}
	cur = new Node(kv);
	cur->_col = RED;  //新增結(jié)點(diǎn)顏色默認(rèn)設(shè)置為RED
	//判斷插入結(jié)點(diǎn)是否在parent的左邊或者右邊
	if (parent->_kv.first > kv.first)  //左邊
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else     //右邊	
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	/* 紅黑樹(shù)性質(zhì)處理：
		如果這棵樹(shù)一開(kāi)始是符合紅黑樹(shù)的性質(zhì)，但在新增結(jié)點(diǎn)之后，
		導(dǎo)致失去了紅黑樹(shù)的性質(zhì)，這里需要控制結(jié)點(diǎn)的顏色和限制
		每條路徑上黑色結(jié)點(diǎn)的個(gè)數(shù)，以上情況都要處理
    */
	while (parent && parent->_col == RED) //父親存在且父親為紅色
	{
		Node* grandfather = parent->_parent;  //祖父
		//父親出現(xiàn)在祖父的左邊需要考慮的情況
		if(parent == grandfather ->left)
		{
			//1、uncle存在，uncle為紅色
			/*
			   如果parent和uncle都存在并且都為紅色這是情況一，
			   需要將parent和uncle的顏色變成紅色，祖父顏色變成黑色
			   更新cur、parent、grandfather、uncle 繼續(xù)向上調(diào)整
			*/
			//2、uncle不存在
			/*  這里考慮兩種旋轉(zhuǎn)情況，直線單旋轉(zhuǎn)，折線雙旋
				/*
					cur出現(xiàn)在parent的左邊 ,右單旋轉(zhuǎn)
					經(jīng)過(guò)右單旋后，parent去做樹(shù)的根,祖父做為右子樹(shù)
					//調(diào)節(jié)結(jié)點(diǎn)顏色
					parent->_col = BLACK;
					grandfather->_col = RED;
				*/
				/*
					cur出現(xiàn)在parent的右邊，左右雙旋
					經(jīng)過(guò)雙旋后，cur作為樹(shù)的根，grandfather為右子樹(shù)
					調(diào)節(jié)結(jié)點(diǎn)顏色
					cur->_col = BLACK;
					grandfather->_col = RED;  
				*/
			*/ 
		}
		else  //父親出現(xiàn)在祖父的右邊
		{
			Node* uncle = grandfather->_left; //叔叔在左子樹(shù) 
			/*
			情況一：叔叔存在，且叔叔和父親都是紅色，那么就需要將父親
			和叔叔結(jié)點(diǎn)的顏色變成黑色，再將祖父的顏色變成紅色，
			繼續(xù)向上調(diào)整，更新孩子、父親、祖父、叔叔的位置
			*/
			/*
				情況二：叔叔不存在
				/*
				 	1、新增結(jié)點(diǎn)出現(xiàn)在父親的右邊，直線情況，左單旋處理
				 	旋轉(zhuǎn)完后parent去做父親的根，grandfather做父親
				 	的左子樹(shù)
							//調(diào)節(jié)顏色，根為黑，左右孩子為紅
					2、新增結(jié)點(diǎn)出現(xiàn)在父親的左邊，會(huì)出現(xiàn)折現(xiàn)的情況，
					引發(fā)雙旋，旋轉(zhuǎn)完后，cur變成根，
					parent和grandfaher去做cur的左右孩子
						   //調(diào)節(jié)顏色,根結(jié)點(diǎn)為黑，左右孩子為紅
				*/
			*/	
		}
	}
	//如果父親不存在為了保證根結(jié)點(diǎn)是黑色的，這里一定得將根結(jié)點(diǎn)處理為黑色
	_root->_col = BLACK;
}

//1、父親一定存在的情況，叔叔存在/不存在 父親叔叔結(jié)點(diǎn)顏色為紅色
while (parent && parent->_col == RED) //父親存在且父親為紅色
{
	Node* grandfather = parent->_parent;  //祖父
	//如果父親和叔叔結(jié)點(diǎn)顏色都是紅色
	if (parent == grandfather->_left)  
	{
		Node* uncle = grandfather->_right;  
		if (uncle && uncle->_col == RED)  //對(duì)應(yīng)情況：uncle存在且為紅
		{
			//處理：父親和叔叔變成黑色，祖父變成紅色，繼續(xù)向上調(diào)整
			uncle->_col = parent->_col = BLACK; 
			grandfather->_col = RED;
			//向上調(diào)整
			cur = grandfather;  //調(diào)整孩子
			parent = cur->_parent;//調(diào)整父親
		}
		else   //uncle不存在，uncle存在且為黑
		{
			//直線情況(cur在parent的左邊)：只考慮單旋，以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)，
			//旋轉(zhuǎn)完后將祖父的顏色變成紅色，將父親的顏色變成黑色
			if (parent->_left == cur) 
			{
				RotateR(grandfather);
				parent->_col = BLACK;
				grandfather->_col = RED;
			}
			else  //parent->_right == cur 
			{	
				//折線情況(cur在parent的右邊)：這里會(huì)引發(fā)雙旋
				RotateL(parent);  //以parent為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋
				RotateR(grandfather); //以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)
				//旋轉(zhuǎn)完后cur會(huì)去做樹(shù)的根，那么設(shè)置為黑色，
				//為了保證每條路徑的黑色結(jié)點(diǎn)個(gè)數(shù)相同，grandfather結(jié)點(diǎn)顏色設(shè)置為紅
				cur->_col = BLACK;
				grandfather->_col = RED;  //黑色	結(jié)點(diǎn)個(gè)數(shù)相同
			}
		}
	}
	else //父親在右子樹(shù)
	{
			Node* uncle = grandfather->_left; //叔叔在左子樹(shù) 
			if (uncle&& uncle->_col == RED)  //情況一處理：叔叔存在，且叔叔的顏色是紅色的（包含了父親的顏色是紅色的情況）
			{
				//根據(jù)情況一處理即可：叔叔和父親變黑，
				//祖父變紅(目的是為了每條路徑的黑色結(jié)點(diǎn)個(gè)數(shù)相同)，繼續(xù)向上
				cur = grandfather;  //孩子
				parent = cur->_parent;//父親
			}
			else //叔叔不存在 
			{
				if (cur == parent->_right)  //新增結(jié)點(diǎn)在父親的右邊，直線情況左單旋處理
				{
					//左單旋轉(zhuǎn)，以grandfather為旋轉(zhuǎn)點(diǎn)，旋轉(zhuǎn)完后parent去做新的根，grandfather去做左子樹(shù)
					RotateL(grandfather);
					//調(diào)節(jié)顏色
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				else //新增結(jié)點(diǎn)在父親的左邊，折線情況，引發(fā)雙旋
				{
					//處理：以parenrt為旋轉(zhuǎn)點(diǎn)做右單旋，再以grandfather為旋轉(zhuǎn)點(diǎn)做左單旋
					RotateR(parent);  //右旋
					RotateL(grandfather); //左旋
					parent->_col = grandfather->_col = RED;
					cur->_col = BLACK;
				}
				break;
			}
		}
	_root->_col = BLACK;
}

Node* uncle = grandfather->_right;  
if (uncle && uncle->_col == RED)  //對(duì)應(yīng)情況：uncle存在且為紅
{
	//處理：父親和叔叔變成黑色，祖父變成紅色，繼續(xù)向上調(diào)整
	uncle->_col = parent->_col = BLACK; 
	grandfather->_col = RED;
	//向上調(diào)整
	cur = grandfather;  //調(diào)整孩子
	parent = cur->_parent;//調(diào)整父親
}

else   //uncle不存在，uncle存在且為黑
{
	//直線情況(cur在parent的左邊)：只考慮單旋，以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)，
	//旋轉(zhuǎn)完后將祖父的顏色變成紅色，將父親的顏色變成黑色
	if (parent->_left == cur) 
	{
		RotateR(grandfather);
		parent->_col = BLACK;
		grandfather->_col = RED;
	}
	else  //parent->_right == cur 
	{	
		//雙旋轉(zhuǎn)
	}
}

//折線情況(cur在parent的右邊)：這里會(huì)引發(fā)雙旋
RotateL(parent);  //以parent為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋
RotateR(grandfather); //以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)
//旋轉(zhuǎn)完后cur會(huì)去做樹(shù)的根，那么設(shè)置為黑色，
//為了保證每條路徑的黑色結(jié)點(diǎn)個(gè)數(shù)相同，grandfather結(jié)點(diǎn)顏色設(shè)置為紅
cur->_col = BLACK;
grandfather->_col = RED; 

void RotateR(Node* parent) //右單旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR) subLR->_parent = parent;  //防止subLR為nullptr
		subL->_right = parent;
		Node* parent_parent = parent->_parent; //指針備份
		parent->_parent = subL;
		if (_root == parent) //如果parent就是樹(shù)的根 
		{
			_root = subL;  //subL取代parent
			_root->_parent = nullptr;
		}
		else  //如果parent并不是樹(shù)的根
		{
			if (parent_parent->_left == parent) parent->_left = subL;
			else parent_parent->_right = subL;
			subL->_parent = parent_parent; //subL去做parent_parent的孩子
		}
	}
	//左單旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL) subRL->_parent = parent;
		subR->_left = parent;
		Node* parent_parent = parent->_parent;
		parent->_parent = subR;
		if (_root == parent)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent_parent->_left == parent) parent_parent->_left = subR;
			else parent_parent->_right = subR;
			subR->_parent = parent_parent;
		}
	}

/*
	紅黑樹(shù)的幾點(diǎn)性質(zhì)在于：
	1、根結(jié)點(diǎn)必須是紅色的
	2、不會(huì)出現(xiàn)連續(xù)的紅色結(jié)點(diǎn)
	3、所有路徑的黑色結(jié)點(diǎn)個(gè)數(shù)是相同的
*/
bool _CheckBlance(Node* root, int isBlackNum, int count) 
{
	if (!root) 
	{
		if (isBlackNum != count) 
		{
			printf("黑色結(jié)點(diǎn)個(gè)數(shù)不均等\n");
			return false;
		}
		return true; //遍歷完整棵樹(shù)，如果以上列舉的非法情況都不存在就返回true
	}
	//檢查是否出現(xiàn)連續(xù)的紅色結(jié)點(diǎn)
	if (root->_col == RED && root->_parent->_col == RED) 
	{
		printf("出現(xiàn)了連續(xù)的紅色結(jié)點(diǎn)\n");
		return false;
	} 
	//走前序遍歷的過(guò)程中記錄每一條路徑黑色結(jié)點(diǎn)的個(gè)數(shù)
	if (root->_col == BLACK) count++;
	//遞歸左右子樹(shù)
	return _CheckBlance(root->_left, isBlackNum, count) && 
			_CheckBlance(root->_right, isBlackNum, count);
}
//驗(yàn)證紅黑樹(shù)
bool CheckBlance()
{
	if (!_root) return true;  //樹(shù)為null
	//根結(jié)點(diǎn)是黑色的
	if (_root->_col != BLACK) 
	{
		printf("根結(jié)點(diǎn)不是黑色的\n");
		return false;
	}
	//每一條路徑黑色結(jié)點(diǎn)的個(gè)數(shù)必須是相同的，
	int isBlcakNum = 0;
	Node* left = _root; 
	while (left) 
	{
		if (left->_col == BLACK) isBlcakNum++; // 統(tǒng)計(jì)某一條路徑的所以黑色結(jié)點(diǎn)個(gè)數(shù)
		left = left->_left;
	}
	//檢查連續(xù)的紅色結(jié)點(diǎn)，檢查每一條路徑的黑色結(jié)點(diǎn)個(gè)數(shù)是否相等
	return _CheckBlance(_root, isBlcakNum ,0);
}