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给出的子树中删除Key通过发送 Node (现有的或新的)1) 不包含 Key 2) 仍然是一个格式良好的二叉树。

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

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

• 如果“it”指的是您的代码，那么可能不是。您实际上是在要求某人对您的(无法工作的)代码进行逆向工程，弄清楚您编写代码时对代码的心理概念是什么，并弄清楚如何将其变成有效的东西。 (我没有尝试...)

• 如果“it”指的是 Sedgewick 代码，则参见上文。 (包含您的代码有什么意义？)

<小时/>

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