Deletion in a Binary search Tree

Question

The teacher explained to us this algorithm for deleting a node in a binary search tree, but I can't understand how it works when the node to be deleted has only one child (I already know how it works theoretically).

Algorithm:

abc_delete(T, z) // z is the node that must be eliminated 
{
        if((z.left == NULL) && (z.right == NULL))
                y = z;
        else
                y = abr_successor(z);

        if(y.left != NULL)
                    x = y.left;
        else
                    x = y.right;

        if(x != NULL)
                x.p = y.p;

        if(y.p == NULL)
                T.root = x;
        else
        {
                if(y == (y.p).left)
                        (y.p).left = x;
                else
                        (y.p).right = x;
        }

        if(y != z)
                z.key = y.key;
        return y;
}

abr_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x == y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

For example, I want to delete the node number $7$:

But, shouldn't the end result be this?

Answer 1

You choice is certainly correct.

However, there is nothing wrong with your teacher's code, either. Here is an excerpt from CLRS.

The operations of insertion and deletion cause the dynamic set represented by a binary search tree to change. The data structure must be modified to reflect this change, but in such a way that the binary-search-tree property continues to hold.

We certainly prefer the operation be made in the easiest way or the fastest way. However, there is no requirement the modification must be made in the easiest way or even in any easy way. Nor does it require that the modification be made in the fastest way or even in any fast way. All it requires that the operation of deletion should produce another binary search tree that has all nodes from the given binary search tree without that specific node (and no more nodes). How those remaining nodes form a binary-search-tree is completely free of restraints.

Your teacher's code, on the other hand, is probably the shortest clear code that does the job. The more I study it, the more ingenuity I find.

Answer 2

Your drawing is the correct solution, however ur parsing to ur teacher code is not accurate (u mis interepreted the code)

When I first saw ur Q I didn't read the code thoroughly & I thought (from the 1st pic/drawing) ur teacher is performing a delete operation for a special kind of BST that has extra conditions than the relative order, but this is not the case

When deleting from a BST (trying to follow ur code variables, Z is the node to be deleted)

If Z is a leaf node (no children) just replace the parent pointer to it with NULL

if Z has 1 child (whether left or right doesn't matter) make the parent pointer points to its only child

That's very simple coding, in a semi pseudo code

If (Z.left == NULL) { Physical_Delete(Z, Zright); return(); //either we have only right subtree or none }

// Here we r sure there is a left subtree

If (Z. right == NULL) { Physical_Delete(Z, Z.left); return(); }

//physical_Delete has the replacement as the 2nd parameter, all the loops in ur teacher code is to find out what is it incase we have two subtrees

If Z has 2 children, then u have to elect one of them to take its place, and here comes ur teacher's code (not in the previous case)

In ur pic imagine u r deleting "5" this long code is for adjusting the remaining subtree of its 2 children (how to link 7 & 3 & their children to node 12 keeping the BST constrain)

If u need detailed tracing we may do that, but only if u found this helpful as a start