一.红黑树

1.概念

2.性质

二.分部实现红黑树

1.树节点

2.红黑树成员

3.插入（重点）

情况一：叔叔节点存在且为红。

情况二：叔叔不存在 or 叔叔存在且为黑

① 单旋情况

② 双旋情况

注意：

4.判断该树是否为红黑树

三.红黑树实现代码

AVLTree-》深入理解AVLTree【旋转控制平衡（单旋、双旋）】_糖果雨滴a的博客-CSDN博客

使用红黑树封装实现的map和set：C++ 关联式容器map+set_糖果雨滴a的博客-CSDN博客

前言：在学习红黑树之前，我们最好先学习一下AVLTree，并且这两个平衡二叉搜索树的难度差不多，学过了AVLTree之后，红黑树就会更加轻松一些。红黑树只是比较抽象一些，在调整方面较AVLTree要简单一些。

一.红黑树

1.概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储为表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其它路径长两倍以上，因而是接近平衡的。

2.性质
① 每个结点不是红色就是黑色

② 根节点是黑色的

③ 如果一个结点是红色的，则它的两个孩子结点是黑色的

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

⑤ 每个叶子结点都是黑色的（此处的叶子结点指的是空结点）

二.分部实现红黑树

1.树节点

实现一个含义3叉链的二叉树，并且包括pair类型的kv，以及枚举RED, BLACK颜色控制。

enum Color
{
	RED,
	BLACK,
};

