C++紅黑樹的實現
最近在閱讀SGI STL源代碼，其中紅黑樹的實現比較有技術含量，但標準庫里面是捆綁了其中的allocator, iterator(Rb_tree專用的)，使用很多模板變量，實現對多種數據類型的處理。這些情況對于有較扎實C++基礎的人來說不成問題，但對于一般 初學算法，而又沒有太好的C++基礎的人來說有點困難。并且SGI STL中的實現代碼寫得很精巧，節省代碼，也高效運行，但會使得功能不夠深厚的人讀起來還是比較費勁。
這里使用簡單的int類型節點，實現紅黑樹的創建、插入及相關內部操作的功能。目前代碼中刪除節點及其內部操作功能沒有實現。
關于紅黑樹的五個條件（有的書上說四個，內容是等價的）以及插入節點后的調整，可以參考侯捷先生的《STL源碼剖析》，里面有詳細的原理介紹。也可以參考 《算法導論》。下面代碼可以直接使用運行，經測試正確，代碼不追求在物理運行上的效率，盡量把算法步驟表現在代碼里，不作過多合并優化，并且已經加上不少 注釋，方便閱讀。
My_Rb_Tree.h
#pragma oncedefine 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;
}; </pre>
My_Rb_Tree.cpp/**/ / @brief Red-Black tree implement. / @author sail2010@163.com / @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; }</pre>