java有人能解释二进制搜索树中的递归delete（）并帮我转换它吗

Question

我有Sedgewick的书《算法》中的代码：

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

基本上，我想知道递归在树中是如何工作的，因为我想将这个方法转换为在找到节点时旋转它，直到它变成一片叶子，然后删除它

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 is a leaf delete it
            //if has one child rotate it
            //if it has two children compare some value
            //of the children choose the bigger and rotate

        } 
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

private Node rotateLeft(Node h)
{
    Node x = h.right;
    h.right = x.left;
    x.left = h;

    return x;
}

private Node rotateRight(Node h)
{
    Node x = h.left;
    h.left = x.right;
    x.right = h;

    return x;
}

我尝试了一些方法，但它抛出了一个空指针异常。我已经试着反复做了，但是 指向节点的指针没有更新，因此我丢失了树。有人能告诉我它是如何工作的，这样我就可以正确地修改它了吗

Answer 1

And basically i want to know how the recursion works in the tree

递归“工作”的方式与它在任何其他算法中的工作方式相同。方法最终会直接或间接地调用自身。。。并且在这个过程中做了一些有用的事情

在这种特殊情况下，有用的是Node delete(Node, Key)通过传递一个Node（现有的或新的），1）不包含Key，2）仍然是一个格式良好的二叉树，从输入Node给出的子树中移除键

一个完整的解释将是漫长而乏味的，可能需要创建大量显示树前后的图形。对如此回答的期望太高了¹。如果您对代码的特定部分有特定的问题，您需要询问它。。。具体地说

... so can someone show me how it works so i can modify it properly?

• 如果“it”是指您的代码，那么可能不是。你实际上是在要求某人对你的（非工作的）代码进行反向工程，弄清楚你在编写代码时对代码的想法是什么，并弄清楚如何将它转化为工作的东西。（我没有尝试…）

• 如果“it”是指Sedgewick代码，请参见上文。（包含代码有什么意义？）

---

^{1-如果有人花时间为你这样做，你很可能会回来说“事实上，我已经理解了其中的大部分。我没有明白的一件事是……”}