0

我将 Sedgewick 的名为 Algorithms 的书中的代码作为一种形式：

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

我尝试了一些东西，但它抛出了一个空指针异常。我已经设法迭代地做到了，但是指向节点的指针没有更新，所以我丢失了树。有人可以告诉我它是如何工作的，以便我可以正确修改它吗？

4

1 回答 1

2

基本上我想知道递归在树中是如何工作的

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

在这种特殊情况下，有用的是通过提供（现有的或新的）1）不包含和 2）仍然是格式良好的二叉树Node delete(Node, Key)，从输入给定的子树中删除 Key 。NodeNodeKey

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

...所以有人可以告诉我它是如何工作的，以便我可以正确修改它吗？

  • 如果“它”表示您的代码，那么可能不是。您实际上是在要求某人对您的（非工作）代码进行逆向工程，弄清楚您在编写代码时对代码的心理概念，并弄清楚如何将其变成可以工作的东西。（我没试过……）

  • 如果“它”表示 Sedgewick 代码，请参见上文。（包含您的代码有什么意义？）

1 - 如果有人花时间为你做这件事，你很可能会回来说“实际上，我已经明白了大部分内容。我没有得到的一件事是......”。

于 2013-07-06T01:31:09.263 回答