数据结构进阶—红黑树

• 1、R-B Tree的概念
• 2、红黑树的性质
• • 2.1 红黑树性质分析
• 3、红黑树的插入
• • 3.1 情况1
  • 3.2 情况2
  • 3.3 情况3
  • 3.4 情况4
  • 3.5 情况5
• 4、树的旋转
• • 4.1 左单旋
  • 4.2 右单旋
  • 4.3 左右单旋和右左单旋
• 5、旋转总结
• 6、整体代码

红黑树(R-B Tree)，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。AVL树是高度平衡的。C++ STL中，很多部分(包括set, multiset, map, multimap)的底层都是红黑树。对于任意一棵红黑树，它可以在O( l o g 2 N log_2N log2​N)时间内做查找，插入和删除，这里的N是树中元素的数目。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树还增加了如下的额外要求：

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点(NIL))
4. 如果一个节点是红色的，则它的两个孩子结点是黑色的
5. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

性质1和性质2：这个很好理解，红黑树嘛，结点不是红色就是黑色，至于为什么根结点是黑色的，因为这也是规定。
性质3：这里的叶子结点不是我们平常认知的叶子结点(没有子结点的结点)，而是NIL(可以认为是nullptr)
性质4：在一棵红黑树中，不可能存在连续的两个红结点(就是父结点是红色的并且子结点也是红色的)
性质5：在上图中，例如黑结点13到黑结点1左边的NUL，有2个黑结点，到黑结点11的左右两边也有2个黑结点。对于红结点17到红结点22左右两边和到27的左右两边的黑结点数也是相同的，都为2。

因为上图满足这5点性质，所以该树是一棵红黑树

在R-B Tree的概念中提到红黑树是接近平衡的，因为红黑树确保没有一条路径会比其他路径长出俩倍。为什么是这样呢？
由于每个结点非红即黑(性质1)，加上不存在两个连续的红结点(性质4)，那么红黑树的最长路径一定是红黑交替的，而最短路径一定全都是黑结点。而任意结点其所有后代叶结点的简单路径上，均包含相同数目的黑色结点，则说明最长路径和最短路径中的黑色结点数目一定相等。最后加上根节点为黑(性质2)和叶子结点为黑(性质3)，那么一定可以得到一个结论：最长路径<=2*最短路径

最长路径 = 最短路径

最长路径 = 2*最短路径

当我们在对红黑树进行插入操作时，对树做了修改，那么可能会违背红黑树的性质。为了保持红黑树的性质，我们可以通过对树进行旋转，即修改树种某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质(五点性质)。
红黑树的插入分为5种情况，在了解之前，我们还要必须知道插入的结点是红色的，如果插入结点为黑色，总是会破坏性质5，而插入红结点不一定会破坏性质5。因为在插入之前，该树已经是红黑树，插入了黑结点肯定会影响该结点到根结点的这条路径。比如：在上图中黑结点11的左边插入黑结点，除了这条路径的黑结点数为4之外，其他的都为3。那为什么插入红色结点不一定会破坏性质5呢？假如还是在上图中黑结点11的左边插入红结点，在插入之后，每条路径的黑结点还是3。
除此之外，我们将需要插入的结点标为N，父结点为P，祖父结点为G，叔结点为U(父亲的亲兄弟)。下面将逐一介绍这5种情况：

该树为空树，直接插入根结点的位置，违反性质1，把节点颜色有红改为黑即可

插入节点N的父节点P为黑色，不违反任何性质，无需做任何修改

N为红，P为红，（祖节点一定存在，且为黑，下边同理）U也为红，这里不论P是G的左孩子，还是右孩子；不论N是P的左孩子，还是右孩子
为什么在这个情况下，祖父结点一定存在？因为P结点为红，假设祖父结点不存在，那么P将成为整颗树的根，但P为红色，已经违反了性质2(根结点为黑色)

在此情况下，只需要将P和U变色即可

