1 红黑树的概念

通过上述性质我们可以得出：

一条最短的路径就是只有黑节点的路径。而一条最长路径就是黑红相间的路径，这样就可以保证没有一条路径会比其他路径长出俩倍。

2.红黑树的插入

2.1.叔叔节点存在且为红

等等还有很多种可能，但是他们对应的处理方式都是一样的。

2.2叔叔节点不存在或者叔叔节点存在且为黑

无论是叔叔节点不存在还是存在且为黑，他们的处理方法都是一样的，都是旋转加变色，旋转变色后就是一颗符合规则的红黑子树。这里的旋转是根据g，p，cur节点的位置进行旋转的。

3.代码实现

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

enum Col
{
	BLACK,
	RED
};
template<class K,class V>
struct RBTreeNode
{

	RBTreeNode(const pair<K,V>& kv)
		:_parent(nullptr)
		,_left(nullptr)
		,_right(nullptr)
		,_kv(kv)
		,_col(RED)
	{}


	RBTreeNode<K, V>* _parent;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;

	pair<K, V>_kv;
	Col _col;
};

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;
		}

		Node* cur = _root;
		Node* parent = nullptr;

		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if(cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}

		//找到要插入的位置 进行链接
		cur = new Node(kv);
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//进行调整 父亲节点存在且为红 才需要调整 默认插入的节点是红色的
		while (parent && parent->_col==RED)
		{
			Node* gradeparent = parent->_parent; //gradeparent节点一定存在 否则不会进入这里 直接就插入成功了
			if (parent == gradeparent->_left)
			{
				Node* uncle = gradeparent->_right;
				//叔叔节点存在且为红
				if (uncle && uncle->_col == RED)
				{
					//变色+继续向上调整
					uncle->_col = parent->_col = BLACK;
					gradeparent->_col = RED;

					//向上调整 此时parent相当于cur
					cur = gradeparent;
					parent = cur->_parent;
				}
				//叔叔节点不存在 or 叔叔节点存在为黑
				else 
				{
					//旋转加变色
					if (cur == parent->_left)
					{
						//    g
						//  p
						//c
						RotateR(gradeparent);
						parent->_col = BLACK;
						gradeparent->_col = RED;
					}
					else
					{
						//    g
						//  p
						//    c

						RotateL(parent);
						RotateR(gradeparent);
						cur->_col = BLACK;
						gradeparent->_col = RED;
					}

					break;
				}
				
			}
			else
			{
				Node* uncle = gradeparent->_left;

				//叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					//变色+向上调整
					uncle->_col = parent->_col = BLACK;
					gradeparent->_col = RED;

					cur = gradeparent;
					parent = cur->_parent;
				}
				//叔叔不存在 or 叔叔存在且为黑
				else
				{
					//旋转+变色
					if (cur == parent->_right)
					{
						//g
						//  p
						//    c

						RotateL(gradeparent);

						parent->_col = BLACK;
						gradeparent->_col = RED;
					}
					else
					{
						//g
						//  p
						//c

						RotateR(parent);
						RotateL(gradeparent);

						cur->_col = BLACK;
						gradeparent->_col = RED;
					}

					break;
				}

			}
		}
		_root->_col = BLACK;
		return true;
	}

	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;

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

	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 (ppNode == nullptr)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = cur;
			}
			else
			{
				ppNode->_right = cur;
			}
			cur->_parent = ppNode;
		}
	}

	bool CheckColour(Node* root, int blacknum, int benchmark)
	{
		if (root == nullptr)
		{
			if (blacknum != benchmark)
				return false;

			return true;
		}

		if (root->_col == BLACK)
		{
			++blacknum;
		}

		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "出现连续红色节点" << endl;
			return false;
		}

		return CheckColour(root->_left, blacknum, benchmark)
			&& CheckColour(root->_right, blacknum, benchmark);
	}

	bool IsBalance()
	{
		return IsBalance(_root);
	}

	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);
	}

private:
	Node* _root = nullptr;
};

#include"RBTree.h"

int main()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.insert(make_pair(e, e));
		cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}

	return 0;
}