紅黑樹：節點插入詳解及其紅黑樹自我實作

紅黑樹的四個性質：

1. 每個結點不是紅色就是黑色
2. 根節點是黑色的
3. 如果一個節點是紅色的，則它的兩個孩子結點是黑色的
4. 對于每個結點，從該結點到其所有后代葉結點的簡單路徑上，均包含相同數目的黑色結點
5. 每個葉子結點都是黑色的(此處的葉子結點指的是空結點）

紅黑樹節點的定義：

// 紅黑樹節點的定義
template<class T>
struct RBTreeNode
{
	RBTreeNode(const T& x = T(), Color c = RED)
	: left(nullptr)
	, right(nullptr)
	, parent(nullptr)
	, data(x)
	, color(c)
	{}

	RBTreeNode<T>* left;
	RBTreeNode<T>* right;
	RBTreeNode<T>* parent;
	T data;
	Color color;
};

情況一：cur節點為紅色 && 叔叔節點存在且為紅色

1. 如果grandparent是根節點，調整完成后，需要將grandparent改為黑色
2. 如果grandparent是子樹，grandparent一定有雙親，且grandparent的雙親如果是紅色，需要繼續向上調整

調整方法：

1. uncle，parent節點變為黑色
2. grandparent節點變為紅色

調整后：

情況二: cur節點為紅色是parent左孩子，parent為紅，grandparent為黑，uncle不存在 || uncle為黑

1. 如果uncle節點不存在，則cur一定是新插入節點，因為如果cur不是新插入節點，abc子樹中一定有節點的顏色是黑色，就不滿足性質4∶每條路徑黑色節點個數相同，
2. 如果u節點存在，則其一定是黑色的，那么cur節點原來的顏色定是黑色的，現在看到其是紅色的原因是因為cur的子樹在調整的程序中將cur節點的顏色由黑色改成紅色，

調整方法：

1. 將parent節點改為黑色，grandparent節點改為紅色
2. 以grandparent為根節點進行右單旋

調整后：
將parent節點改為黑色，grandparent節點改為紅色：

以grandparent為根節點進行右單旋：

情況三: cur節點為紅色是parent右孩子，parent為紅，grandparent為黑，uncle不存在 || uncle為黑

調整方法：

1. 對以parent為根節點進行左單旋
2. 情況調整成為情況二，同理情況二

調整后：

1. 對以parent為根節點進行左單選：

2. 同理情況二

剩下兩種情況為二、三情況中二叉樹的鏡像，同理二三可得

1. 情況二中的鏡像：parent為grandparent的右孩子，cur為parent的右孩子，則進行以grandparent為根節點進行左單旋轉
2. 情況三中的鏡像：parent為grandparent的右孩子，cur為parent的左孩子，則以parent為根節點右單旋

紅黑樹代碼實作：

#pragma once
#include <iostream>
using namespace std;
enum Color{ RED, BLACK };

//紅黑樹節點定義
template<class T>
struct RBTreeNode
{
	RBTreeNode(const T& x = T(), Color c = RED)
	: left(nullptr)
	, right(nullptr)
	, parent(nullptr)
	, data(x)
	, color(c)
	{}

	RBTreeNode<T>* left;
	RBTreeNode<T>* right;
	RBTreeNode<T>* parent;
	T data;
	Color color;
};

//假設：紅黑樹中值是唯一的
template<class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	RBTree()
	{
		head = new Node();
		head->left = head;
		head->right = head;
		head->parent = nullptr;  // 紅黑樹中沒有任何節點
	}
	~RBTree()
	{
		Destroy(GetRoot());
		delete head;
		head = nullptr;
	}
	bool Insert(const T& data)
	{
		Node*& root = GetRoot();
		if (root == nullptr)
		{
			root = new Node(data, BLACK);
			root->parent = head;
			head->left = root;
			head->right = root;
			return true;
		}
		//查找插入節點在二叉樹中的位置
		Node* cur = root;
		Node* parent = head;
		while (cur != nullptr)
		{
			if (cur->data > data)
				cur = cur->left;
			else if (cur->data < data)
				cur = cur->right;
			else
				return false;
		}
		//插入新節點
		cur = new Node(data);
		if (parent->data > cur->data)
			parent->left = cur;
		else
			parent->right = cur;

		//插入節點默認是紅色的，對節點顏色開始更新
		while (parent != head && parent->color == RED)
		{
			Node* grandFather = parent->parent;
			if (parent == grandFather->left)
			{
				//情況一：叔叔節點存在且為紅色
				Node* uncle = grandFather->right;
				if (uncle && RED == uncle->color)
				{
					parent->color = BLACK;
					uncle->color = BLACK;
					grandFather->color = RED;
					cur = grandFather;
					parent = cur->parent;
				}
				else
				{
					//情況二和情況三:叔叔節點不存在 || 叔叔節點存在且為黑色
					if (cur == parent->right)
					{
						// 情況三
						RotateLeft(parent);
						swap(parent, cur);
					}
					//情況二
					parent->color = BLACK;
					grandFather->color = RED;
					RotateRight(grandFather);
				}
				
			}

			else
			{
				Node* uncle = grandFather->left;
				if (uncle && uncle->color == RED)
				{
					// 情況一的反情況
					parent->color = BLACK;
					uncle->color = BLACK;
					grandFather->color = RED;
					cur = grandFather;
					parent = cur->parent;
				}
				else
				{
					if (cur == parent->left)
					{
						//情況三的反情況
						RotateRight(parent);
						swap(parent, cur);
					}
					//情況二的反情況
					parent->color = BLACK;
					grandFather->color = RED;
					RotateLeft(grandFather);
				}
			}
		}
		// 新節點插入之后，紅色樹中的最大或者最小節點發生變化
		root->color = BLACK;
		head->left = LeftMost();
		head->right = RightMost();
		return true;
	}

private:
	void RotateRight(Node* parent)
	{
		Node* subL = parent->left;
		Node* subLR = subL->right;

		parent->left = subLR;
		if (subLR)
			subLR->parent = parent;
		subL->right = parent;
		Node* pparent = parent->parent;
		parent->parent = subL;
		subL->parent = pparent;
		if (pparent == head)
		{
			// 說明旋轉之前parent一定是根節點
			head->parent=subL
		}
		else
		{
			if (parent=pparent->left)
				pparent->left = subL;
			else
				pparent->right = subL;
		}

	}
	void RotateLeft(Node* parent)
	{
		Node* subR = parent->right;
		Node* subRL = subR->left;

		parent->right = subRL;
		// 注意：右單支
		if (subRL)
			subRL->parent = parent;

		subR->left = parent;

		// 更新subR和parent的雙親
		Node* pparent = parent->parent;
		parent->parent = subR;
		subR->parent = pparent;

		// 需要處理旋轉之后parent雙親的情況
		if (pparent == head)
		{
			// 旋轉之前parent是根節點
			head->parent = subR;
		}
		else
		{
			// 旋轉之前parent是有雙親的
			if (parent == pparent->left)
				pparent->left = subR;
			else
				pparent->right = subR;
		}
	}
	Node*& GetRoot()
	{
		return head->parent;
	}
	Node* LeftMost()
	{
		Node* root = GetRoot();
		if (nullptr == root)
			return head;

		Node* cur = root;
		while (cur->left)
			cur = cur->left;

		return cur;
	}
	Node* RightMost()
	{
		Node* root = GetRoot();
		if (nullptr == root)
			return head;

		Node* cur = root;
		while (cur->right)
			cur = cur->right;

		return cur;
	}
	void Destroy(Node* & root)
	{
		if (root)
		{
			Destroy(root->left);
			Destroy(root->right);
			delete root;
			root = nullptr;
		}
	}

private:
	Node* head;    // 指向紅黑樹中的頭節點
};