初夏小谈：红黑树原理及实现

一、红黑树的概念及产生原因：

红黑树就是一棵二叉搜索树，只不过在里面添加了一些特性，它的结点不是红的就是黑的。

红黑树（本质二叉搜索树）是在基于二叉搜索树，为了改善在极端情况下，二叉搜索树的查找不佳的情况。（比如，每个结点只有左孩子/每个结点只有有孩子的情况等等）。二叉搜索树的查找次数就是二叉树的高度。平均查找时间复杂度（O（logn)）,最差时间复杂度（O（n））

为了解决在极端情况下二叉搜索树的查找不佳的情况，红黑树较好的解决了这种情况。关联式容器map底层就是红黑树实现的，另外，哈希时哈希桶也会挂红黑树。

二、红黑树的性质：

1.红黑树中这样规定：

红黑树中每个结点不是红的就是黑的
红黑树的根节点一定是黑的。
红黑树中如果有一个结点是红的，则它如果有孩子则它的孩子都是黑的。（这说明在红黑树中红色结点不可能连续）
红黑树中从任意结点出发，以该节点为基础，所有分支上的黑色节点数量都相同。
所有叶子结点就是黑的（此时说的叶子结点是NULL结点）

2.从红黑树的性质中可以不难得到这样的结论：

红黑树中：根节点一定是黑的，红结点不会连续，并且以任意节点出发的所有分支上黑色结点数量相同。

从上述性质中可以看出：红黑树中最长路径不会超过最短路径的两倍。这是因为，在最长时理想情况是以黑色结点为根，之后最长路径上每两个黑色结点中间都会有一个红色结点，最后以红色结点终止。由性质4可以发现，最短路径上至少包含的黑色结点的数量一定和最长路径上的黑色结点数量相同。而最长路径上所有结点数量至多是黑色结点数量的2倍。所以以此证明。

三、红黑树中需要调整的三种情况

所谓需要调整的情况就是当前的树不满足红黑树的性质的情况。

1.第一种就是开始插入时会遇到的情况及当遇到连续的红色结点时，此时就需要调整。

调整方法：将新插入结点S4的爸爸和叔叔进行变黑处理。要保证每条路径上黑节点个数相同所以要将S1结点变红，当S1是根节点时，再变黑。

当然如果S4是S2的右孩子也是一样的调整方法。

第二种：可能在调整的过程中会再次遇到的情况：红的再次连续。分为两种情况

当S3存在时就是调整之后发生的，当S3不存在时就是插入时遇到的调整。

情况一：红结点的左孩子是红结点：

调整方法：对S1进行右单旋，使得S2称为S1的爸爸。S1变为S2的右孩子。并且将S2的颜色置黑，S1颜色置红。

情况三：红结点的右孩子是红节点。

调整方法：将S2向左旋后变为情况2进行右单旋

这是在左子树的情况，右子树则与此对称相反。

四、代码实现：

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

enum Color{RED, BLACK};

template<class T>
struct RBTreeNode
{
	RBTreeNode(const T& data = T(), const Color color = RED)
		:_Left(nullptr)
		,_Right(nullptr)
		,_Parent(nullptr)
		,_data(data)
		,_Color(color)
	{}
	RBTreeNode<T>* _Left;
	RBTreeNode<T>* _Right;
	RBTreeNode<T>* _Parent;
	T _data;
	Color _Color;
};

template<class T>
class RBTree
{
	typedef RBTreeNode<T> RBTreeNode;
public:
	RBTree()
	{
		_Head = new RBTreeNode;
		_Head->_Left = _Head;
		_Head->_Right = _Head;
		_Head->_Parent = nullptr;
	}

	~RBTree()
	{
		_Destroy(GetRoot());
	}
	bool Insert(const T& data)
	{
		RBTreeNode*& Root = GetRoot();
		if (Root == nullptr)
		{
			Root = new RBTreeNode(data, BLACK);
			Root->_Parent = _Head;
		}
		else
		{
			//按照二叉搜索树性质插入
			//1.找位置
			RBTreeNode* ptr = Root;
			RBTreeNode* Parent = nullptr;
			while (ptr)
			{
				Parent = ptr;
				if (ptr->_data > data)
				{
					ptr = ptr->_Left;
				}
				else if (ptr->_data < data)
				{
					ptr = ptr->_Right;
				}
				else
				{
					return false;
				}
			}

			//2.插入新节点
			ptr = new RBTreeNode(data);
			if (Parent->_data > data)
			{
				Parent->_Left = ptr;
			}
			else
			{
				Parent->_Right = ptr;
			}
			ptr->_Parent = Parent;
			//3.更新节点颜色
			while (Parent != _Head && RED == Parent->_Color)
			{
				RBTreeNode* GrandFather = Parent->_Parent;
				if (Parent == GrandFather->_Left)
				{
					RBTreeNode* Uncle = GrandFather->_Right;
					//叔叔结点存在且为红（情况一）
					if (Uncle && Uncle->_Color == RED)
					{
						Parent->_Color = BLACK;
						Uncle->_Color = BLACK;
						GrandFather->_Color = RED;

						ptr = GrandFather;
						Parent = ptr->_Parent;
					}
					else
					{
						//先处理情况三为情况二
						if (ptr == Parent->_Right)
						{
							RotateL(Parent);
							swap(ptr, Parent);
						}

						//情况二
						Parent->_Color = BLACK;
						GrandFather->_Color = RED;
						RotateR(GrandFather);
					}
				}
				else
				{
					RBTreeNode* Uncle = GrandFather->_Left;
					if (Uncle && Uncle->_Color == RED)
					{
						Parent->_Color = BLACK;
						Uncle->_Color = BLACK;
						GrandFather->_Color = RED;

						ptr = GrandFather;
						Parent = ptr->_Parent;
					}
					else
					{
						if (ptr == Parent->_Left)
						{
							RotateR(Parent);
							swap(ptr, Parent);
						}

						Parent->_Color = BLACK;
						GrandFather->_Color = RED;
						RotateL(GrandFather);
					}
				}

			}
		}

		Root->_Color = BLACK;
		//更新头结点指向的最大最小节点
		_Head->_Left = LeftMost();
		_Head->_Right = RightMost();
		return true;
	}

