#ifndef RB_TREE_H #define RB_TREE_H #include <iostream> #include <queue> #include <stack> using namespace std; enum RB_COLOR { BLACK, RED }; // class RB_Tree; // 樹結點 class TreeNode { friend class RB_Tree; public: TreeNode() : color( BLACK ), key( 0 ), parent( NULL ), lchild( NULL ), rchild( NULL ) { } TreeNode( int k ) : color( BLACK ), key( k ), parent( NULL ), lchild( NULL ), rchild( NULL ) { } TreeNode( const TreeNode &rhs ) { color = rhs.color; key = rhs.key; parent = rhs.parent; lchild = rhs.lchild; rchild = rhs.rchild; } ~TreeNode() { parent = 0; lchild = 0; rchild = 0; } int key; // RB_COLOR color; private: RB_COLOR color; // int key; TreeNode *parent; TreeNode *lchild; TreeNode *rchild; }; // 紅黑樹 class RB_Tree { public: RB_Tree() { Nil = new TreeNode(); Nil->parent = Nil; Nil->lchild = Nil; Nil->rchild = Nil; root = Nil; } ~RB_Tree() { delete Nil; Nil = NULL; root = NULL; } // 左旋 void LeftRotate( TreeNode *x ); void RightRotate( TreeNode *x ); void RB_InsertFixUp( TreeNode *z ); void RB_Insert( TreeNode *z ); void RB_Create( int a[], int length ); TreeNode* TreeMinimun( TreeNode *x ); TreeNode* TreeMaxmun( TreeNode *x ); TreeNode* TreeSuccessor( TreeNode *x ); TreeNode* TreePredecessor( TreeNode *x ); TreeNode* TreeSearch( int k ); void RB_DeleteFixUp( TreeNode *x ); TreeNode* RB_Delete( TreeNode *z ); void PrintElem( TreeNode *x ); void LevelOrderTraverse(); void PreOrderTraverse(); void InOrderTraverse(); void PostOrderTraverse(); private: TreeNode *root; TreeNode *Nil; }; #endif
/** * @brief RED_BLACK_TREE * @author An * @data 2013.7.18 **/ #include "RB_Tree.h" void RB_Tree::LeftRotate( TreeNode *x ) { TreeNode *y = x->rchild; x->rchild = y->lchild; if ( y->lchild != Nil ) { y->lchild->parent = x; } y->parent = x->parent; // 設置指向y的指針 if ( x->parent == Nil ) { root = y; // root.key = y.key ?? } else if ( x == x->parent->lchild ) { x->parent->lchild = y; } else { x->parent->rchild = y; } x->parent = y; // 測試這兩條順序 y->lchild = x; } void RB_Tree::RightRotate( TreeNode *x ) { TreeNode *y = x->lchild; x->lchild = y->rchild; if ( y->rchild != Nil ) { y->rchild->parent = x; } y->parent = x->parent; if ( x->parent == Nil ) { root = y; } else if ( x == x->parent->lchild ) { x->parent->lchild = y; } else { x->parent->rchild = y; } x->parent = y; // 測試這兩條順序 y->rchild = x; } void RB_Tree::RB_InsertFixUp( TreeNode *z ) { while ( z->parent->color == RED ) { if ( z->parent == z->parent->parent->lchild ) // z->parent->parent 是否存在??? { TreeNode *y = z->parent->parent->rchild; if ( y->color == RED ) // case 1 { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else // case 2, 3 { if ( z == z->parent->rchild ) //case 2 { z = z->parent; LeftRotate( z ); } z->parent->color = BLACK; //case 3 檢查流程是否正確??? z->parent->parent->color = RED; RightRotate( z->parent->parent ); } } //endif left else { TreeNode *y = z->parent->parent->lchild; if ( y->color == RED ) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if ( z == z->parent->lchild ) { z = z->parent; RightRotate( z ); } z->parent->color = BLACK; z->parent->parent->color = RED; LeftRotate( z->parent->parent ); } } //endif right // root->color = BLACK; // 位置是否正確??? } // endwhile root->color = BLACK; } void RB_Tree::RB_Insert( TreeNode *z ) { TreeNode *y = Nil; TreeNode *x = root; while ( x != Nil ) { y = x; if ( z->key < x->key ) { x = x->lchild; } else { x = x->rchild; } } z->parent = y; if ( y == Nil ) { root = z; // root.key = z.key? } else if ( z->key < y->key ) { y->lchild = z; // } else { y->rchild = z; // } z->lchild = Nil; z->rchild = Nil; z->color = RED; RB_InsertFixUp( z ); } void RB_Tree::RB_Create( int a[], int length ) { for ( int i = 0; i != length; ++i ) { TreeNode *p = new TreeNode( a[ i ] ); RB_Insert( p ); } } TreeNode* RB_Tree::TreeMinimun( TreeNode *x ) // 經過些函數x變了嗎。。。 { if ( x == Nil ) { cout << "ERROR" << endl; return Nil; } while ( x->lchild != Nil ) { x = x->lchild; } return x; } TreeNode* RB_Tree::TreeMaxmun( TreeNode *x ) { if ( x == Nil ) { cout << "ERROR" << endl; return Nil; } while ( x->rchild != Nil ) { x = x->rchild; } return x; } TreeNode* RB_Tree::TreeSuccessor( TreeNode *x ) { if ( x == Nil ) { cout << "ERROR!" << endl; return Nil; } if ( x->rchild != Nil ) { x = x->rchild; while ( x->lchild != Nil ) { x = x->lchild; } return x; } while ( x == x->parent->rchild ) { x = x->parent; } x = x->parent; return x; } TreeNode* RB_Tree::TreePredecessor( TreeNode *x ) { if ( x == Nil ) { cout << "ERROR" << endl; return Nil; } if ( x->lchild != Nil ) { x = x->lchild; while ( x->rchild != Nil ) { x = x->rchild; } return x; } while ( x == x->parent->lchild ) { x = x->parent; } x = x->parent; return x; } TreeNode* RB_Tree::TreeSearch( int k ) { TreeNode *p = root; while ( p != Nil && p->key != k ) { if ( k < p->key ) { p = p->lchild; } else { p = p->rchild; } } if ( p->key == k ) { return p; } else { return Nil; } } void RB_Tree::RB_DeleteFixUp( TreeNode *x ) { while ( x != root && x->color == BLACK ) { if ( x == x->parent->lchild ) { TreeNode *w = x->parent->rchild; if ( w->color == RED ) // case 1 { x->parent->color = RED; w->color = BLACK; LeftRotate( x->parent ); w = x->parent->rchild; } // case 2, 3, 4 if ( w->lchild->color == BLACK && w->rchild->color == BLACK ) // case 2 { w->color = RED; x = x->parent; } else // case 3, 4 { if ( w->lchild->color == RED && w->rchild->color == BLACK ) // case 3 { w->color = RED; w->lchild->color = BLACK; RightRotate( w ); w = x->parent->rchild; } w->color = x->parent->color; x->parent->color = BLACK; w->rchild->color = BLACK; LeftRotate( x->parent ); x = root; } } else { TreeNode *w = x->parent->lchild; if ( w->color == RED ) // case 1 { w->color = BLACK; x->parent->color = RED; RightRotate( x->parent ); w = x->parent->lchild; } //case 2, 3, 4 if ( w->lchild->color == BLACK && w->rchild->color == BLACK ) // case 2 { w->color = RED; x = x->parent; } else { if ( w->lchild->color == BLACK ) { w->color = RED; w->rchild->color = BLACK; LeftRotate( w ); w = x->parent->lchild; } w->color = x->parent->color; x->parent->color = BLACK; w->lchild->color = BLACK; RightRotate( x->parent ); x = root; } } //end if } //end while x->color = BLACK; } TreeNode* RB_Tree::RB_Delete( TreeNode *z ) { TreeNode *y = Nil; TreeNode *x = Nil; if ( z->lchild == Nil || z->rchild == Nil ) { y = z; } else { y = TreeSuccessor( z ); } if ( y->lchild != Nil ) { x = y->lchild; } else if ( y->rchild != Nil ) { x = y->rchild; } x->parent = y->parent; if ( y->parent == Nil ) { x = root; } else if ( y == y->parent->lchild ) { y->parent->lchild = x; } else if ( y == y->parent->rchild ) { y->parent->rchild = x; } if ( y != z ) { z->key = y->key; } if ( y->color == BLACK ) { RB_DeleteFixUp( x ); } return y; } void RB_Tree::PrintElem( TreeNode *x ) { cout << x->key << "(" << x->color << ")" << " "; } void RB_Tree::LevelOrderTraverse() { queue<TreeNode*> q; if ( root != Nil ) { q.push( root ); } while ( !q.empty() ) { TreeNode *x = q.front(); PrintElem( x ); if ( x->lchild != Nil ) { q.push( x->lchild ); } if ( x->rchild != Nil ) { q.push( x->rchild ); } q.pop(); } } void RB_Tree::PreOrderTraverse() { stack<TreeNode*> stk; TreeNode *p = root; while ( p != Nil || !stk.empty() ) { while ( p != Nil ) { PrintElem( p ); stk.push( p ); p = p->lchild; } if ( !stk.empty() ) { p = stk.top()->rchild; stk.pop(); } } } void RB_Tree::InOrderTraverse() { stack<TreeNode*> stk; TreeNode *p = root; while ( p != Nil || !stk.empty() ) { while ( p != Nil ) { stk.push( p ); p = p->lchild; } if ( !stk.empty() ) { PrintElem( stk.top() ); p = stk.top()->rchild; stk.pop(); } } } void RB_Tree::PostOrderTraverse() { stack<TreeNode*> stk; TreeNode *pre = Nil; TreeNode *cur = Nil; stk.push( root ); while ( !stk.empty() ) { cur = stk.top(); if ( ( cur->lchild == Nil && cur->rchild == Nil ) || ( pre != Nil && ( pre == cur->lchild || pre == cur->rchild ) ) ) { PrintElem( cur ); pre = cur; stk.pop(); } else { if ( cur->rchild != Nil ) { stk.push( cur->rchild ); } if ( cur->lchild != Nil ) { stk.push( cur->lchild ); } } } }