C++红黑树的完整实现
#include <iostream> using namespace std; typedef enum Color { RED, BLACK, }Color; template<typename Type> struct RbNode { Color color; Type data; RbNode<Type> *parent; RbNode<Type> *left; RbNode<Type> *right; RbNode(Type d=Type()):left(NULL),right(NULL),parent(NULL),data(d),color(RED){} }; template<typename Type> class RbTree { public: RbTree() { Root = NULL; Nul = NULL; Start = BuyNode(); Start->color = BLACK; } void Insert(Type ar[],int n) { for(int i=0;i<n;i++) { _Insert(Root,ar[i]); } } private: bool _Insert(RbNode<Type> *p,int val) { RbNode<Type> *pr = NULL; while(p!=NULL) { if(p->data == val)return false; pr = p; if(p->data > val)p=p->left; else p=p->right; } if(pr==NULL) { Root = BuyNode(val); p = Root; } else p = BuyNode(val); if(pr!=NULL) { if(pr->data>val) pr->left = p; else pr->right = p; p->parent = pr; } Init_Set(Root,p); Root->color = BLACK; } RbNode<Type>* BuyNode(Type d=Type()) { RbNode<Type> *s = new RbNode<Type>(d); return s; } bool Init_Set(RbNode<Type> *&t,RbNode<Type> *&p) { p->color = RED; if(p->parent!=Nul && p->parent->color == RED) { if(p->parent->parent->left==p->parent) { if(p->parent->left==p) { RbNode<Type> *s = p->parent->parent->right; if(s!=Nul && s->color==RED) { p->parent->color = BLACK; s->color = BLACK; p=s->parent; Init_Set(Root,p); } else { p->parent->color = BLACK; p->parent->parent->color=RED; p = p->parent->parent; StateR(Root,p); } } else { RbNode<Type> *s = p->parent->parent->right; if(s!=Nul && s->color==RED) { p->parent->color = BLACK; s->color = BLACK; p=s->parent; Init_Set(Root,p); } else { p = p->parent; StateL(Root,p); Init_Set(Root,p->left); } } } else { if(p->parent->right==p)// \ s { RbNode<Type> *s = p->parent->parent->left; if(s!=Nul && s->color == RED) { p->parent->color = BLACK; s->color = BLACK; p = s->parent; Init_Set(Root,p); } else { p->parent->color = BLACK; p->parent->parent->color=RED; p=p->parent->parent; StateL(Root,p); } } else { RbNode<Type> *s = p->parent->parent->left; if(s!=Nul && s->color==RED) { p->parent->color = BLACK; s->color = BLACK; p=s->parent; Init_Set(Root,p); } else { p = p->parent; StateR(Root,p); Init_Set(Root,p->right); } } } } } void StateL(RbNode<Type> *&t,RbNode<Type> *&p) { int flogs = 0; RbNode<Type> *q = p->right; RbNode<Type> *save = p->parent; if(p==t){ flogs++; } p->right = q->left; if(q->left) q->left->parent = p; q->left = p; p->parent = q; if(save) { if(save->left==p) save->left=q; else save->right=q; q->parent=save; } p = q; if(flogs==1) {Root = p;Root->parent=Start;} } void StateR(RbNode<Type> *&t,RbNode<Type> *&p) { int flogs = 0; RbNode<Type> *q = p->left; if(t==p) flogs++; RbNode<Type> *save = p->parent; p->left = q->right; if(q->right!=NULL) q->right->parent = p; q->right = p; p->parent = q; if(save!=NULL) if(save->left==p) { save->left = q; } else { save->right=q; } q->parent = save; p = q; if(flogs==1){Root = p;Root->parent=Start;} } public: void Printf() { Printf(Root); } void Remove(Type val) { Remove(Root,val); } private: void Remove(RbNode<Type> *t,Type val) { RbNode<Type> *p = t; RbNode<Type> *pr = NULL; while(p!=NULL) { if(p->data == val)break; if(p->data>val)p=p->left; else p=p->right; } if(p==NULL)return ; else { // t = p; if(p->left!=NULL && p->right!=NULL) { pr = p->right; while(pr->left!=NULL)pr=pr->left; t->data = pr->data; p = pr; } pr = p->parent; if(t->left==p) { RbNode<Type> *s = p->right; t->left = s; if(s!=NULL) { s->parent = NULL; s->parent = t; } if(p->color==BLACK) { if(s!=Nul && s->color==RED) { s->color=BLACK; } else if(s!=Nul && s->color==BLACK) { Remove_Set(Root,s); } } else { RbNode<Type> *s = p->right; t->left = s; if(s!=NULL) { s->parent = NULL; s->parent = t; } if(p->color==BLACK) { if(s!=Nul && s->color==RED) { s->color = BLACK; } else if(s!=Nul && s->color==BLACK) { Remove_Set(Root,s); } } } } } Root->color = BLACK; delete p;p=NULL; } void Remove_Set(RbNode<Type> *&t,RbNode<Type> *p) { RbNode<Type> *s = p->parent->right; while(p!=Start && p->color!=RED) { if(s!=NULL) { if(s->color==RED) { s->parent->color = RED; s->color = BLACK; s=s->parent; StateL(Root,s); } else if(s->color==BLACK) { if(s->left!=NULL && s->right!=NULL) { if(s->left->color==BLACK && s->left->right->color==BLACK) { s->color = RED; s->parent->color = BLACK; p = s->parent; } else if(s->right->color==BLACK && s->left->color==RED) { StateR(Root,s); } else if(s->right->color==RED && s->color==BLACK) { s=s->parent; StateL(Root,s); p = s; } } } } } } void Printf(RbNode<Type> *&t) { if(t==NULL)return ; else { Printf(t->left); cout<<t->data<<":"<<t->color<<"\t"; Printf(t->right); } } RbNode<Type> *Start; RbNode<Type> *Root; RbNode<Type> *Nul; }; int main() { int a[]={0,2,3,1,5,10,15,7,8}; RbTree<int> rb; rb.Insert(a,9); rb.Remove(5); rb.Printf(); return 0; }