while x!=root[T] and color[x]=BLACK
do if x=left[p[x]]
then w <- right[p[x]]
if color[w]=RED
then color[w] <- BLACK
color[p[x]] <- RED
LEFT-ROTATE(T,p[x])
w <- right[p[x]]
if color[left[w]]=BLACK and color[right[w]]=BLACK
then color[w] <- RED
x <- p[x]
else
then if color[right[w]]=BLACK
then color[left[w]] <- BLACK
color[w] <- RED
RIGHT-ROTATE(T,w)
w <- right[p[x]]
color[w] <- color[p[x]]
color[p[x]] <- BLACK
color[right[w]] <- BLACK
LEFT-ROTATE(T,p[x])
x <- root[T]
else (same as then clause with “right” and “left” exchanged)
color[x] <- BLACK
附录：
C++代码
#includeusing namespace std; typedef enum col{RED, BLACK} col; template class RBNode { public: RBNode(T k, RBNode *l=NULL, RBNode *r=NULL, RBNode *p=NULL ):key(k),left(l),right(r),parent(p){} ~RBNode(); T key; RBNode *left, *right, *parent; col color; }; template class RBTree { public: RBTree(RBNode *r=NULL):root(r){ NIL=new RBNode (-1); NIL->color=BLACK; root->color=BLACK; root->left=NIL; root->right=NIL; root->parent=NIL; } ~RBTree(); void inorder(RBNode *); RBNode * search(T k, RBNode *x); RBNode * min(RBNode *x); RBNode * max(RBNode *x); RBNode * successor(RBNode *x); void rightRotate(RBNode *z); void leftRotate(RBNode *z); void Insert(RBNode *z); void Insert_fixup(RBNode *x); void Delete(RBNode *z); void Delete_fixup(RBNode *x); RBNode *root; RBNode *NIL; }; template void RBTree ::inorder(RBNode *x) { if(x==NIL) return; inorder(x->left); cout << x->key << " "; inorder(x->right); } template RBNode * RBTree ::search(T k, RBNode *x) { RBNode *p=x; while(p!=NIL && p->key!=k) { if(k < (p->key)) p=p->left; else p=p->right; } return p; } template RBNode * RBTree ::min(RBNode *x) { RBNode *p=x; if(p==NIL) return NIL; while(p->left!=NIL) p=p->left; return p; } template RBNode * RBTree ::max(RBNode *x) { RBNode *p=x; if(p==NIL) return NIL; while(p->right!=NIL) p=p->right; return p; } template RBNode * RBTree ::successor(RBNode *x) { if(x->right!=NIL) return min(x->right); RBNode *y=x; RBNode *p=x->parent; while(p!=NIL && p->right==y) { y=p; p=p->parent; } return p; } template void RBTree ::leftRotate(RBNode *z) { RBNode *y=z->right; if(y->left!=NIL) y->left->parent=z; y->parent=z->parent; if(y->parent==NIL) root=y; else if(z==z->parent->left) z->parent->left=y; else z->parent->right=y; z->right=y->left; z->parent=y; y->left=z; } template void RBTree ::rightRotate(RBNode *z) { RBNode *y=z->left; y->parent=z->parent; if(y->parent==NIL) root=y; else if(z==z->parent->left) z->parent->left=y; else z->parent->right=y; if(y->right!=NIL) y->right->parent=z; z->left=y->right; y->right=z; z->parent=y; } template void RBTree ::Insert(RBNode *z) { RBNode *y=root; RBNode *x; while(y!=NIL) { x=y; if(z->key < y->key) y=y->left; else y=y->right; } z->parent=x; if(x==NIL) root=z; else if(z->key < x->key) x->left=z; else x->right=z; z->color=RED; z->left=NIL; z->right=NIL; Insert_fixup(z); } template void RBTree ::Insert_fixup(RBNode *z) { RBNode *x=z; RBNode *w; while(x->parent->color==RED) { if(x->parent==x->parent->parent->left) { w=x->parent->parent->right; if(w->color==RED) { w->color=BLACK; x->parent->color=BLACK; x->parent->parent->color=RED; x=x->parent->parent; } else { if(x==x->parent->right) { x=x->parent; leftRotate(x); } x->parent->color=BLACK; x->parent->parent->color=RED; rightRotate(x->parent->parent); } } else { w=x->parent->parent->left; if(w->color==RED) {