Не удается отследить проблему в функции удаления BST

Question

Я не могу отследить ошибку в моей логике в функции удаления BST в Go.

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

Вывод не должен содержать 4, но вместо этого результат показывает два раза 6

Ожидаемый вывод 5 6, но он показывает 4 6 6

Answer 1

Как отмечают некоторые в комментариях, вы должны предоставить Минимальный воспроизводимый пример , который помогает людям избежать напрасной траты времени на простые недоразумения.

В этом случае, однако, это довольно очевидночто вы сделали неправильно - по крайней мере, на первом уровне.(Может быть больше, в зависимости от того, что вы собираетесь делать с этими деревьями.)

Рассмотрим следующую функцию:

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

(полная версия на игровой площадке Go)

Что вы ожидаете от этой программы?Попробуй: получилось ли то, что ты ожидал?Почему или почему нет?Если нет, то как насчет этого варианта:

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

Что будет делать эта версия? Попробуйте на детской площадке.

Имея это в виду, подумайте о своей переменной d

Ваша функция:

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

занимаетпараметр с именем d типа pointer to Node (и v типа int, конечно).Если вы измените d в delete, это не повлияет на переменную * Node любого вызывающего абонента, поскольку d является копией этого указателя на узел.Вы можете изменить *d, чтобы изменить Node, на который указывает указатель вызывающего, но вы не можете изменить указатель вызывающего.

Существует несколько различных способов исправить это.Например, вместо d *Node вы можете взять другой объект, который содержит root *Node указатель, или вы можете взять pd **Node, чтобы вы могли обновить d *Node в вызывающей программе.,Какой правильный путь?Это зависит от вас.