Code Source - https://github.com/Bibeknam/algorithmtutorprograms/blob/master/data-structures/red-black-trees/RedBlackTree.cpp
y = z;
int y_original_color = y->color;
if (z->left == TNULL) {
x = z->right;
rbTransplant(z, z->right);
} else if (z->right == TNULL) {
x = z->left;
rbTransplant(z, z->left);
} else {
y = minimum(z->right);
y_original_color = y->color;
x = y->right;
if (y->parent == z) {
x->parent = y; \\ [1] Local Class TNull
} else {
rbTransplant(y, y->right); \\ [2] Losing Y
y->right = z->right;
y->right->parent = y;
}
rbTransplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color; \\ [3] Need of Recoloring
}
Questions
y->right
is a TNull
) Within this class function, TNull is a local pointer simply passed to x
; isn't changing the parent
of x
also change the parent of the local TNull
?z
is not a direct children. Later it will be placed at z
's location. Won't this segment only pivot y->right / x
until it reaches z
's location, instead of y / minimum
?fixDelete()
function call, why is this needed?Please bear with me, I'm slow in this kind of stuff and I'm really at my wits' end. This is the first time I'm asking here. Thank you.
On your questions