Golang指针接收器未按预期更新。

huangapple go评论71阅读模式
英文:

Golang pointer receiver not updating as expected

问题

我正在实现二叉搜索树中的节点删除。我已经实现了一个在算法上看起来不错的方法,但是它不起作用。在花费了几个小时试图理解原因后,我希望能从你这里得到一些帮助。

BST定义

type Node struct {
    Data  int
    Left  *Node
    Right *Node
}

辅助方法(它们已经经过测试并且有效)

// New返回指向新节点的指针(类似于Go中的new构造)
func New(data int) *Node {
    return &Node{Data: data}
}

// Find检查bst中是否存在某个数据,并返回相应的节点
func (bst *Node) Find(data int) *Node {
    if bst == nil {
        return bst
    }
    if bst.Data == data {
        return bst
    }
    if data < bst.Data {
        return bst.Left.Find(data)
    }
    return bst.Right.Find(data)
}

// Min返回bst中最小的元素
func (bst *Node) Min() *Node {
    if bst == nil {
        return nil
    }
    current := bst
    for current.Left != nil {
        current = current.Left
    }
    return current
}

不起作用的方法

// Delete从二叉树中删除一个键
func (bst *Node) Delete(data int) *Node {
    if bst == nil {
        return bst
    }
    current := bst
    toDelete := current.Find(data)
    if toDelete == nil {
        return current
    }
    if toDelete.Right == nil && toDelete.Left != nil {
        toDelete = toDelete.Left
        return current
    }
    if toDelete.Right != nil && toDelete.Left == nil {
        toDelete = toDelete.Right
        return current
    }
    inOrderSuccessor := toDelete.Right.Min()
    toDelete = inOrderSuccessor
    return current
}

测试

func main() {
    root := bst.New(8)
    root.Left = bst.New(3)
    root.Right = bst.New(10)
    root.Left.Left = bst.New(1)
    root.Left.Right = bst.New(6)
    fmt.Println(root.InOrder())
    root = root.Delete(3)
    fmt.Println(root.InOrder())
}

输出结果

1->3->6->8->10->
1->3->6->8->10->

Delete方法中有一些问题,但我无法理解原因。

可以在这里的playground中运行此代码:https://go.dev/play/p/oJZMOCp2BXL

英文:

I am implementing node deletion in binary search tree. I have implemented a method which look good (at algorithm standpoint). But do not work. After spending hours trying to understand why, I would love to get some help from you.

BST definition

    type Node struct {
	Data  int
	Left  *Node
	Right *Node
}

Helper methods (they have been tested and works)

// New returns a pointer to a mew node (like the new construct in Go)
func New(data int) *Node {
	return &amp;Node{Data: data}
}

// Find checks whether some data exist in the bst and returns the corresponding node
func (bst *Node) Find(data int) *Node {
	if bst == nil {
		return bst
	}
	if bst.Data == data {
		return bst
	}
	if data &lt; bst.Data {
		return bst.Left.Find(data)
	}
	return bst.Right.Find(data)
}

// Min returns the smallest element in a bst
func (bst *Node) Min() *Node {
	if bst == nil {
		return nil
	}
	current := bst
	for current.Left != nil {
		current = current.Left
	}
	return current
}

The non working method

// Delete removes a key from the binary tree
func (bst *Node) Delete(data int) *Node {
	if bst == nil {
		return bst
	}
	current := bst
	toDelete := current.Find(data)
	if toDelete == nil {
		return current
	}
	if toDelete.Right == nil &amp;&amp; toDelete.Left != nil {
		toDelete = toDelete.Left
		return current
	}
	if toDelete.Right != nil &amp;&amp; toDelete.Left == nil {
		toDelete = toDelete.Right
		return current
	}
	inOrderSuccessor := toDelete.Right.Min()
	toDelete = inOrderSuccessor
	return current
}

Test

func main() {
	root := bst.New(8)
	root.Left = bst.New(3)
	root.Right = bst.New(10)
	root.Left.Left = bst.New(1)
	root.Left.Right = bst.New(6)
	fmt.Println(root.InOrder())
	root = root.Delete(3)
	fmt.Println(root.InOrder())
}

output
1-&gt;3-&gt;6-&gt;8-&gt;10-&gt;
1-&gt;3-&gt;6-&gt;8-&gt;10-&gt;

There is something wrong in the Delete method but I could not understand why.

This code can be run in the playground here https://go.dev/play/p/oJZMOCp2BXL

答案1

得分: 2

我假设你认为

toDelete = toDelete.Left

会覆盖指针 toDelete 指向的数据。
但是这个操作只是给 toDelete 变量赋予一个新的指针。要覆盖存储在内存中的数据,你需要解引用指针:

*toDelete = *toDelete.Left

你可以查看这个例子 https://go.dev/play/p/M62hd3lpHXk 并在一个更简单的情况下看到区别。

英文:

I assume that you think that

toDelete = toDelete.Left

overwrites data that is stored where toDelete points to.
But this operation will just assign a new pointer to toDeletevariable. To overwrite data that is stored in memory you need to dereference the pointer:

*toDelete = *toDelete.Left

You can look at this example https://go.dev/play/p/M62hd3lpHXk and see the difference in a simpler case.

huangapple
  • 本文由 发表于 2022年9月22日 21:13:09
  • 转载请务必保留本文链接:https://go.coder-hub.com/73815288.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定