最近在閱讀SGI STL源代碼，其中紅黑樹的實現比較有技術含量，但標准庫裡面是捆綁了其中的allocator, iterator(Rb_tree專用的)，使用很多模板變量，實現對多種數據類型的處理。這些情況對於有較扎實C++基礎的人來說不成問題，但對於一般初學算法，而又沒有太好的C++基礎的人來說有點困難。並且SGI STL中的實現代碼寫得很精巧，節省代碼，也高效運行，但會使得功能不夠深厚的人讀起來還是比較費勁。
這裡使用簡單的int類型節點，實現紅黑樹的創建、插入及相關內部操作的功能。目前代碼中刪除節點及其內部操作功能沒有實現。
關於紅黑樹的五個條件（有的書上說四個，內容是等價的）以及插入節點後的調整，可以參考侯捷先生的《STL源碼剖析》，裡面有詳細的原理介紹。也可以參考《算法導論》。下面代碼可以直接使用運行，經測試正確，代碼不追求在物理運行上的效率，盡量把算法步驟表現在代碼裡，不作過多合並優化，並且已經加上不少注釋，方便閱讀。
My_Rb_Tree.h
[cpp]
#pragma once
#define node_black true
#define node_red false
typedef bool node_color;
typedef int value_type;
struct node
{
node_color color;
node * left;
node * right;
node * parent;
value_type val;
};
class My_Rb_Tree
{
public:
My_Rb_Tree(void);
~My_Rb_Tree(void);
node * InsertUnique(value_type in_val);
void Erase(node * in_cur);
node * Find(value_type _val);
private:
node * Root();
void Init();
node * CreateNode(value_type _val);
void DestoryNode(node * &_n);
void RotateLeft(node * _cur);
void RotateRight(node * _cur);
void Rebalance(node * _cur);
void RebalanceForErase(node * _cur);
node * Insert(node * in_parent, node * in_cur, value_type in_value);
private:
int node_count;
node * head;
};
My_Rb_Tree.cpp
[cpp] view plaincopy
/************************************************************************/
/* @brief Red-Black tree implement.
/* @author [email protected]
/* @date 2012.10.12
/* @time 16:56:37
/************************************************************************/
#include "StdAfx.h"
#include "My_Rb_Tree.h"
#include "assert.h"
My_Rb_Tree::My_Rb_Tree(void)
:node_count(0),
head(0)
{
Init();
}
My_Rb_Tree::~My_Rb_Tree(void)
{
}
node * My_Rb_Tree::Root()
{
assert(head);
if (!head)
{
return 0;
}
return head->parent;
}
void My_Rb_Tree::Init()
{
head = CreateNode(0);
if (!head)
{
return;
}
head->color = node_red;
head->left = head;
head->right = head;
head->parent = 0;
}
node * My_Rb_Tree::CreateNode(value_type _val)
{
node * n = new node;
n->parent = 0;
n->left = 0;
n->right = 0;
n->color = node_red;
n->val = _val;
return n;
}
void My_Rb_Tree::DestoryNode(node * &_n)
{
delete _n;
_n = 0;
}
void My_Rb_Tree::RotateLeft(node * _cur)
{
node * _root = Root();
node * r = _cur->right;
if (!r)
{
return;
}
if ( _cur ==_root )
{
_root = r;
r->parent = _cur->parent;
_cur->parent->parent = r;
}
else
{
}
r->parent = _cur->parent;
if (_cur->parent->left == _cur)
{
r->parent->left = r;
}
else
{
r->parent->right = r;
}
_cur->right = r->left;
if (r->left)
{
_cur->right->parent = _cur;
}
r->left = _cur;
_cur->parent = r;
}
void My_Rb_Tree::RotateRight(node * _cur)
{
node * _root = Root();
node * l = _cur->left;
if (!l)
{
return;
}
if ( _cur == _root )
{
_root = l;
l->parent = _cur->parent;//head
l->parent->parent = l;// head->parent
}
else
{
l->parent = _cur->parent;
if (l->parent->left == _cur)
{
l->parent->left = l;
}
else
{
l->parent->right = l;
}
}
_cur->left = l->right;
if (l->right)
{
_cur->left->parent = _cur;
}
l->right = _cur;
_cur->parent = l;
}
void My_Rb_Tree::Rebalance(node * _cur)
{
node * _root = Root();
_cur->color = node_red;
if (_cur->parent == head) // _cur is root node
{
_cur->color = node_black;
return;
}
if ( _cur->parent->color == node_black ) // now is balance state.
{
return ;
}
// 根據原來的樹是符合紅黑規則，祖父節點必定為黑色
while( (_cur != Root()) && (_cur->parent->color == node_red)) // 當前節點的父節點為紅色，違反規則
{
if (_cur->parent->parent->left == _cur->parent) // 父節點為左子節點
{
if(_cur->parent->parent->right
&& _cur->parent->parent->right->color == node_red) // 伯父節點為紅
{
// 把父節點和伯父節點變成黑色，祖父節點變成紅色
_cur->parent->parent->right->color=node_black;
_cur->parent->color = node_black;
_cur->parent->parent->color = node_red;
// 因為祖父節點為紅色，需要繼續向上測試是否滿足規則
_cur = _cur->parent->parent;
continue;
}
else // 伯父節點為黑或不存在
{
if ( _cur == _cur->parent->right )
{
// 以父節點為軸，左旋轉後變成兩個左外節點連續為紅。
_cur = _cur->parent;
RotateLeft(_cur/*,_root*/);
}
// 改變顏色，以祖父節點為軸，右旋轉。
_cur->parent->parent->color = node_red;
_cur->parent->color = node_black;
RotateRight(_cur->parent->parent/*,_root*/);
// 此時進入下一次while判斷跳出循環
}
}
else // 父節點為右子節點，依照左子節點的同樣方法解決。
{
if(_cur->parent->parent->left
&& _cur->parent->parent->left->color == node_red) // 伯父節點為紅
{
// 把父節點和伯父節點變成黑色，祖父節點變成紅色
_cur->parent->parent->left->color=node_black;
_cur->parent->color = node_black;
_cur->parent->parent->color = node_red;
// 因為祖父節點為紅色，需要繼續向上測試是否滿足規則
_cur = _cur->parent->parent;
continue;
}
else // 伯父節點為黑或不存在
{
if ( _cur == _cur->parent->left )
{
// 以父節點為軸，右旋轉後變成兩個右外節點連續為紅。
_cur = _cur->parent;
RotateRight(_cur/*,_root*/);
}
// 改變顏色，以祖父節點為軸，左旋轉。
_cur->parent->parent->color = node_red;
_cur->parent->color = node_black;
RotateLeft(_cur->parent->parent/*,_root*/);
// 此時進入下一次while判斷跳出循環
}
}
}//end while
_root->color = node_black;
}
node * My_Rb_Tree::InsertUnique(value_type in_val)
{
node * y = head;
node * x = Root();
bool comp = true;
while( x )//一層一層深入找到合適的插入點
{
y = x;
comp = ( in_val < x->val );
if (in_val == x->val)
{
return 0;
}
x = comp ? x->left : x->right;
}
return Insert(y,x,in_val);
}
node * My_Rb_Tree::Insert(node * in_parent, node * in_cur, value_type in_value)
{
node * new_node = CreateNode(in_value);
if (in_parent == head) // 插入的是根節點
{
head->parent = new_node;
head->left = new_node;
head->right = new_node;
new_node->parent = head;
new_node->color = node_black;
}
else // 插入的是非根節點
{
if ( new_node->val < in_parent->val )
{
in_parent->left = new_node;
if (in_parent == head->left) // 若插入點的父節點是最小節點，更新最小值節點指針
{
head->left = new_node;
}
}
else
{
in_parent->right = new_node;
if (in_parent == head->right)// 若插入點的父節點是最大節點，更新最大值節點指針
{
head->right = new_node;
}
}
new_node->parent = in_parent;
if (in_parent == head)
{
head->parent = new_node;
in_parent->parent = Root();
}
}
Rebalance(new_node/*,head->parent*/);
node_count++;
return new_node;
}
// 未實現，這個函數比較復雜
void My_Rb_Tree::RebalanceForErase(node * _cur)
{
return;
}
// 依賴RebalanceForErase的實現
void My_Rb_Tree::Erase(node * in_cur)
{
return;
}
node * My_Rb_Tree::Find(value_type _val)
{
node * _t = Root();
while(_t)
{
if (_t->val == _val)
{
return _t;
}
else if (_t->val > _val)
{
_t = _t->right;
}
else
{
_t = _t->left;
}
}
return 0;
}