	void InOrderPrint()
	{
		_InOrderPrint(GetRoot());
		cout << endl;
	}
private:
	RBTreeNode*& GetRoot()
	{
		return _Head->_Parent;
	}
	void _InOrderPrint(RBTreeNode* Root)
	{
		if (Root)
		{
			_InOrderPrint(Root->_Left);
			cout << Root->_data << " ";
			_InOrderPrint(Root->_Right);
		}
	}

	void _Destroy(RBTreeNode*& Root)
	{
		if (Root)
		{
			_Destroy(Root->_Left);
			_Destroy(Root->_Right);
			delete Root;
			Root = nullptr;
		}
	}
	RBTreeNode* LeftMost()
	{
		RBTreeNode* ptr = GetRoot();
		if (ptr == nullptr)
		{
			return _Head;
		}
		while (ptr)
		{
			if (ptr->_Left != nullptr)
			{
				ptr = ptr->_Left;
			}
			else
			{
				break;
			}
		}
		return ptr;
	}

	RBTreeNode* RightMost()
	{
		RBTreeNode* ptr = GetRoot();
		if (ptr == nullptr)
		{
			return _Head;
		}
		while (ptr)
		{
			if (ptr->_Right != nullptr)
			{
				ptr = ptr->_Right;
			}
			else
			{
				break;
			}
		}
		return ptr;
	}

	void RotateL(RBTreeNode* Parent)
	{
		RBTreeNode* SubR = Parent->_Right;
		RBTreeNode* SubRL = SubR->_Left;

		Parent->_Right = SubRL;
		if (SubRL)
		{
			SubRL->_Parent = Parent;
		}

		SubR->_Left = Parent;

		RBTreeNode* PParent = Parent->_Parent;
		Parent->_Parent = SubR;
		SubR->_Parent = PParent;

		RBTreeNode*& Root = GetRoot();
		if (Root == Parent)
		{
			Root = SubR;
		}
		else
		{
			if (PParent->_Left == Parent)
			{
				PParent->_Left = SubR;
			}
			else
			{
				PParent->_Right = SubR;
			}
		}
	}

	void RotateR(RBTreeNode* Parent)
	{
		RBTreeNode* SubL = Parent->_Left;
		RBTreeNode* SubLR = SubL->_Right;

		Parent->_Left = SubLR;
		if (SubLR)
		{
			SubLR->_Parent = Parent;
		}

		SubL->_Right = Parent;
		RBTreeNode* PParent = Parent->_Parent;
		SubL->_Parent = PParent;

		RBTreeNode*& Root = GetRoot();
		if (Parent == Root)
		{
			Root = SubL;
		}
		else
		{
			if (PParent->_Left == Parent)
			{
				PParent->_Left = SubL;
			}
			else
			{
				PParent->_Right = SubL;
			}
		}
	}
private:
	RBTreeNode* _Head;
};

测试用例：

4,2,6,1,3,5,15,7,16,14

图解插入过程：插入过程中默认颜色为红色，没有说明则为正常插入。

在插入1时遇到情况一，所以将2变黑，6变黑。

在插入7时遇到情况一，所以将5变黑，15变黑，6不是根节点，所以变红。

在插入14时便到下图：

插入结点14所遇到的情况也是情况一。所以直接进行调整：将14的爸爸7和叔叔16变黑。15不是根节点变红。

此时便遇到了情况二如下图：

此时按照情况二处理：把6往上提成为根节点，4变为6的左孩子，6原来的左孩子5变为4的右孩子。并且将6的颜色置黑。4的颜色置红。如下图：

此时已满足红黑树的性质便不再调整。

代码测试：

#include"RBTree.hpp"

void TestRBTree()
{
	int a[] = { 4,2,6,1,3,5,15,7,16,14 };
	RBTree<int> t;
	for (auto e : a)
	{
		t.Insert(e);
	}

	t.InOrderPrint();
}

int main()
{
	TestRBTree();
	system("pause");
	return 0;
}

运行结果：中序遍历打印：