淺析紅黑樹算法

紅黑樹簡介

    紅黑樹是一種自平衡二叉查找樹，也有著二叉搜索樹的特性，保持著右邊始終大于左邊結點key的特性。前面提到過的AVL樹，也是二叉搜索樹的一種變形，紅黑樹沒有達到AVL樹的高度平衡，換句話說，它的高度，并沒有AVL樹那么高的要求，但他的應用卻更加的廣泛，實踐中是相當高效的，他可以在O(log n)的時間內做查找、插入、刪除操作。在C++ STL中，set、multiset、map、multimap等都應用到的紅黑樹的變體。

    紅黑樹在平衡二叉搜索樹的前提下，每個節點新增了 _color 這一成員變量，用來對各個節點做出標記。接下來，我們就來分析紅黑樹的插入算法。

    一棵AVL樹，需要滿足以下幾條要求。

    1、每個結點，不是黑色就是紅色

    2、樹的根結點必須是黑色

    3、從根節點到葉子結點的任意一條路上，不允許存在兩個連續的紅色結點。

    4、對于每個結點，從他開始到每個葉結點的簡單路徑上，黑色結點樹相同。

    這里多說一點，如果滿足以上條件的話，從根節點開始，到葉子結點，最長的不會超過最長路徑的兩倍。（可以考慮最為極端的情況）

思路簡析

    和AVL樹相同，要保證樹的平衡性，必須要用到的是旋轉算法。由于紅黑樹的情況比較多（盡管寫起代碼來不是很復雜），所以在這里旋轉的過程中，我們不像AVL樹一樣，旋轉的同時對平衡因子進行調整，紅黑樹的旋轉算法，只是單純調整當前結點與其parent 、grandparent 、uncle結點的相對位置，在旋轉完成之后，我們再對結點顏色進行設置。

    插入算法會在下面給出。

首先我們給出結點的定義。

enum Color
{
RED,
BLACK
};
template<typename K, typename V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
K _key;
V _value;
Color _color;
RBTreeNode(const K& key,const V& value)
:_left(NULL)
, _right(NULL)
, _parent(NULL)
, _key(key)
, _value(value)
, _color(RED)//默認構造紅色結點
{}
};

    _key為關鍵碼（_key值是不允許重復的），_value為值，關于這里結點的構造函數，想多說一點，為什么結點顏色要默認給紅色？很明顯，一般情況下，黑色結點比紅色結點多，但這里我們需要注意的是，我們針對的調整，其實大多數是紅色。黑色結點下如果追加了紅色結點，是不需要調整的，紅色結點下如果多增加了一個黑色結點，是一定要進行調整的。

接下來開始插入結點。

    1、處理特殊情況

    當樹為空樹時，直接 new 一個結點給根，然后再改變顏色即可。

if (_root == NULL)
{
_root = new Node(key, value);
_root->_color = BLACK;
return true;
}

    2、樹不為空樹時，我們首先需要找到我們待插入結點的位置。由于紅黑樹是二叉搜索樹，通過循環，比較待插入結點的key值和當前結點的大小，找到待插入結點的位置。同時給該節點開辟空間，確定和parent節點的指向關系。

Node* cur = _root;
Node* parent = NULL;
while (cur != NULL)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key, value);
if (key > (parent->_key))
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}

    當插入結點的parent結點為黑色結點時，不需要做任何調整，只需要和parent結點建立聯系即可。

    3、下面是需要我們特殊處理的幾種情況。

    我們給出四個Node結點  cur（待插入結點）、parent （cur的父親結點）、grandparent（cur的祖父結點）、uncle（cur的叔叔結點）。

情況一、

    parent為黑色，uncle存在且為紅色

如圖：

    三角形結點只是表示可能存在的結點，可能為空。

    當cur為新插入結點時，a-e結點均為空結點，由于不可以存在連續的紅結點，因此，我們需要將parent結點和uncle結點變為黑色。細心的話可以發現，grandparent結點變為了紅色，這是因為當grandparent不為根節點時，我們這棵子樹的一條支路上的黑色結點就會多出一個，因此我們需要將grandparent結點變為紅色，然后繼續向上進行調整。在插入完成之后，我們只需要統一將根節點重新賦值為紅色即可。

情況二、

    parent為紅色，uncle結點不存在，或uncle結點存在，但為黑色

如圖：

   看到第一張圖的時候，不要懷疑這里畫的有問題，這種情況是可能存在的，那就是說，cur是調整上來的，從我的上一種情況調整過來的，雖然看著grandparent的左右支路黑色結點數不相同，但我還有下面的三角形結點。

    現在我這里就需要進行旋轉，為什么這里不能直接顏色變換？因為我們拋過三角形結點，以grandparent結點為分界，最左支路和最后支路的，黑色結點數差一。旋轉的圖示如上圖所示，以grandparent結點為軸，向右旋轉。將grandparent結點作為parent結點的右子樹進行旋轉。同時需要的是，grandparent結點不一定是根節點，我們需要提前保留并判斷grandparent->_parent結點，之后重新賦給parent->_parent。

