算法导论学习笔记－第十三章－红黑树(三)
w->color=BLACK; x->parent->color=BLACK; x->parent->parent->color=RED; x=x->parent->parent; } else { if(x==x->parent->left) { x=x->parent; rightRotate(x); } x->parent->color=BLACK; x->parent->parent->color=RED; leftRotate(x->parent->parent); } } } root->color=BLACK; } template
void RBTree
::Delete(RBNode
*z) { RBNode
*y; RBNode
*x; if(z->left==NIL || z->right==NIL) y=z; else y=successor(z); if(y->left!=NIL) x=y->left; else x=y->right; x->parent=y->parent; if(y->parent==NIL) root=x; else if(y==y->parent->left) y->parent->left=x; else y->parent->right=x; if(y!=z) z->key=y->key; if(y->color==BLACK) Delete_fixup(x); } template
void RBTree
::Delete_fixup(RBNode
*z) { RBNode
*x=z; RBNode
*w; while(x->color==BLACK && x!=root) { if(x==x->parent->left) { w=x->parent->right; if(w->color==RED) { w->color=BLACK; x->parent->color=RED; leftRotate(x->parent); w=x->parent->right; } if(w->left->color==BLACK && w->right->color==BLACK) { w->color=RED; x=x->parent; } else { if(w->right->color==BLACK) { w->color=RED; w->left->color=BLACK; w=w->left; rightRotate(w->parent); } w->right->color=BLACK; w->color=w->parent->color; x->parent->color=BLACK; leftRotate(x->parent); x=root; } } else { w=x->parent->left; if(w->color==RED) { w->color=BLACK; x->parent->color=RED; rightRotate(x->parent); w=x->parent->left; } if(w->left->color==BLACK && w->right->color==BLACK) { w->color=RED; x=x->parent; } else { if(w->left->color==BLACK) { w->color=RED; w->right->color=BLACK; w=w->right; leftRotate(w->parent); } w->left->color=BLACK; w->color=w->parent->color; x->parent->color=BLACK; rightRotate(x->parent); x=root; } } } x->color=BLACK; } int main() { RBNode
* a1=new RBNode
(6); RBNode
* a2=new RBNode
(5); RBNode
* a3=new RBNode
(4); RBNode
* a4=new RBNode
(3); RBNode
* a5=new RBNode
(2); RBNode
* a6=new RBNode
(1); RBTree
*T=new RBTree
(a1); T->inorder(T->root); cout << endl; T->Insert(a2); T->Insert(a3); T->Insert(a4); T->Insert(a5); T->Insert(a6); RBNode
*p=T->search(4,T->root); T->Delete(p); T->inorder(T->root); cout << endl; T->Delete(a6); T->Delete(a5); T->Delete(a4); T->Delete(a2); T->inorder(T->root); cout << endl; T->Delete(a1); T->inorder(T->root); }