Returning a pointer to a pointer with a find method on a binary tree implemented with Go generics

Picci 0
Viewed 28

I have been recently watching a video where Ian Lance Taylor was presenting the new generics implementation in Go.

As an example he shows a simple implementation of a binary tree like this

type Node[T any] struct {
    left, right *Node[T]
    data        T
}

type bTree[T any] struct {
    root    *Node[T]
    compare func(T, T) int
}

and an implementation of a search method for such binary tree like this

func (bt *bTree[T]) findDoublePointer(v T) **Node[T] {
    pl := &bt.root
    for *pl != nil {
        switch cmpRes := bt.compare(v, (*pl).data); {
        case cmpRes < 0:
            pl = &(*pl).left
        case cmpRes > 0:
            pl = &(*pl).right
        default:
            return pl
        }
    }
    return pl
}

The method that I have called findDoublePointer returns a pointer to a pointer to a Node of the tree.

My question is whether this is just an example to explain something else, in this case the generics idea, or whether there is a sound reason to return a pointer to a pointer in this case.

The reason I ask this question is that it seems to me that a simpler version of the find method can be achieved with such code

func (bt *bTree[T]) findPointer(v T) *Node[T] {
    pl := bt.root
    for pl != nil {
        switch cmpRes := bt.compare(v, (*pl).data); {
        case cmpRes < 0:
            pl = (*pl).left
        case cmpRes > 0:
            pl = (*pl).right
        default:
            return pl
        }
    }
    return pl
}
go
1 Answers

findDoublePointer returns a pointer to the subtree that is the best match for the value v. It has nothing to do with generics, it is a nice way to lookup-insert-if-missing a value.

If the double pointer points to a non-nil subtree, it means that the tree contains the value equal to v. But if it points to nil, then it is exactly the place where to add a new Node with v as the value.

func main() {
    t := NewIntTree(0)
    pt := &t
    p1 := pt.findDoublePointer(1)
    // *p1 == nil
    // Insert `1` into the tree
    *p1 = NewNode[int](1)
    p1 = pt.findDoublePointer(1)
    // Success: 1 is in the tree
    println("1 node: ", *p1, (*p1).data)
}

Full Example: https://go.dev/play/p/X80joH39G5C

Pak Uula0
Related