这是BST Hibbard删除错误的代码吗？

Question

我正在读普林斯顿大学的Sedgewick和Wayne写的《算法》一书，它为BSTMaps提供了一种BST删除方法。

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;
}

原来是一个著名的算法，叫做急切希伯德删除，也在这个环节中呈现。

由于代码是用Java编写的，所以我尝试自己实现它。但由于引用问题，它会导致无限循环。如果x指向后续节点，并且x.left被更新，那么deleteMin方法不仅会删除原始节点，还会通过新的左分支删除树的另一半的最小值。

这可以通过复制min（t.right）的值和键来绕过，而不只是使用“=”，并且不需要t节点。

但我的问题是：这本书（和网页）中的代码是否完全错了？很难想象，因为这是一本第四版的畅销书。

下面的示例再现了这个问题。

BSTMap<String, Integer> 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");

这棵树原来是：

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

删除（我代码中的“删除”）应该在删除“Hello”时促进“zebra”。但是在将“zebra”.↓分配给“cat”后，deleteMin方法会删除“cat”而不是“zebra”本身，导致“zebra”指向自己。

Answer 1

不，Sedgewick和Wayne代码没有错。我绝对喜欢这本书，但有时它的代码对我的口味来说有点蹩脚。在他们的实现中，他们希望跟踪每个节点的“大小”，因此他们调用deleteMin（...）来重新计算这个属性。他们对min（...）的实现也是正确的，因为这种方法递归地找到从根节点开始的具有最小键的节点。我将复制我的Hibdard删除实现并附上一些注释。如果我的实现无法工作，可能您在构建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;

}