Questions regarding Red-Black Tree Deletion (z has 2 children) (pre-fixDelete)

Question

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

• 1. Local Class TNull - (In case 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?
• 2. Losing Y - This section is meant to be executed in case the minimum in right subtree of 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?
• 3. Need of Recoloring - Iirc, recoloring will also happen in the later 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.

Answer 1

On your questions

• Yes that can happen, TNull's parent is set and the authors remark that this is a deliberate design choice which they exploit.
• y is moving to where z is and this just fixes y so its pointers are what z had. s
• No. Essentially when the node to be deleted has 2 children, you find the successor or predecessor node (which has to have 0 or 1 child) and swap the nodes. You then delete the node at the successor or predecessor node position. The predecessor or successor node swapped, preserves the tree ordering. But the important thing is in swapping the nodes, the colour is not swapped, it must be preserved so the red-black tree properties are still correct. This is what y_original_color is for.