1
$\begingroup$

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$: enter image description here

But, shouldn't the end result be this? enter image description here

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks, I thought I was misinterpreting the code. However, it is not clear to me what this instruction exactly does: x.p = y.p; $\endgroup$
    – Shyvert
    May 5 '20 at 17:02
  • 1
    $\begingroup$ x.p = y.p means, literally, assigning the parent of y to be the parent of x. The intention is to establish a parent-child relationship between y.p and x that replaces the current parent-child relationship between y.p and y, thus replacing y with x. Since x is a child of y, the effect is the same as moving the subtree rooted at x one level up, to directly under its (previous) grandparent, the parent of y. $\endgroup$
    – John L.
    May 5 '20 at 18:57
  • 1
    $\begingroup$ Note that a parent-child relation is a two-way relation. The operation x.p = y.p tells x to identify y.p as its parent. The next operation should tell y.p to identify x as its child, either left child or right child. That is what we see next, (y.p).left = x or (y.p).right = x. The order to write/execute these two operations can be reversed. $\endgroup$
    – John L.
    May 5 '20 at 18:57
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.