Hello, I am making a code for a red black tree. The insert is working but there's a problem in my code when it comes to deleting the node. These are the cases that work:
- Red Leaf
- The node to be deleted only has one child
The other cases don't work.
Here's my code:
Code:bool isRed(node *y) { return (y!=NIL && y->color!='B'); } bool isNull(node *x) { return (x==NULL || x==NIL); } node* TreeSuccessor(node *z) { if(z->rightchild!=NIL) { z=z->rightchild; while(z->leftchild!=NIL) z=z->leftchild; return z; } node *y=z->parent; while(y!=NIL && z==y->rightchild) { z=y; y=y->parent; } return y; } int LeftRotate(node* z) { node *y; y=z->rightchild; z->rightchild=y->leftchild; if (!isNull(y->leftchild)) y->leftchild->parent=z; y->parent=z->parent; if(isNull(z->parent)) root=y; else if(z==z->parent->leftchild) z->parent->leftchild=y; else z->parent->rightchild=y; y->leftchild=z; z->parent=y; return 0; } int RightRotate (node *z) { node *y; y=z->leftchild; z->leftchild=y->rightchild; if(!isNull(y->rightchild)) y->rightchild->parent=z; y->parent=z->parent; if(isNull(z->parent)) root=y; else if(z==z->parent->rightchild) z->parent->rightchild=y; else z->parent->leftchild=y; y->rightchild=z; z->parent=y; return 0; } int DeleteFix(node *z) { node *y; while(z!=root && z->color == 'B') { if(z==z->parent->leftchild) { y=z->parent->rightchild; if(isRed(y)) { y->color='B'; z->parent->color='R'; LeftRotate(z->parent); y=z->parent->rightchild; } if(y->leftchild->color == 'B' && y->rightchild->color == 'B') { y->color='R'; z=z->parent; } else if(y->rightchild->color == 'B') { y->leftchild->color='B'; y->color='R'; RightRotate(y); y=z->parent->rightchild; } y->color=z->parent->color; z->parent->color='B'; y->rightchild->color='B'; LeftRotate(z->parent); z=root; } else { y=z->parent->leftchild; if(isRed(y)) { y->color='B'; z->parent->color='R'; RightRotate(z->parent); y=z->parent->leftchild; } else if(y->leftchild->color == 'B') { y->rightchild->color='B'; y->color='R'; LeftRotate(y); y=z->parent->leftchild; } } y->color=z->parent->color; z->parent->color='B'; y->leftchild->color='B'; RightRotate(z->parent); z=root; } z->color='B'; y = NULL; cout << root->number; return 0; } int DeleteNode() { cout << "\t\t========================================\n"; cout << "\t\t R E D B L A C K T R E E S\n"; cout << "\t\t========================================\n"; cout << "\t\t\t\tD E L E T E\n"; cout << "\t\t----------------------------------------\n"; int number; cout << "Please enter the number to be deleted: "; cin >> number; node *z; for(z=root;z!=NIL;) { if(number < z->number) z=z->leftchild; else if(number > z->number) z=z->rightchild; else if(number==z->number) break; else if (z==NIL) { cout << "No such number exists."; return 0; } else return 0; } node *x; node *y; if (z->leftchild==NIL || z->rightchild==NIL) y=z; else y=TreeSuccessor(z); if(y->leftchild!=NIL) x = y->leftchild; else x=y->rightchild; x->parent=y->parent; if(y->parent==NIL) root=x; else if(y==y->parent->leftchild) y->parent->leftchild=x; else y->parent->rightchild=x; if(y!=z) z->number=y->number; if(y->color=='B') { DeleteFix(x); } return 0; }



LinkBack URL
About LinkBacks


