Is this code for BST Hibbard deletion buggy?

Question

I am reading the book Algorithms by Sedgewick and Wayne of Princeton, and it presents a BST deletion method for BSTMaps.

public void deleteMin()
{
    root = deleteMin(root);
}

private Node deleteMin(Node x)
{
    if (x.left == null) return x.right;
    x.left = deleteMin(x.left);
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

public void delete(Key key)
{
    root = delete(root, key);
}

private Node delete(Node x, Key key)
{
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp < 0) x.left = delete(x.left, key);
    else if (cmp > 0) x.right = delete(x.right, key);
    else
    {
        if (x.right == null) return x.left;
        if (x.left == null) return x.right;
        Node t = x;
        x = min(t.right); // <----This would cause infinite loop
        x.right = deleteMin(t.right);
        x.left = t.left;
    }
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

It turns out to be a famous algorithm called eager Hibbard deletion, which is also presented in this link.

As the code is in Java, I tried to implement it myself. But it causes infinite loop because of a reference problem. If x is pointed to the successor, and x.left is updated, then the deleteMin method will not only delete the original node, but go through the new left branch to delete the min of the other half of the tree.

This can be bypassed by copying the values and keys of min(t.right) instead of just use '=', and the t node would be unnecessary.

But my question is: is the code in the book (and the webpage) just blatantly wrong? It is hard to conceive since this is a well-received book at its 4th edition.

Here's an example that reproduces the problem.

BSTMap bstmap = new BSTMap<>();
bstmap.put("hello", 5);
bstmap.put("cat", 10);
bstmap.put("fish", 22);
bstmap.put("zebra", 90);
Integer rm = bstmap.remove("dog");
Integer rm2 = bstmap.remove("hello");

The tree was originally:

       ┌────────┐
    ┌──┤ hello  ├────────┐
    │  └────────┘        │
    │                    │
 ┌──┴───┐            ┌───┴────┐
 │ cat  ├─┐          │ zebra  │
 └──────┘ │          └────────┘
      ┌───┴───┐
      │ fish  │
      └───────┘

The delete ('remove' in my code) is supposed to promote 'zebra' when 'hello' is deleted. But after assigning 'zebra'.left to 'cat', the deleteMin method will delete 'cat' instead of 'zebra' itself, causing 'zebra' to point to itself.

Thanks for the help, everyone. I think I find the problem. I thought I got exactly the same code, but actually

x.right = deleteMin(t.right);
x.left = t.left;

I got these two lines in reverse, which caused the problem.

It's unbelievable that I looked at the code for so long and did not find the difference. I changed the variable names even...

user_469201 · Answer

No, Sedgewick and Wayne code is not wrong. I absolutely love this book, but sometimes it's code is a little bit criptic for my taste. In their implementation they want to keep track of the "size" of each node, so they call deleteMin(...) to recalculate this attribute. Their implementation of min(...) is correct too, because this method recursively find the node with the minimal key starting from a root node. I will copy my implementation of Hibdard deletion with some comments. If my implementation fails to work, probably you have problems in the way you are constructing your BST.

public void delete( Key key ) throws IllegalArgumentException {

    if ( key == null ) {
        throw new IllegalArgumentException( "argument to delete() is null" );
    }
    
    root = delete( root, key );

}

private Node delete( Node node, Key key ) {
    
    if ( node != null ) {
        
        Node temp;
        int comp = key.compareTo( node.key );

        // found the node with the key to remove
        if ( comp == 0 ) {
            
            size--;  // symtable size
            
            // the node does not have any childrem
            // so, in it's place it will be a 
            // null reference
            if ( node.left == node.right ) {

                return null;

            // the node does not have a left child
            // the node that will replace it will
            // be its right child
            } else if ( node.left == null ) {

                temp = node.right;
                node.right = null;
                return temp;

            // the node does not have a right child
            // the node that will replace it will
            // be its left child
            } else if ( node.right == null ) {

                temp = node.left;
                node.left = null;
                return temp;

            // the node have left and right childrem
            } else {

                // marks the node that will replace the removed node
                temp = node.right;
                
                // marks the same node to perform the search
                // for the minimal node
                Node min = temp;

                // searches for the minimal node
                while ( min.left != null ) {
                    min = min.left;
                }
                
                // the left subtree of the node that will
                // be removed is now the left subtree of the
                // minimal node
                min.left = node.left;

                // detaches the left and right subtrees of the
                // node that will be deleted
                node.left = null;
                node.right = null;

                // return the node that was greater than the 
                // node that was removed
                return temp;

            }

        } else if ( comp < 0 ) {
            node.left = delete( node.left, key );
        } else { // comp > 0
            node.right = delete( node.right, key );
        }
        
    }
    
    return node;

}

Is this code for BST Hibbard deletion buggy?

1 Answers