go - BST删除函数无法追踪问题

Question

我无法在 Go 中的 BST 删除函数中跟踪我的逻辑错误。

func delete(d *Node, v int) {
if d == nil {
    fmt.Println("The tree is empty")
}
if v < d.key {
    delete(d.left, v)
} else if v > d.key {
    delete(d.right, v)
} else if v == d.key {
    if d.right == nil && d.left == nil {
        d = nil
    } else {
        if d.left == nil && d.right != nil {
            d.key= d.right.key
            delete(d.right,d.key)


        } else if d.right == nil && d.left != nil {
            d.key= d.left.key
            delete(d.left,d.key)
        }else{
        min := minvalue(d.right)
        d.key = min.key
        delete(d.right, min.key)
    }
    }
}
}

The output shouldn't contain 4 but the result is instead showing 6 two times

预期的输出是 5 6，但它显示的是 4 6 6

Answer 1

正如一些人在评论中指出的那样，您应该提供一个 Minimal Reproducible Example ，这有助于人们避免将时间浪费在简单的误解上。

不过，在这种情况下，您做错了什么是很明显的——至少在第一层是这样。 (可能还有更多，具体取决于您打算对这些树做什么。)

考虑以下函数:

func setToNil(p *int) {
    p = nil
}

让我们在 main 中使用它:

func main() {
    x := 3
    px := &x
    fmt.Println("before: x =", x, "px =", px)
    setToNil(px)
    fmt.Println("after: x =", x, "px =", px)
}

(Complete version on the Go playground)

您希望这个程序做什么？试一试:它是否达到了您的预期？为什么或者为什么不？如果不是，那么这个变体怎么样:

func setToTheAnswer(i int) {
    i = 42
}

func main() {
    x := 3
    fmt.Println("before: x =", x)
    setToTheAnswer(x)
    fmt.Println("after: x =", x)
}

填写其余的并尝试一下。为什么 x 没有改变？ (它应该改变吗？如果你这么认为，为什么你这么认为？语言定义说它不应该。)

现在，将其与此版本进行比较:

func setToTheAnswer(p *int) {
    *p = 42
}

func setToNil(q **int) {
    *q = nil
}

func main() {
    x := 3
    px := &x
    fmt.Println("before: x =", x, "px =", px)
    setToTheAnswer(px)
    setToNil(&px)             // note the & in front of px
    fmt.Println("after: x =", x, "px =", px)
}

这个版本会做什么？ Try it on the playground.

考虑到这一点，考虑一下您的变量 d

你的功能:

func delete(d *Node, v int) {
    // ...
}

接受一个名为 d 的 pointer to Node 类型的参数(当然还有 int 类型的 v ) .如果您在 delete 中更改 d，那对任何调用者中的任何 * Node 变量都没有影响，因为 d是这个指向节点的指针的副本。您可以更改 *d 以更改调用者指针指向的 Node，但您不能更改调用者的指针。

有多种不同的方法可以解决这个问题。例如，您可以取一个包含root *Node 指针的不同对象，而不是取一个d *Node，或者您可以取一个pd **Node 以便您可以更新调用方中的 d *Node。哪个是正确的方法？这取决于你。