N为红，P为红，U为黑(存在为黑或者不存在)，P为G的左孩子，N为P的左孩子(或者P为G的右孩子，N为P的左孩子；反正就是同向的)
在此情况下，需要将P、G变色，P、G变换即左单旋(或者右单旋)

此处为左单旋，右单旋为相反操作

N为红，P为红，U为黑(存在为黑或者不存在)，P为G的左孩子，N为P的右孩子(或者P为G的右孩子，N为P的左孩子；反正两方向相反)

在此情况下，需要进行两次旋旋转，P、N右单旋，G、N左单旋
此处为右左单旋，左右单旋为相反操作

红黑树的旋转和AVL树的旋转一样，只是红黑树没有平衡因子，不需要控制平衡因子

void RotateL(Node* parent)
{
	Node* subR = parent->_right;//parent的的右边一定不为nullptr
	Node* subRL = subR->_left;//subR的左边可能为nullptr
	Node* pparent = parent->_parent;//保存parent的根(父节点)

	//将subRL链接到parent的右侧
	parent->_right = subRL;
	if (subRL != nullptr)
		subRL->_parent = parent;

	//将parent链接到subR左侧
	subR->_left = parent;
	parent->_parent = subR;

	//将subR和pparent链接起来
	//pparent为nullptr，subR要成为新的根
	if (pparent == nullptr)//_parent == _root
	{
		subR->_parent = pparent;
		_root = subR;
	}
	//pparent不为nullptr，就链接pparent和subR
	else
	{
		if (pparent->_right == parent)
			pparent->_right = subR;
		else
			pparent->_left = subR;
		subR->_parent = pparent;
	}
}

void RotateR(Node* parent)
{
	Node* subL = parent->_left;//parent的的左边一定不为nullptr
	Node* subLR = subL->_right;//subL的右边可能为nullptr
	Node* pparent = parent->_parent;//保存parent的根(父节点)

	//将subLR链接到parent的左侧
	parent->_left = subLR;
	if (subLR != nullptr)
		subLR->_parent = parent;

	//将parent链接到subL右侧
	subL->_right = parent;
	parent->_parent = subL;

	//将subL和pparent链接起来
	//pparent为nullptr，subL要成为新的根
	if (pparent == nullptr)
	{
		subL->_parent = pparent;
		_root = subL;
	}
	//pparent不为nullptr，就链接pparent和subL
	else
	{
		if (pparent->_left == parent)
			pparent->_left = subL;
		else
			pparent->_right = subL;
		subL->_parent = pparent;
	}
}

//右旋左旋
void RotateRL(Node* parent)
{
	RotateR(parent->_right);
	RotateL(parent);
}

//左旋右旋
void RotateLR(Node* parent)
{
	RotateL(parent->_left);
	RotateR(parent);
}

1. 父亲节点是·黑色，插入的节点为红色，不需要进行操作。
2. 父亲节点和叔叔节点是红色，插入一个红色的节点后，父亲节点和叔叔节点变为黑色，祖父节点变为红色
3. 父亲节点是红色、叔叔节点不存在或者存在且为黑色：
   1.parent在grandfather左侧：
   cur在parent左侧 -> 以祖父为中心，进行右旋，并且祖父变为红色，父亲变为黑色 (右旋)
   cur在parent右侧 -> 先以父亲为中心进行左旋，再以祖父为中心进行右旋 (左右双旋)
   2.parent在grandfather右侧：
   cur在parent右侧 -> 以祖父为中心，进行左旋,并且祖父变为红色，父亲变为黑色 (左旋)
   cur在parent左侧 -> 先以父亲为中心进行右旋，再以祖父为中心进行左旋 (右左双旋)

#pragma once

#include
using namespace std;

enum Color
{
	RED,
	BLACK
};

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

	pair _kv;
	Color _cor;

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

template
class RBTree
{
	typedef RBTreeNode Node;

public:
	RBTree()
		:_root(nullptr)
	{}
	
	bool Insert(const pair& kv)
	{
		//_root为nullptr，说明是插入的第一个值
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_cor = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			//插入的值比cur大，说明要在右边插入
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			//插入的值比cur小，说明要在左边插入
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
				return false;
		}

