红黑树模拟实现

个人主页：Lei宝啊 

愿所有美好如期而遇

红黑树概念

红黑树是一种二叉搜索树，对比于AVL树，他不存储平衡因子，取而代之的是存储节点颜色，黑色或者红色，我们这里对颜色的定义使用枚举，通过对每个节点颜色的限制，使得红黑树确保没有一条路径比其他路径长两倍，因而是接近平衡的。

红黑树性质

1. 每个节点的颜色不是黑色就是红色。
2. 根节点必须是黑色。
3. 如果一个节点的颜色是红色，那么它的两个孩子是黑色，不能有连续的红色节点，但是可以有连续的黑色节点。
4. 每条路径的黑色节点的数量相等。

保证了上面几条核心性质，就能保证黑树没有一条路径比其他路径长两倍。

红黑树节点定义

enum Color
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	struct RBTreeNode* _left;
	struct RBTreeNode* _right;
	struct RBTreeNode* _parent;
	T _data;
	int _color;

	RBTreeNode(const K& data)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _color(RED)
		, _data(data)
	{}
};

我们这里将每个新节点默认的颜色设置为红色，因为如果我们默认设置成黑色，插入一个节点，那么就不是每条路径上的黑色节点数都相同了，非常不好控制，而红色节点只会影响当前路径有连续红色节点，我们后续可以通过其他手段控制。

红黑树类的结构

template<class K, class T>
class RBTree
{
	typedef RBTreeNode<K, T> Node;
public:

	bool Insert(const K& key, const T& val);
	bool IsBlance();
	void Inorder();

private:

	bool _IsBlance(Node *root, int real_black_num, int standard_black_num);
	void _Inorder(Node* root);

	//左单旋
	void RotateL(Node* par)	
	//右单旋
	void RotateR(Node* par)
	
	Node* _root = nullptr;
};

红黑树节点插入操作

红黑树是在二叉搜索树基础上加上限制平衡的手段，因此红黑树节点的插入可以分为两步：

第一步：

按照二叉搜索树的规则插入节点：（这里可以参考：二叉搜索树，AVL树）