情況三、

    如果可以理解了第二種情況，第三種情況就容易理解了許多，和第二種情況一樣，只不過cur是parent的右子樹，我們需要先以parent為軸，向左旋轉，得到上面這種情況之后，再以grandparent為軸向右旋轉。如下圖。

值得注意的一點，也是一開始寫代碼總是驗證出錯的一個問題，我們先以parent為軸左旋，之后看上圖，cur此時變成了parent->_parent,如果此時按照情況二的處理方式，結點顏色一定會發生問題，因此，在上圖中，我專門給出了一張圖，將parent和cur指針交換，注意，只交換的是指針。

到這里，紅黑樹的基本情況以及處理完畢，再有的話就是當parent一開始就是在grandparent的右子樹上的幾種情況，和上面的旋轉成鏡像的關系。下面給出具體的代碼：

bool Insert(const K& key,const V& value)
{
//空樹
if (_root == NULL)
{
_root = new Node(key, value);
_root->_color = BLACK;
return true;
}
//構建節點，并插入到對應位置
Node* cur = _root;
Node* parent = NULL;
while (cur != NULL)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key, value);
if (key > (parent->_key))
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//開始調整
while (cur != _root && parent->_color == RED)
{
//如果parent的color為RED，parent一定不是根節點，且祖父節點color為BLACK
Node* grandparentnode = parent->_parent;//grandparentnode->_color = BLACK;
if (parent == grandparentnode->_left)
{
Node* unclenode = grandparentnode->_right;//叔叔節點uncle
if (unclenode && (unclenode->_color == RED))//uncle不為空，且uncle->color為RED
{
parent->_color = BLACK;
unclenode->_color = BLACK;
grandparentnode->_color = RED;
cur = grandparentnode;
parent = cur->_parent;
}
else//uncle為空，或uncle->color為BLACK
{
if (cur == parent->_right)
{
RotateL(parent);
std::swap(parent, cur);
}
RotateR(grandparentnode);
parent->_color = BLACK;
grandparentnode->_color = RED;
break;
}
}
else//parent == grandparent->_right
{
Node* unclenode = grandparentnode->_left;
if (unclenode && (unclenode->_color == RED))//uncle存在，且color為 RED
{
parent->_color = BLACK;
unclenode->_color = BLACK;
grandparentnode->_color = RED;
cur = grandparentnode;
parent = cur->_parent;
}
else//uncle不存在，或uncle->color為黑色
{
if (cur == parent->_left)
{
RotateR(parent);
std::swap(cur,parent);
}
RotateL(grandparentnode);
grandparentnode->_color = RED;
parent->_color = BLACK;
break;
}
}
}
//統一將根節點的顏色變為黑色
_root->_color = BLACK;
return true;
}

    紅黑樹結點的插入到這里就結束了，可以發現的是，我們其實一直在關注的是uncle結點，也就是cur的叔叔結點。這是紅黑樹插入思想里面的一個核心。

    下面，就紅黑樹的基本特征，給出一段檢驗函數，判斷紅黑樹是否滿足要求。

bool IsBalance()
{
if (_root == NULL)
return true;
if (_root->_color == RED)
return false;
int count = 0;
Node* cur = _root;
while (cur != NULL)
{
if (cur->_color == BLACK)
{
count++;
}
cur = cur->_left;
}
int k = 0;
return _IsBalance(_root, count, k);
}
bool _IsBalance(Node* root, const int& count, int k)
{
if (root == NULL)
return true;
if (root != _root && root->_color == RED)
{
if (root->_parent->_color == RED)
{
cout << "連續紅色結點" << root->_key << endl;
return false;
}
}
if (root->_color == BLACK)
k++;
if (root->_left == NULL && root->_right == NULL)
{
if (k == count)
return true;
else
{
cout << "黑色節點不相等" << root->_key << endl;
return false;
}
}
return _IsBalance(root->_left, count, k) \
&& _IsBalance(root->_right, count, k);
}

    紅黑樹的應用遠比AVL樹多，還是一開始我們說的，其實紅黑樹的高度相對來說要比AVL樹高出一些的，但這其實并不影響太多。因為我們的時間復雜度都是在O(log n)附近，當n = 10億時，log(n)也僅僅只有30。但是另一方面，由于紅黑樹要比AVL樹的要求低，所以當我們插入一個結點時，相對來說調整的次數也就少了許多，這個是紅黑樹的優勢。

                                    ------muhuizz整理