英文:
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 &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 < 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 && 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
}
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->3->6->8->10->
1->3->6->8->10->
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论