简单来说就是节点的左子树的每个节点的值都小于节点的值，节点的右子树的每个节点的值都大于节点的值，同时对二叉搜索树进行中序遍历可以得到有序的一个序列。

		Node* newnode = new Node(data);

		if (_root == nullptr)
		{
			_root = newnode;
			_root->_color = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* par = nullptr;
		while (cur)
		{
			par = cur;

			if (compare(cur->_data) == data) return false;
			else if (compare(cur->_data) < data) cur = cur->_right;
			else cur = cur->_left;
		}

		if (compare(par->_data) > data) par->_left = newnode;
		else par->_right = newnode;

		newnode->_parent = par;

		cur = newnode;

第二步：

检测新节点插入后，红黑树的性质是否遭到破坏。

因为我们设置了新节点的颜色为红色，如果这个新节点插入的位置是黑色节点的孩子，那么无需做出调整；如果插入位置是红色节点的孩子，那么就违反了不能有连续红色节点这个性质，此时我们需要做出调整。

调整

调整分为两种情况

情况一：

假设我们插入的节点就是cur，此时我们需要做出调整，直接旋转(不行)，变色？使p和u节点变成黑色怎么样？是的，当前我们看到的确实平衡了，但是如果这只是子树呢？其他路径是不是就不平衡了，所以我们把g节点变成红色，这样就可以了。

但是什么情况下我们才这么做呢？如果u是黑色节点呢？如果u不存在呢？我们还能这样变吗？

所以这样做是因为uncle节点存在且为红色，这就是情况一。

情况二：

那么显然第二种情况就是叔叔不存在或者叔叔为黑色节点，那么这为什么算是一种情况呢？我们画图来看：（叔叔不存在）

这种情况我们如何对节点进行调整？

此时我们可以进行p节点的左单旋，然后进行g节点的右单旋，最后对cur节点和g节点进行变色，cur节点变黑色，g节点变红色：

或者是这样：（叔叔存在且为黑色）

先进行一次情况一的调整：（叔叔存在且为红色） 

剩下这种情况我们就需要进行双旋，首先将p节点进行左旋，然后将g节点进行右旋，之后是这样的：

然后我们进行变色：cur节点变黑，g节点变红，完成双旋：

代码：

我们的逻辑是这样的：

cur是我们插入的新节点，par是cur的父节点，我们要调整的情况是：cur为红色，且父节点为红色，当我们调整后，cur = par；par = par->_parent；如果此时cur已经是根节点，那么par为空，我们结束调整，并将根节点的颜色变成黑色。

进入循环后，首先判断par是grandfather的左节点还是右节点，因为我们需要知道叔叔是g节点的哪个孩子（左还是右），我们主要是看叔叔节点来判断如何进行旋转（左左，左右，右左，右右）。

（当然，也可以先进行判断叔叔是否存在，颜色是什么，然后再判断他是g节点的左还是右，这都是可以的（但是这样做每一个if里都要判断左右，还是比较麻烦的））

        while (par && par->_color == RED)
		{
			Node* grandfather = par->_parent;

			if (grandfather->_left == par)
			{
				Node* uncle = grandfather->_right;

				//情况一：鼠鼠存在且为红色
				if (uncle && uncle->_color == RED)
				{
					par->_color = BLACK;
					uncle->_color = BLACK;
					grandfather->_color = RED;

					cur = grandfather;
					par = cur->_parent;
				}
				//情况二：鼠鼠不存在或者鼠鼠为黑色(可以一同处理)
				else
				{
					//左左，右单旋
					if (cur == par->_left)
					{
						RotateR(grandfather);

						grandfather->_color = RED;
						par->_color = BLACK;
					}
					//左右，左右双旋
					else
					{
						RotateL(par);
						RotateR(grandfather);

						cur->_color = BLACK;
						grandfather->_color = RED;
					}

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

				//情况一：鼠鼠存在且为红色
				if (uncle && uncle->_color == RED)
				{
					par->_color = BLACK;
					uncle->_color = BLACK;
					grandfather->_color = RED;

					cur = grandfather;
					par = cur->_parent;
				}
				//情况二：鼠鼠不存在或者鼠鼠为黑色(可以一同处理)
				else
				{
					//右右，左单旋
					if (cur == par->_right)
					{
						RotateL(grandfather);

						grandfather->_color = RED;
						par->_color = BLACK;
					}
					//右左，右左双旋
					else
					{
						RotateR(par);
						RotateL(grandfather);

						cur->_color = BLACK;
						grandfather->_color = RED;
					}

					break;
				}
			}		
		}
		_root->_color = BLACK;

		return true;
	}

    //左单旋
	void RotateL(Node* par)
	{
		Node* subR = par->_right;
		Node* subRL = subR->_left;

		par->_right = subRL;
		if (subRL)
			subRL->_parent = par;

		Node* p_par = par->_parent;
		subR->_left = par;
		par->_parent = subR;

		if (p_par == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (p_par->_left == par)
			{
				p_par->_left = subR;
				subR->_parent = p_par;
			}
			else
			{
				p_par->_right = subR;
				subR->_parent = p_par;
			}
		}
	}

	//右单旋
	void RotateR(Node* par)
	{
		Node* subL = par->_left;
		Node* subLR = subL->_right;

		par->_left = subLR;
		if (subLR)
			subLR->_parent = par;

		Node* p_par = par->_parent;
		subL->_right = par;
		par->_parent = subL;

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

整体代码

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

enum Color
{
	RED,
	BLACK
};

template<class K, class T>
struct RBTreeNode
{
	struct RBTreeNode* _left;
	struct RBTreeNode* _right;
	struct RBTreeNode* _parent;
	pair<K, T> _p;
	int _color;

	RBTreeNode(const K& key, const T& val)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _color(RED)
		, _p(key, val)
	{}
};

template<class K, class T>
class RBTree
{
	typedef RBTreeNode<K, T> Node;
public:
	bool Insert(const K& key, const T& val)
	{
		Node* newnode = new Node(key, val);

		if (_root == nullptr)
		{
			_root = newnode;
			_root->_color = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* par = nullptr;
		while (cur)
		{
			par = cur;

			if (cur->_p.first == key) return false;
			else if (cur->_p.first < key) cur = cur->_right;
			else cur = cur->_left;
		}

		if (par->_p.first > key) par->_left = newnode;
		else par->_right = newnode;

		newnode->_parent = par;

		cur = newnode;
		while (par && par->_color == RED)
		{
			Node* grandfather = par->_parent;

			if (grandfather->_left == par)
			{
				Node* uncle = grandfather->_right;

				//情况一：鼠鼠存在且为红色
				if (uncle && uncle->_color == RED)
				{
					par->_color = BLACK;
					uncle->_color = BLACK;
					grandfather->_color = RED;

					cur = grandfather;
					par = cur->_parent;
				}
				//情况二：鼠鼠不存在或者鼠鼠为黑色(可以一同处理)
				else
				{
					//左左，右单旋
					if (cur == par->_left)
					{
						RotateR(grandfather);

						grandfather->_color = RED;
						par->_color = BLACK;
					}
					//左右，左右双旋
					else
					{
						RotateL(par);
						RotateR(grandfather);

						cur->_color = BLACK;
						grandfather->_color = RED;
					}

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

				//情况一：鼠鼠存在且为红色
				if (uncle && uncle->_color == RED)
				{
					par->_color = BLACK;
					uncle->_color = BLACK;
					grandfather->_color = RED;

					cur = grandfather;
					par = cur->_parent;
				}
				//情况二：鼠鼠不存在或者鼠鼠为黑色(可以一同处理)
				else
				{
					//右右，左单旋
					if (cur == par->_right)
					{
						RotateL(grandfather);

						grandfather->_color = RED;
						par->_color = BLACK;
					}
					//右左，右左双旋
					else
					{
						RotateR(par);
						RotateL(grandfather);

						cur->_color = BLACK;
						grandfather->_color = RED;
					}

					break;
				}
			}		
		}
		_root->_color = BLACK;

		return true;
	}

	bool IsBlance()
	{
		if (_root && _root->_color == RED)
			return false;

		int standard_black_num = 0;

		Node* cur = _root;
		while (cur)
		{
			if (cur->_color == BLACK)
				standard_black_num++;

			cur = cur->_left;
		}

		return _IsBlance(_root, 0, standard_black_num);
	}

	void Inorder()
	{
		return _Inorder(_root);
	}

private:

	// 检查这棵树是否是红黑树
	// 1、遵守根节点为黑色
	// 2、遵守不能有连续的红色节点
	// 3、每条路径黑色节点数量相同
	// 
	// 遵守最长路径不超过最短路径的两倍，最长路径为一黑一红，最短路径为全黑。
	bool _IsBlance(Node *root, int real_black_num, int standard_black_num)
	{
		if (root == nullptr)
		{
			if (real_black_num != standard_black_num)
				return false;

			return true;
		}

		if (root != _root && root->_color == RED && root->_parent->_color == RED)
			return false;

		if (root->_color == BLACK)
			real_black_num++;

		return _IsBlance(root->_left, real_black_num, standard_black_num)
			&& _IsBlance(root->_right, real_black_num, standard_black_num);
	}

	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout << root->_p.first << " : " << root->_p.second << endl;
		_Inorder(root->_right);
	}

	//左单旋
	void RotateL(Node* par)
	{
		Node* subR = par->_right;
		Node* subRL = subR->_left;

		par->_right = subRL;
		if (subRL)
			subRL->_parent = par;

		Node* p_par = par->_parent;
		subR->_left = par;
		par->_parent = subR;

		if (p_par == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (p_par->_left == par)
			{
				p_par->_left = subR;
				subR->_parent = p_par;
			}
			else
			{
				p_par->_right = subR;
				subR->_parent = p_par;
			}
		}
	}

	//右单旋
	void RotateR(Node* par)
	{
		Node* subL = par->_left;
		Node* subLR = subL->_right;

		par->_left = subLR;
		if (subLR)
			subLR->_parent = par;

		Node* p_par = par->_parent;
		subL->_right = par;
		par->_parent = subL;

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

	Node* _root = nullptr;

};