完整源代碼:?http://download.csdn.net/detail/hanqing280441589/8450041

?

紅黑節點設計與實現

template <typename Comparable> class RedBlackNode {friend class RedBlackTree<Comparable>; //所有的成員都是private private:RedBlackNode(const Comparable &theElement = Comparable(),RedBlackNode *theLeft = NULL,RedBlackNode *theRight = NULL,int theColor = RedBlackTree<Comparable>::BLACK): element(theElement), left(theLeft), right(theRight), color(theColor) {}//數據成員Comparable element;RedBlackNode *left;RedBlackNode *right;int color; };

紅黑樹的設計

template <typename Comparable> class RedBlackTree { //類型定義 public:typedef RedBlackNode<Comparable> Node;enum COLOR {RED, BLACK};//開放的接口 public:explicit RedBlackTree(const Comparable & negInf);~RedBlackTree();void insert(const Comparable &x);bool isEmpty() const;void makeEmpty();Gref<Comparable> find(const Comparable & x) const;Gref<Comparable> findMin() const;Gref<Comparable> findMax() const;//實用的私有操作 private://自動處理: [1]重新染色; [2]:自動旋轉void handleReorient(const Comparable &item);//自動旋轉函數(返回旋轉以后的theParent子樹的根)Node *rotate(const Comparable & item, Node *theParent);/**單旋轉**///向右轉(帶著右孩子)void rotateWithLeftChild(Node *& k2);//向左轉(帶著左孩子)void rotateWithRightChild(Node *& k1);//遞歸刪除所有節點void reclainMemory(Node *t) const;private://指向紅黑樹的頭(偽根節點)Node *header;Node *nullNode;//在insert時使用Node *current; //當前節點Node *parent; //父節點Node *grand; //祖父節點Node *great; //曾祖父節點 };

紅黑樹的實現

//紅黑樹構造函數 template <typename Comparable> RedBlackTree<Comparable>::RedBlackTree(const Comparable & negInf) {nullNode = new RedBlackNode<Comparable>;//nullNode 的左右子節點都指向自己nullNode->left = nullNode->right = nullNode;header = new RedBlackNode<Comparable>(negInf, nullNode, nullNode); } //紅黑樹析構函數: 完善版本 template <typename Comparable> RedBlackTree<Comparable>::~RedBlackTree() {if (!isEmpty())makeEmpty();delete nullNode;delete header; } /**紅黑樹最復雜的操作 ** insert **/ template <typename Comparable> void RedBlackTree<Comparable>::insert(const Comparable &x) {current = parent = grand = great = header;nullNode->element = x;while (current->element != x){//讓祖父成為曾祖父, 父親成為祖父, 自己成為父親//每個節點都成長一輩great = grand;grand = parent;parent = current;current = (x < current->element) ? current->left : current->right;//處理1. 如果current節點有兩個紅色孩子if ((current->left->color == RED) && (current->right->color == RED))handleReorient( x );}//如果樹中包含相同的元素if (current != nullNode)throw DuplicateItemException();current = new Node(x, nullNode, nullNode);if (x < parent->element)parent->left = current;elseparent->right = current;//+ 處理2. 如果新插入的節點破壞了紅黑規則handleReorient( x ); } /**自動平衡函數:[1]重新染色[2]自動旋轉 */ template <typename Comparable> void RedBlackTree<Comparable>::handleReorient(const Comparable & item) {// 將current節點染成紅色current->color = RED;// 將current的left和right節點染成黑色current->left->color = current->right->color = BLACK;// 如果current節點的父節點也是紅的 -> 單旋轉 or 雙旋轉if( parent->color == RED ){//則將其祖父(爺爺)的顏色染成紅色grand->color = RED;//然后判斷新插入的節點是否是內部孫子?//如果是, 則增加一次旋轉->構成雙旋轉//if注釋: 如果該節點小于爺爺, 小于爸爸, 這兩種情況不同時滿足//則說明其是爺爺的內孫子if( (item < grand->element) != (item < parent->element) ){// 則依grand(祖父)節點進行旋轉parent = rotate( item, grand ); // Start double rotate}// 則依great(曾祖父)節點進行旋轉current = rotate( item, great );//令當前節點為黑色current->color = BLACK;}//根節點必須是黑色的header->right->color = BLACK; // Make root black } // 自動判斷并進行旋轉函數 template <typename Comparable> typename RedBlackTree<Comparable>::Node * RedBlackTree<Comparable>::rotate(const Comparable &item,Node *theParent ) {//位于theParent的左子樹if( item < theParent->element ){//如果為真, 則說明theParent->left有左孩子,//否則, 有右孩子item < theParent->left->element ?//如果theParent左邊有一棵子樹, 則以theParent->left//為軸, 向右轉rotateWithLeftChild( theParent->left ) : // LL//如果theParent右邊有一棵子樹, 則以theParent->left//為軸, 向左轉rotateWithRightChild( theParent->left ) ; // LRreturn theParent->left; //返回左子樹}else //位于右子樹{//如果為真, 則說明theParent->right有左孩子,往右轉//否則, 有右孩子, 往左轉item < theParent->right->element ?rotateWithLeftChild( theParent->right ) : // RLrotateWithRightChild( theParent->right ); // RRreturn theParent->right; //返回右子樹} } /** 右(單)旋轉 **/ template <typename Comparable> void RedBlackTree<Comparable>::rotateWithLeftChild(Node *& k2) {Node *k1 = k2->left;k2->left = k1->right;k1->right = k2;k2 = k1; } /** 左(單)旋轉 **/ template <typename Comparable> void RedBlackTree<Comparable>::rotateWithRightChild(Node *& k1) {Node * k2 = k1->right;k1->right = k2->left;k2->left = k1;k1 = k2; } template <typename Comparable> Gref<Comparable> RedBlackTree<Comparable>::find(const Comparable &x) const {if (isEmpty())return Gref<Comparable>();nullNode->element = x;Node *iter = header->right;while (true){if (x < iter->element)iter = iter->left;else if (x > iter->element)iter = iter->right;//如果 x == iter->elementelse if (iter != nullNode)return Gref<Comparable>(iter->element) ;elsereturn Gref<Comparable>();} } template <typename Comparable> Gref<Comparable> RedBlackTree<Comparable>::findMax() const {if (isEmpty())return Gref<Comparable>();Node *iter = header->right;while (iter->right != nullNode){// 一直向右走iter = iter->right;}return Gref<Comparable>(iter->element); } template <typename Comparable> Gref<Comparable> RedBlackTree<Comparable>::findMin() const {if (isEmpty())return Gref<Comparable>();Node *iter = header->right;while (iter->left != nullNode){// 一直向左走iter = iter->left;}return Gref<Comparable>(iter->element); } template <typename Comparable> bool RedBlackTree<Comparable>::isEmpty() const {if (header->right == nullNode)return true;return false; } template <typename Comparable> void RedBlackTree<Comparable>::makeEmpty() {reclainMemory(header->right);header->right = nullNode; } template <typename Comparable> void RedBlackTree<Comparable>::reclainMemory(Node *t) const {//t == t->left的時候, 是當t==nullNode時if (t != t->left){reclainMemory(t->left);reclainMemory(t->right);delete t;} }

Gref包裝器的設計與實現

template <typename Object> class Gref { public:Gref(): obj(NULL) {}explicit Gref(const Object &x): obj(& x) {}const Object &get() const{if (isNull())throw NullPointerException();elsereturn * obj;}bool isNull() const{if (obj == NULL)return true;return false;}private:const Object * obj; };

Exception的設計與實現

class DSException { public:typedef std::string string;public:DSException(const string &_msg = string()):message(_msg) {}virtual ~DSException() {}virtual string what() const{return message;}virtual string toString() const{return "Exception " + message;}private:string message; };class DuplicateItemException : public DSException { public:DuplicateItemException(const string &_msg = string()): DSException(_msg) {} };class NullPointerException : public DSException { public:NullPointerException(const string &_msg = string()): DSException(_msg) {} };

測試代碼

int main() {const int NEG_INF = -999999;RedBlackTree<int> tree(NEG_INF);tree.insert(50);tree.insert(40);tree.insert(30);tree.insert(10);tree.insert(55);tree.insert(88);tree.insert(200);tree.insert(100);tree.insert(70);tree.insert(80);tree.insert(650);Gref<int> g = tree.findMin();cout << "Min = " << g.get() << endl;g = tree.findMax();cout << "Max = " << g.get() << endl;int searchVal;while (cin >> searchVal){g = tree.find(searchVal);if (g.isNull())cout << "not found" << endl;elsecout << g.get() << " founded" << endl;}tree.makeEmpty();if (tree.isEmpty()){cout << "is Empty" << endl;}else{cout << "not Empty" << endl;}return 0; }

總結

以上是生活随笔為你收集整理的数据结构拾遗(3) --红黑树的设计与实现(下)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。