Sedgewick《算法》中BST Hibbard删除代码是否存在bug？

背景 #

我在读普林斯顿大学Sedgewick与Wayne所著的经典教材《算法》（第4版）时，参考书中BSTMap的二叉搜索树删除实现写代码，该实现是经典的eager Hibbard删除算法，公开技术资料里也广泛使用同款逻辑。
书中给出的Java实现代码如下：

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);
        x.right = deleteMin(t.right);
        x.left = t.left;
    }
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

问题现象 #

自己复现代码时触发了无限循环，一开始我以为是引用逻辑有缺陷：如果x指向后继节点后先更新x.left指针，deleteMin方法就不会只删除原右子树的最小节点，反而会顺着新挂上去的左分支往下遍历，错删树另一侧的最小节点。当时我还找到个绕过方案：复制min(t.right)节点的键和值，不直接做引用赋值，这种写法也不需要保留临时节点t。
我当时特别疑惑：这本口碑极好、更新到第4版的经典教材，还有官方配套网页上的参考代码，难道会有这么明显的错误？
用来复现问题的测试代码如下：

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（我的实现里对应remove方法）时，预期是把zebra节点提升为新的根节点。但如果先给zebra的left指针赋值指向cat子树，再调用deleteMin方法，就会错删cat节点而不是原右子树的最小节点，最后导致zebra节点出现自引用，触发无限循环。

根因定位 #

最后排查清楚了，教材的代码本身没毛病，问题出在我自己写代码时把两行核心赋值代码的顺序写反了：

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

必须先做完后继节点右子树的删除最小节点操作，再给后继节点挂上原节点的左子树，顺序写反就会触发前面说的引用遍历错误。我之前反复核对代码好久都没发现这个顺序差，中间还改过变量名，整个排查过程花了不少时间。

内容的提问来源于stack exchange，提问作者zf Zhang