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

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

Golang pointer receiver not updating as expected

问题

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

BST定义

  1. type Node struct {
  2.     Data  int
  3.     Left  *Node
  4.     Right *Node
  5. }

辅助方法（它们已经经过测试并且有效）

  1. // New返回指向新节点的指针（类似于Go中的new构造）
  2. func New(data int) *Node {
  3.     return &Node{Data: data}
  4. }
  6. // Find检查bst中是否存在某个数据，并返回相应的节点
  7. func (bst *Node) Find(data int) *Node {
  8.     if bst == nil {
  9.         return bst
  10.     }
  11.     if bst.Data == data {
  12.         return bst
  13.     }
  14.     if data < bst.Data {
  15.         return bst.Left.Find(data)
  16.     }
  17.     return bst.Right.Find(data)
  18. }
  20. // Min返回bst中最小的元素
  21. func (bst *Node) Min() *Node {
  22.     if bst == nil {
  23.         return nil
  24.     }
  25.     current := bst
  26.     for current.Left != nil {
  27.         current = current.Left
  28.     }
  29.     return current
  30. }

不起作用的方法

  1. // Delete从二叉树中删除一个键
  2. func (bst *Node) Delete(data int) *Node {
  3.     if bst == nil {
  4.         return bst
  5.     }
  6.     current := bst
  7.     toDelete := current.Find(data)
  8.     if toDelete == nil {
  9.         return current
  10.     }
  11.     if toDelete.Right == nil && toDelete.Left != nil {
  12.         toDelete = toDelete.Left
  13.         return current
  14.     }
  15.     if toDelete.Right != nil && toDelete.Left == nil {
  16.         toDelete = toDelete.Right
  17.         return current
  18.     }
  19.     inOrderSuccessor := toDelete.Right.Min()
  20.     toDelete = inOrderSuccessor
  21.     return current
  22. }

测试

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

输出结果

  1. 1->3->6->8->10->
  2. 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

  1.     type Node struct {
  2. 	Data  int
  3. 	Left  *Node
  4. 	Right *Node
  5. }

Helper methods (they have been tested and works)

  1. // New returns a pointer to a mew node (like the new construct in Go)
  2. func New(data int) *Node {
  3. 	return &amp;Node{Data: data}
  4. }
  6. // Find checks whether some data exist in the bst and returns the corresponding node
  7. func (bst *Node) Find(data int) *Node {
  8. 	if bst == nil {
  9. 		return bst
  10. 	}
  11. 	if bst.Data == data {
  12. 		return bst
  13. 	}
  14. 	if data &lt; bst.Data {
  15. 		return bst.Left.Find(data)
  16. 	}
  17. 	return bst.Right.Find(data)
  18. }
  20. // Min returns the smallest element in a bst
  21. func (bst *Node) Min() *Node {
  22. 	if bst == nil {
  23. 		return nil
  24. 	}
  25. 	current := bst
  26. 	for current.Left != nil {
  27. 		current = current.Left
  28. 	}
  29. 	return current
  30. }

The non working method

  1. // Delete removes a key from the binary tree
  2. func (bst *Node) Delete(data int) *Node {
  3. 	if bst == nil {
  4. 		return bst
  5. 	}
  6. 	current := bst
  7. 	toDelete := current.Find(data)
  8. 	if toDelete == nil {
  9. 		return current
  10. 	}
  11. 	if toDelete.Right == nil &amp;&amp; toDelete.Left != nil {
  12. 		toDelete = toDelete.Left
  13. 		return current
  14. 	}
  15. 	if toDelete.Right != nil &amp;&amp; toDelete.Left == nil {
  16. 		toDelete = toDelete.Right
  17. 		return current
  18. 	}
  19. 	inOrderSuccessor := toDelete.Right.Min()
  20. 	toDelete = inOrderSuccessor
  21. 	return current
  22. }

Test

  1. func main() {
  2. 	root := bst.New(8)
  3. 	root.Left = bst.New(3)
  4. 	root.Right = bst.New(10)
  5. 	root.Left.Left = bst.New(1)
  6. 	root.Left.Right = bst.New(6)
  7. 	fmt.Println(root.InOrder())
  8. 	root = root.Delete(3)
  9. 	fmt.Println(root.InOrder())
  10. }
  12. output
  13. 1-&gt;3-&gt;6-&gt;8-&gt;10-&gt;
  14. 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

我假设你认为

  1. toDelete = toDelete.Left

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

  1. *toDelete = *toDelete.Left

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

英文:

I assume that you think that

  1. 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:

  1. *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
  • algorithm
  • binary-tree
  • go
匿名

发表评论

匿名网友

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

确定