數據結構之——紅黑樹

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

紅黑樹是滿足下面紅黑性質的二叉搜索樹：

1. 每個節點，不是紅色就是黑色的

2. 根節點是黑色的

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

4. 對每個節點，從該節點到其所有后代葉節點的簡單路徑上，均包含相同數目的黑色節點。（每條路徑的黑色節點的數量相等）

這里分析一下為什么紅黑樹能保證最長路徑不超過最短路徑的兩倍：首先因為第4條約束條件假設一棵樹如下所示：

   B

 B   B

B      B    B表示為黑色結點，那么要在其中插入任何一個黑色結點就需要保證第4條約定，而如果要插入紅色結點，則第3條約束又使得紅色結點只能插在黑色結點之間，因此一條路徑最多變成：

   B

 B   R

B      B

        R

         B      因此，最長路徑不超過最短路徑的兩倍，也就保證了搜索的效率；

下面是實現紅黑樹的插入過程：

#pragma once

#include <iostream>
using namespace std;

//結點的顏色 紅or黑
enum Color
{
	RED,
	BLACK
};

//結點結構體
template <class K, class V>
struct RBTreeNode
{
	K _key;
	V _val;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Color _col;

	RBTreeNode(const K& key, const V& val)
		:_key(key)
		,_val(val)
		,_left(NULL)
		,_right(NULL)
		,_parent(NULL)
		,_col(RED)
	{}
};

//紅黑樹類
template <class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;

public:
	RBTree()
		:_root(NULL)
	{}
	~RBTree()
	{
		_Clear(_root);
	}

	//插入結點
	bool Insert(const K& key, const V& val)
	{
		if(_root == NULL)//如果根結點為NULL，創建新的結點為根結點返回true
		{
			_root = new Node(key, val);
			_root->_col = BLACK;
			return true;
		}

		//如果根結點不為NULL，則遍歷樹直到找到合適的插入位置
		Node* cur = _root;
		Node* prev = cur;
		while(cur != NULL)
		{
			if(cur->_key == key)//如果樹中已經有該結點，則返回false
				return false;
			else if(cur->_key > key)//如果關鍵值小于結點的關鍵值，則去左子樹找
			{
				prev = cur;
				cur = cur->_left;
			}
			else//否則關鍵值大于結點的關鍵值，去右子樹找
			{
				prev = cur;
				cur = cur->_right;
			}
		}
		//循環結束，找到了合適的插入位置，判斷應該插入到結點的左邊還是右邊
		Node* tmp = new Node(key, val);
		if(prev->_key > key)
			prev->_left = tmp;
		else
			prev->_right = tmp;
		tmp->_parent = prev;

		//插入結點之后，就要開始判斷目前的樹是否符合紅黑樹的性質
		while((tmp != _root) && (prev->_col == RED))
		{
			Node* grandfather = prev->_parent;//提取出tmp的祖父結點
			if(grandfather->_left == prev)//如果prev是grandfather的左結點
			{
				//第一種情況
				//tmp為紅，prev為紅，grandfather為黑，uncle存在且為紅
				//則將prev,uncle改為黑，grandfather改為紅，然后把grandfather當成tmp，繼續向上調整。
				Node* uncle = grandfather->_right;
				if(uncle != NULL && uncle->_col == RED)
				{
					prev->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					tmp = grandfather;
					prev = tmp->_parent;
				}
				else//第二種情況:tmp為紅，prev為紅，grandfather為黑，uncle不存在/uncle為黑
					//prev為grandfather的左孩子，tmp為prev的左孩子，則進行右單旋轉；
					//prev、grandfather變色--prev變黑，grandfather變紅

				{
					//第三種情況
					//tmp為紅，prev為紅，grandfather為黑，uncle不存在/uncle為黑
					//prev為grandfather的左孩子，tmp為prev的右孩子，則針對prev做左單旋轉；
					//則轉換成了情況二

					if(prev->_right == tmp)
					{
						_RotateL(prev);
						swap(tmp, prev);
					}
					_RotateR(grandfather);//進行右單旋
					prev->_col = BLACK;
					grandfather->_col = RED;
					break;
				}
			}
			else//當perv是grandfather的右結點的時候，和上面的情況相反
			{
				//第一種情況
				//tmp為紅，prev為紅，grandfather為黑，uncle存在且為紅
				//則將prev,uncle改為黑，grandfather改為紅，然后把grandfather當成tmp，繼續向上調整。
				Node* uncle = grandfather->_left;
				if(uncle != NULL && uncle->_col == RED)
				{
					prev->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					tmp = grandfather;
					prev = tmp->_parent;
				}
				else//第二種情況:tmp為紅，prev為紅，grandfather為黑，uncle不存在/uncle為黑
					//prev為grandfather的右孩子，tmp為prev的右孩子，則進行左單旋轉
					//prev、grandfather變色--prev變黑，grandfather變紅

				{
					//第三種情況
					//tmp為紅，prev為紅，grandfather為黑，uncle不存在/uncle為黑
					//prev為grandfather的右孩子，tmp為prev的左孩子，則針對prev做右單旋轉
					//則轉換成了情況二

					if(prev->_left == tmp)
					{
						_RotateR(prev);
						swap(tmp, prev);
					}
					_RotateL(grandfather);//進行右單旋
					prev->_col = BLACK;
					grandfather->_col = RED;
					break;
				}
			}
		}
		//如果根結點被調整成了紅色，將其改為黑色，并會不影響左右黑結點的個數
		if(_root->_col == RED)
			_root->_col = BLACK;
		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout<<endl;
	}

	/*bool Find(const K& key)
	{

	}*/

private:
	void _Clear(Node* root)
	{
		if(root == NULL)
			return;

		_Clear(root->_left);
		_Clear(root->_right);
		delete root;
		root = NULL;
	}
	
	void _RotateL(Node* parent)//左單旋
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
 
        parent->_right = subRL;
        if (subRL != NULL)
            subRL->_parent = parent;
         
        Node* ppNode = parent->_parent;
 
        subR->_left = parent;
        parent->_parent = subR;
 
        if (ppNode == NULL)
            _root = subR;
        else
        {
            if (ppNode->_left == parent)
                ppNode->_left = subR;
            else
                ppNode->_right = subR;
        }
		subR->_parent = ppNode;
    }

    void _RotateR(Node* parent)//右單旋
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
 
        parent->_left = subLR;
        if (subLR != NULL)
            subLR->_parent = parent;
 
        Node* ppNode = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;
 
        if (ppNode == NULL)
            _root = subL;
        else
        {
            if (ppNode->_left == parent)
                ppNode->_left = subL;
            else
                ppNode->_right = subL;
        }
		subL->_parent = ppNode;
	}

	void _InOrder(Node* root)
	{
		if(root != NULL)
		{
			_InOrder(root->_left);
			cout<<root->_key<<" ";
			_InOrder(root->_right);
		}
	}

private:
	Node* _root;
};


void Test()
{
	int arr[] = {3, 4, 6, 1, 7, 2, 8};
	RBTree<int, int> t;
	for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i)
		t.Insert(arr[i], i);

	t.InOrder();
}

運行程序：

《完》