一、红黑树的概念

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

ps:树的路径是从根节点走到空节点（此处为NIL 节点）才算一条路径

二、红黑树的性质

• 每个结点不是红色就是黑色

• 根结点是黑色的

• 如果一个结点是红色的，则它的两个孩子结点是黑色的（没有连续的红色结点）

• 对于每个结点，从该节点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

• 每个叶子结点都是黑色的（此处的叶子结点指的是空节点,NIL节点），如果是空树，空节点也是黑色，符合第一个性质

理解最长路径长度不超过最短路径长度的 2 倍：

根据第三个性质：红黑树不会出现连续的红色结点，根据第四个性质：从每个结点到所有后代结点的路径上包含相同数目的黑色结点。

极端场景：最短路径上全黑，一条路径黑色节点的数量，最长路径上是一黑一红相间的路径

---

三、红黑树节点的定义

三叉链结构，对比AVL数节点的定义，把平衡因子替换成节点颜色，采用枚举的方式：

//结点颜色
enum Color
{
	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;

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

这里可以清楚的看到，构造结点时默认设置为红色,问题来了：

如果插入的是黑色结点那就是不符合第四个性质（路径上均包含相同的黑色结点），此时我们必须要去进行维护每条路径的黑色结点

如果插入的是红色结点那就是不符合第三个性质（没有出现连续的红色结点），但是我们并不一定需要调整，如果根刚好为黑色，就不需要进行调整。

所以如果插入为红色结点，不一定会破坏结构，但是如果插入黑色结点我们就必须去进行维护了

---

四、红黑树的插入

红黑树插入的操作部分和AVL树的插入一样：

• 找到待插入位置
• 将待插入结点插入到树中
• 调整：若插入结点的父结点是红色的，我们就需要对红黑树进行调整

前两步大差不差

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论

关键在于对红黑树进行调整：为了能够展示出各种情况，这里有一个基本的模型：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一：cur为红，p为红，g为黑，u存在且为红 :

cur为红，p为红，g为黑，u存在且为红

关键看u结点，根结点的颜色为黑色，不能有连续的红色结点，所以上面的情况已经出现连续的红色结点了，此时我们需要进行调整：

把p结点改为黑色，同时把u结点也改为黑色（符合性质四：每条路径上的黑色节点数量相同），最后在把g结点改为红色；如果g是子树的话，g一定会有双亲，为了维持每条路径上黑色节点的数量，g必须变红，不然会多出一个黑色节点，在把g结点当做cur结点继续往上调整，当g为根结点时，在把g置为黑色：

代码实现：

      while (parent && parent->_col == RED)
		{
			Node* grandfater = parent->_parent;
			if (parent == grandfater->_left)
			{
				Node* uncle = grandfater->_right;
				//情况一：u存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfater->_col = RED;

					cur = grandfater;
					parent = cur->_parent;
				}
				else//其他情况
				{
				}
			}
			else//parent==grandfater->_right
			{
				Node* uncle = grandfater->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfater->_col = RED;

					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
				}

			}
		}
		_root->_col = BLACK;

情况二：cur为红，p为红，g为黑，u不存在/u为黑，gpc在同一侧：

此时u的情况：

如果u结点不存在，则cur一定是新增结点，因为如果cur不是新增结点：则cur和p一定有一个节点时黑色，就不满足每条路径都有相同的黑色结点的性质。

如果u结点存在，则其一定是黑色的，那么c节点原来的颜色一定是黑色，在其子树调整过程中变为了红色

如果p为g的左孩子，cur为p的左孩子，则进行右单旋转；

如果p为g的右孩子，cur为p的右孩子，则进行左单旋转，

同时，p、g变色–p变黑，g变红

以下情况：u不存在，cur为新增节点，进行右单旋：

以下情况：u结点存在且为黑：

情况三: cur为红，p为红，g为黑，u不存在/u为黑，gpc不在同一侧:

这时候我们就需要进行双旋了：

p为g的左孩子，cur为p的右孩子，对p做左单旋转；
p为g的右孩子，cur为p的左孩子，对p做右单旋转;
旋转之后则转换成了情况2，在继续进行调整即可

---

五、代码实现

送上源码：

#pragma once
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;
enum Color
{
	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;

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

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* 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;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		while (parent && parent->_col == RED)
		{
			Node* grandfater = parent->_parent;
			if (parent == grandfater->_left)
			{
				Node* uncle = grandfater->_right;
				//情况一：u存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfater->_col = RED;
					//向上调整
					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					//情况2
					if (cur == parent->_left)
					{
						RotateR(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					//情况3
					else
					{
						//       g
						//  p
						//    c 
						RotateL(parent);
						RotateR(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
			else//parent==grandfater->_right
			{
				Node* uncle = grandfater->_left;
				//情况1：u存在且为红色
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfater->_col = RED;
					//向上调整
					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					//情况2：u不存在/u存在为黑色
					//g
					//    p
					//        c
					if (cur == parent->_right)
					{
						RotateL(grandfater);
						grandfater->_col = RED;
						parent->_col = BLACK;
					}
					//情况3
					//     g
					 //         p
					 //      c
					else
					{
						RotateR(parent);
						RotateL(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					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;
		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (ppNode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subL;
		subL->_right = parent;
		if (ppNode == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}


	void InOrder()
	{
		_InOrder(_root);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}


	bool Check(Node*root,int blackNum,int ref)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			if (blackNum != ref)
			{
				cout << "违反规则：本条路径的黑色结点的数量根最左路径不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "违反规则：出现连续的红色结点" << endl;
			return false;
		}
		if (root->_col == BLACK)
		{
			++blackNum;
		}
		return Check(root->_left,blackNum,ref)
			&& Check(root->_right,blackNum,ref);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col != BLACK)
		{
			return false;
		}
		int ref = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
			{
				++ref;
			}
			left = left->_left;
		}
		return Check(_root,0,ref);
	}
private:
	Node* _root = nullptr;
};


void TestRBTree1()
{
	//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	//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));
	}
	t.InOrder();
	cout << t.IsBalance() << endl;
}


void TestRBTree2()
{
	srand(time(0));
	const size_t N = 100000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; i++)
	{
		size_t x = rand();
		t.Insert(make_pair(x, x));
	}
	cout << t.IsBalance() << endl;

}

---

本篇结束…