		//链接父子结点
		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		//控制平衡
		while (parent != nullptr && parent->_cor == RED)
		{
			//不需要判断grandfather是否为nullptr，因为parent如果是红色，不可能是根
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//情况1、uncle存在且为红，不需要旋转处理
				if (uncle != nullptr && uncle->_cor == RED)
				{
					//变色+向上继续调整
					parent->_cor = uncle->_cor = BLACK;
					grandfather->_cor = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				//情况2、uncle存在且为黑/不存在
				else
				{
					//cur为parent的左孩子，需要进右单旋
					//       g      p(黑)
					//     p     c    g(红)
					//   c
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_cor = BLACK;
						grandfather->_cor = RED;
					}
					//cur为parent的右孩子，需要左右双旋(先左旋，再右旋)
					//      g            c(黑)
					//   p(红)         p   g(红)
					//      c(红)
					else
					{
						RotateLR(grandfather);
						//RorateL(parent);
						//RorateR(grandfather);
						cur->_cor = BLACK;
						grandfather->_cor = RED;
					}
					break;
				}
			}
			//parent为grandfather的右孩子，和parent为grandfather的左孩子的情况一样，只是方向不同
			else
			{
				Node* uncle = grandfather->_left;
				//情况1、uncle存在且为红，不需要旋转处理
				if (uncle != nullptr && uncle->_cor == RED)
				{
					//变色+向上继续调整
					parent->_cor = uncle->_cor = BLACK;
					grandfather->_cor = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				//情况2、uncle存在且为黑/不存在
				else
				{
					//cur为parent的右孩子，需要进左单旋
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_cor = BLACK;
						grandfather->_cor = RED;
					}
					//cur为parent的左孩子，需要进右左单旋
					else
					{
						RotateRL(grandfather);
						//RorateR(parent);
						//RorateL(grandfather);
						cur->_cor = BLACK;
						grandfather->_cor = RED;
					}
					break;
				}
			}
		}
		//让根变黑
		_root->_cor = BLACK;
		return true;
	}


private:
	Node* _root;

	//右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;//parent的的左边一定不为nullptr
		Node* subLR = subL->_right;//subL的右边可能为nullptr
		Node* pparent = parent->_parent;//保存parent的根(父节点)

		//将subLR链接到parent的左侧
		parent->_left = subLR;
		if (subLR != nullptr)
			subLR->_parent = parent;

		//将parent链接到subL右侧
		subL->_right = parent;
		parent->_parent = subL;

		//将subL和pparent链接起来
		//pparent为nullptr，subL要成为新的根
		if (pparent == nullptr)
		{
			subL->_parent = pparent;
			_root = subL;
		}
		//pparent不为nullptr，就链接pparent和subL
		else
		{
			if (pparent->_left == parent)
				pparent->_left = subL;
			else
				pparent->_right = subL;
			subL->_parent = pparent;
		}
	}

	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;//parent的的右边一定不为nullptr
		Node* subRL = subR->_left;//subR的左边可能为nullptr
		Node* pparent = parent->_parent;//保存parent的根(父节点)

		//将subRL链接到parent的右侧
		parent->_right = subRL;
		if (subRL != nullptr)
			subRL->_parent = parent;

		//将parent链接到subR左侧
		subR->_left = parent;
		parent->_parent = subR;

		//将subR和pparent链接起来
		//pparent为nullptr，subR要成为新的根
		if (pparent == nullptr)//_parent == _root
		{
			subR->_parent = pparent;
			_root = subR;
		}
		//pparent不为nullptr，就链接pparent和subR
		else
		{
			if (pparent->_right == parent)
				pparent->_right = subR;
			else
				pparent->_left = subR;
			subR->_parent = pparent;
		}
	}

	//右旋左旋
	void RotateRL(Node* parent)
	{
		RotateR(parent->_right);
		RotateL(parent);
	}

	//左旋右旋
	void RotateLR(Node* parent)
	{
		RotateL(parent->_left);
		RotateR(parent);
	}
};