i checked google and most of the rbt delete implementation are using successor
is there a way to do it without the successor???
he told the class to follow the book "intro to algorithms" but he wrote his version w/o even looking at the book and he wrote his answer w/o successor...
ive implemented my own with successor but my professor is forcing the class to do it w/o it
heres my codes
Code:
void deleteRb(string data)
{
treeNode* y;
treeNode* z = searchDelete(data); //searchDelete finds where the node is to be deleted
treeNode* x;
if ( z->left == NULL || z->right == NULL )
y=z;
else
y = treeSuccessor(z);
if (y->left != NULL)
x= y->left;
else
x= y->right;
x->parent = y->parent;
if ( y->parent == NULL)
root = x;
else if (y = y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
if ( y != z)
z->data = y->data;
if ( y->red = false)
deleteFixUp(x);
}
^the delete()
Code:
treeNode* treeSuccessor(treeNode* x)
{
if (x->right != NULL)
return treeMinimum (x->right);
treeNode* y;
y = x->parent;
while ( y != NULL)
{
if ( x == y->right)
{
x=y;
y=y->parent;
}
return y;
}
}
^successor()
can someone help me...