template
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	pair _kv;

	Color _col;

	RBTreeNode(const pair& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

2.红黑树成员

template
class RBTree
{
	typedef RBTreeNode Node;
private:
	Node* _root = nullptr;
}

3.插入（重点）

先简单看一下插入的代码：

bool Insert(const pair& kv)
{
	// 1.搜索树的规则插入
	// 2.看是否违反平衡规则，如果违反就需要处理：旋转
	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;
	}
	else
	{
		parent->_left = cur;
	}

	cur->_parent = parent;

	// 存在连续红色节点
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;
		assert(grandfather);

		if (grandfather->_left == parent)
		{
			Node* uncle = grandfather->_right;
			// 情况一：叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			// 叔叔不存在 or 叔叔存在且为黑
			else
			{
				// 情况二：单旋(右单旋)
				if (cur == parent->_left)
				{
					//     g
					//   p
					// c
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				// 情况三：双旋(左右双旋)
				else
				{
					//     g
					//   p
					//     c
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;

			}
		}
		// grandfather->_right == parent
		else
		{
			Node* uncle = grandfather->_left;
			// 情况一：叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			// 叔叔不存在 or 叔叔存在且为黑
			else
			{
				// 情况二：单旋(左单旋)
				if (cur == parent->_right)
				{
					// g
					//   p
					//     c 
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				// 情况三：双旋(右左双旋)
				else
				{
					// g
					//   p
					// c
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
	}

	_root->_col = BLACK;

	return true;
}

前面就是正常的找到插入的位置，然后插入节点。

这里我们默认插入的节点的颜色是红色，如果默认是黑色就一定违反规则四，而是红色就只是可能会违反规则三，相比较而言，插入节点颜色为红色的影响较小。

接下来就是红黑树的重点部分：①符合红黑树规则 ②保证该搜索二叉树相对平衡。

因为我们插入的节点是红色，那么只有出现连续的红色节点（即插入节点为红色，其父节点也为红色时）才需要进行调整。而具体情况主要与叔叔节点有关。

这里我们先定义一个祖父节点grandfather，因为出现这种情况时父节点为红色，而如果没有grandfather，就一定违反规则二（根节点为黑色），因此grandfather一定存在，为了防止出现问题，这里我们assert一下。

接下来就需要分情况了，首先是parent在祖父节点的左还是右需要分情况，因为左和右的不同，我们在后面进行旋转控制平衡时的旋转方向是不同的，因此要区分开来。

这里我们以parent在grandfather的左为例，首先定义一个叔叔节点（grandfather的另一个孩子节点），这个叔叔节点是红黑树的关键。我们要以叔叔进行分情况。

情况一：叔叔节点存在且为红。

这种情况我们只需要变色处理，但是在变色处理后，可能导致上面的节点也出现此情况，因此要继续向上处理。

处理方式：变色处理。

操作：将parent和uncle的颜色改为BLACK，让grandfather的颜色改为RED。（这里我们不讨论grandfather是根节点的情况，我们在最后强制让root节点变为黑色）

我们处理的原则是尽量保证原来的黑色节点的数量不变进行插入，因此按上述改颜色后黑色节点的数量是不会发生变化的。

下面我们看图实现：

g为grandfather，p为parent，u为uncle。

代码实现：

// 情况一：叔叔存在且为红
if (uncle && uncle->_col == RED)
{
	// 变色
	parent->_col = uncle->_col = BLACK;
	grandfather->_col = RED;

	// 继续往上处理
	cur = grandfather;
	parent = cur->_parent;
}

情况二：叔叔不存在 or 叔叔存在且为黑
情况二要再次进行划分，可以再分为两种情况，一种是进行单旋，另一种是进行双旋。

① 单旋情况

grandfather，parent，cur在一条线上时发生单旋，这里我们是以parent在grandfather的左为例，因此这里cur是parent的左节点。

处理方式：右单旋+变色处理

操作：首先是右单旋，这里在AVLTree中进行了详细解释，然后再把parent的颜色变为BLACK，grandfather的颜色变为RED。

代码实现：

// 情况二：单旋(右单旋)
if (cur == parent->_left)
{
	//     g
	//   p
	// c
	RotateR(grandfather);
	parent->_col = BLACK;
	grandfather->_col = RED;
}

② 双旋情况

grandfather，parent，cur不在一条线上是发生双旋，这种情况说明cur是parent的右节点。

处理方式：左右双旋+变色处理

操作：先左单旋后右双旋，然后把cur的颜色变为BLACK，grangfather的颜色变为RED

代码实现：

// 情况三：双旋(左右双旋)
else
{
	//     g
	//   p
	//     c
	RotateL(parent);
	RotateR(grandfather);
	cur->_col = BLACK;
	grandfather->_col = RED;
}

注意：
上面我们是以parent在grandfather的左为例，如果parent在grandfather的右，那么情况一是相同的，而情况二中的单旋和双旋分别从右单旋变为左单旋，从左右双旋变为右左双旋。而变色处理是相同的。

4.判断该树是否为红黑树

要想判断该树是否为红黑树，就要依次去判断该树是否满足这5个规则，同时也要满足没有一条路径会比其它路径长两倍以上。

bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
{
	// 走到null之后，判断k和black是否相等
	if (nullptr == pRoot)
	{
		if (k != blackCount)
		{
			cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
			return false;
		}
			
		return true;
	}

	// 统计黑色节点的个数
	if (BLACK == pRoot->_col)
	{
		k++; 
	}

	// 检测当前节点与其双亲是否都为红色
	if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
	{
		cout << "违反性质三：存在连在一起的红色节点" << endl;
		return false;
	}

	return _IsValidRBTree(pRoot->_left, k, blackCount) &&
		_IsValidRBTree(pRoot->_right, k, blackCount);
}

bool IsBalanceTree()
{
	// 检查红黑树几条规则
	Node* pRoot = _root;
	// 空树也是红黑树
	if (nullptr == pRoot)
		return true;

	// 检测根节点是否满足情况
	if (BLACK != pRoot->_col)
	{
		cout << "违反红黑树性质二：根节点必须为黑色" << endl;
		return false;
	}

	// 获取任意一条路径中黑色节点的个数 -- 比较基准值
	size_t blackCount = 0;
	Node* pCur = pRoot;
	while (pCur)
	{
		if (BLACK == pCur->_col)
			blackCount++;

		pCur = pCur->_left;
	}

	// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
	size_t k = 0;
	return _IsValidRBTree(pRoot, k, blackCount);
}

三.红黑树实现代码

#pragma once

#include 

enum Color
{
	RED,
	BLACK,
};

template
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	pair _kv;

	Color _col;

	RBTreeNode(const pair& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

template
class RBTree
{
	typedef RBTreeNode Node;
public:
	bool Insert(const pair& kv)
	{
		// 1.搜索树的规则插入
		// 2.看是否违反平衡规则，如果违反就需要处理：旋转
		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;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		// 存在连续红色节点
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			assert(grandfather);

			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				// 情况一：叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				// 叔叔不存在 or 叔叔存在且为黑
				else
				{
					// 情况二：单旋(右单旋)
					if (cur == parent->_left)
					{
						//     g
						//   p
						// c
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					// 情况三：双旋(左右双旋)
					else
					{
						//     g
						//   p
						//     c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;

				}
			}
			// grandfather->_right == parent
			else
			{
				Node* uncle = grandfather->_left;
				// 情况一：叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				// 叔叔不存在 or 叔叔存在且为黑
				else
				{
					// 情况二：单旋(左单旋)
					if (cur == parent->_right)
					{
						// g
						//   p
						//     c 
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					// 情况三：双旋(右左双旋)
					else
					{
						// g
						//   p
						// c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;

		return true;
	}

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

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

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

	}

	bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
	{
		// 走到null之后，判断k和black是否相等
		if (nullptr == pRoot)
		{
			if (k != blackCount)
			{
				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
				return false;
			}
			
			return true;
		}

		// 统计黑色节点的个数
		if (BLACK == pRoot->_col)
		{
			k++; 
		}

		// 检测当前节点与其双亲是否都为红色
		if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
		{
			cout << "违反性质三：存在连在一起的红色节点" << endl;
			return false;
		}

		return _IsValidRBTree(pRoot->_left, k, blackCount) &&
			_IsValidRBTree(pRoot->_right, k, blackCount);
	}

public:
	bool IsBalanceTree()
	{
		// 检查红黑树几条规则
		Node* pRoot = _root;
		// 空树也是红黑树
		if (nullptr == pRoot)
			return true;

		// 检测根节点是否满足情况
		if (BLACK != pRoot->_col)
		{
			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
			return false;
		}

		// 获取任意一条路径中黑色节点的个数 -- 比较基准值
		size_t blackCount = 0;
		Node* pCur = pRoot;
		while (pCur)
		{
			if (BLACK == pCur->_col)
				blackCount++;

			pCur = pCur->_left;
		}

		// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
		size_t k = 0;
		return _IsValidRBTree(pRoot, k, blackCount);
	}
private:
	Node* _root = nullptr;
};

深入理解红黑树【满足红黑树5条规则】

一.红黑树

二.分部实现红黑树

2.红黑树成员
template class RBTree { typedef RBTreeNode Node; private: Node* _root = nullptr; }

情况二：叔叔不存在 or 叔叔存在且为黑
情况二要再次进行划分，可以再分为两种情况，一种是进行单旋，另一种是进行双旋。

注意：
上面我们是以parent在grandfather的左为例，如果parent在grandfather的右，那么情况一是相同的，而情况二中的单旋和双旋分别从右单旋变为左单旋，从左右双旋变为右左双旋。而变色处理是相同的。

Java相关栏目本月热门文章

深入理解 红黑树【满足红黑树5条规则】

一.红黑树

二.分部实现红黑树

2.红黑树成员 template class RBTree { typedef RBTreeNode Node; private: Node* _root = nullptr; }

情况二：叔叔不存在 or 叔叔存在且为黑 情况二要再次进行划分，可以再分为两种情况，一种是进行单旋，另一种是进行双旋。

注意： 上面我们是以parent在grandfather的左为例，如果parent在grandfather的右，那么情况一是相同的，而情况二中的单旋和双旋分别从右单旋变为左单旋，从左右双旋变为右左双旋。而变色处理是相同的。

Java相关栏目本月热门文章

深入理解红黑树【满足红黑树5条规则】

2.红黑树成员
template class RBTree { typedef RBTreeNode Node; private: Node* _root = nullptr; }

情况二：叔叔不存在 or 叔叔存在且为黑
情况二要再次进行划分，可以再分为两种情况，一种是进行单旋，另一种是进行双旋。

注意：
上面我们是以parent在grandfather的左为例，如果parent在grandfather的右，那么情况一是相同的，而情况二中的单旋和双旋分别从右单旋变为左单旋，从左右双旋变为右左双旋。而变色处理是相同的。