go - 重新平衡树后如何更改接收器类型(根节点)

Question

我正在尝试在 Go 中实现二叉树，但目前我陷入了树的重新平衡。重新平衡后，根节点很可能会发生变化。由于根节点是接收器类型，我必须更改接收器类型指向的值。以前的根节点现在被用作另一个节点，这导致了这个节点现在也是根节点的情况。

func (n *treeNode) rebalance()  {  

    sorted := n.traverseTree([]*treeNode{})  //returns a sorted array of *treeNode
    newRoot := innerRebalance(sorted) //the method gives the correct result
    *n = *newRoot//now I have a cyclic reference in the tree

}

重新平衡在 add 函数中调用。我不想公开 rebalance 方法，因为它是一个实现细节。我想在 Add 方法中调用 rebalance 方法。

界面:

type Store interface {
    Add(key string, value string)
    Get(key string) string
    Remove(key string) bool
}

树节点结构:

type treeNode struct {
    bigger           *treeNode
    smaller          *treeNode
    key              string
    value            string
}

例子

再平衡之前

100(根) --> 150 --> 200

再平衡后

100 <-- 150(根)--> 200

分配给 *n 之后

... 150 <-- 150 <-- 150 --> 200

如何更改接收器类型而不获取对自身的循环引用？

Answer 1

你要改的其实是**n ，所以它可以指向另一个节点。您不能在当前范围内这样做。但是，您可以包装节点并将节点设置在方法之外，并让节点的方法返回一个根。

例如，

type tree struct {
    root *treeNode
}

func (t *tree) Remove(key string) bool {
    root,ok := t.root.Remove()
    t.root = root
    return ok
}

并更改 *treeNode.Add至 func (*treeNode) Add(string) *treeNode .