紅黑樹的插入及查找

紅黑樹：首先是一棵二叉搜索樹，它在每個節點上增加了一個存儲位來表示節點的顏色，可以是Red或Black。通過對任何一條從根到葉子簡單路徑上的顏色來約束，紅黑樹保證最長路徑不超過最短路徑的兩倍，因而近似于平衡。

紅黑樹滿足的性質：

1. 根節點是黑色的

2. 如果一個節點是紅色的，則它的兩個子節點是黑色的(沒有連續的紅節點)

3. 每條路徑的黑色節點的數量相等

紅黑樹保證最長路徑不超過最短路徑的兩倍，如下圖所示

插入節點時的三種情況

1. 
   

2. cur為紅，p為紅，g為黑，u存在且為紅

   

3. cur為紅，p為紅，g為黑，u不存在/u為黑，p為g的左孩子，cur為p的左孩子，則進行右單旋轉；相反，p為g的右孩子，cur為p的右孩子，則進行左單旋轉

   p、g變色--p變黑，g變紅

   

4. cur為紅，p為紅，g為黑，u不存在/u為黑，p為g的左孩子，cur為p的右孩子，則針對p做左單旋轉；相反，p為g的右孩子，cur為p的左孩子，則針對p做右單旋轉

#pragma once

#include <iostream>
using namespace std;
enum Color
{
	RED,
	BALCK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	K _key;
	V _value;
	Color _col;
	RBTreeNode(const K& key, const V& value)
		:_left(NULL)
		, _right(NULL)
		, _parent(NULL)
		, _key(key)
		, _value(value)
		, _col(RED)
	{}
};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree()
		:_root(NULL)
	{}
	Node* Find(const K& key)
	{
		if (_root == NULL)
			return NULL;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key == key)
				return cur;
			else if (cur->_key < key)
				cur = cur->_right;
			else
				cur = cur->_left;
		}
		return NULL;
	}
	bool Insert(const K& key, const V& value)
	{
		if (_root == NULL)
		{
			_root = new Node(key, value);
			_root->_col = BALCK;
			return true;
		}
		Node* cur = _root;
		Node* parent = NULL;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key>key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				cout << "該節點已存在" << endl;
				return false;
			}
		}
		cur = new Node(key, value);
		if (parent->_key > key)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//調整節點顏色
		while (cur != _root&&parent->_col == RED)
		{//規定根節點必須為黑色，若parent的顏色為紅色，則它一定不為根節點，它的父節點也一定存在
			Node* ppNode = parent->_parent;//不用判空
			Node* uncle = NULL;
			
			if (parent == ppNode->_left)
			{//parent為它的父節點的左孩子，則叔節點若存在，肯定在右邊
				uncle = ppNode->_right;
				if (uncle&&uncle->_col == RED)
				{//1.cur為紅，parent為紅，ppNode為黑，u存在且為紅
					parent->_col = uncle->_col = BALCK;
					ppNode->_col = RED;
					cur = ppNode;
					ppNode = cur->_parent;
				}
				else
				{//2.cur為紅，parent為紅，uncle不存在或者為黑
					if (cur == parent->_right)
					{
						RotateL(parent);
						swap(cur, parent);
					}
					parent->_col = BALCK;
					ppNode->_col = RED;
					RotateR(ppNode);
				}
			}
			else
			{//另一邊
				uncle = ppNode->_left;
				if (uncle&&uncle->_col == RED)
				{//1.cur為紅，parent為紅，ppNode為黑，u存在且為紅
					parent->_col = uncle->_col = BALCK;
					ppNode->_col = RED;
					cur = ppNode;
					ppNode = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(parent);
						swap(cur, parent);
					}
					parent->_col = BALCK;
					ppNode->_col = RED;
					RotateL(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;
		if (parent == _root || ppNode == NULL)//若要調整的節點為根節點
		{
			_root = subL;
			subL->_parent = NULL;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}

	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;
		if (parent == _root || ppNode == NULL)//若要調整的節點為根節點
		{
			_root = subR;
			subR->_parent = NULL;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}
	bool IsBalance()
	{
		int BlackNodeCount = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BALCK)
			{
				BlackNodeCount++;
			}
			cur = cur->_left;
		}
		int count = 0;
		return _IsBalance(_root, BlackNodeCount, count);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	~RBTree()
	{}
protected:
	bool _IsBalance(Node* root, const int BlackNodeCount, int count)
	{
		if (root == NULL)
			return false;
		if (root->_parent)
		{
			if (root->_col == RED && root->_parent->_col == RED)
			{
				cout << "不能有兩個連續的紅節點" << endl;
				return false;
			}
		}
		if (root->_col == BALCK)
			++count;
		if (root->_left == NULL&&root->_right == NULL&&count != BlackNodeCount)
		{
			cout << "該條路徑上黑色節點數目與其它不相等" << endl;
			return false;
		}
		return _IsBalance(root->_left, BlackNodeCount,count) &&
			_IsBalance(root->_right, BlackNodeCount,count);
	}
	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
protected:
	Node* _root;
};

void Test()
{
	RBTree<int,int> bt;
	int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
	{
		bt.Insert(arr[i], i);
	}
	bt.IsBalance();
	bt.InOrder();
	cout << bt.Find(6) << endl;;
	cout<<bt.Find(9) << endl;
}

紅黑樹與AVL樹的異同：

紅黑樹和AVL樹都是高效的平衡二叉樹，增刪查改的時間復雜度都是O(lg(N))

紅黑樹的不追求完全平衡，保證最長路徑不超過最短路徑的2倍，相對而言，降低了旋轉的要求，所以性能跟AVL樹差不多，但是紅黑樹實現更簡單，所以實際運用中紅黑樹更多。

紅黑樹的應用：

STL庫中的map、set

多路復用epoll模式在linux內核的實現

JAVA的TreeMap實現