c++data-structuresred-black-tree

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


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

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.


Solution

  • On your questions