Binary Tree for Go?

[pongad]

Hi All,
I do not see any thread on this topic, so I have taken the liberty
to start my own.
I have been playing with Go for a while, and I see it does not have
an "always sorted" data structure like binary tree. Here is my idea so
far:

The tree can be constructed with
tree := tree.New(fn),
where 'fn' is a function with signature
func(a, b interface{}) (int, os.Error).

Function 'fn' should return a integer that is positive if 'a' should
be sorted after 'b', negative if 'a' should be sorted before 'b', and
zero if 'a' is logically equal to 'b'. The error can be raised if
either 'a' or 'b' does not have the type wanted by the tree (ie, if we
want a tree of ints and 'a' is a string).

Function Add(a interface{}) adds an element to the tree
Add() does nothing if there exists an element 'x' already in the tree
where fn(x, a) == 0.

Function Remove(a interface{}) and Contains(a interface{}) removes and
checks if the tree contains the element 'a' respectively.

Function 'Len() int' returns the size of the tree.

Function 'Balance()' balances the tree.

Does anyone else like this idea? :D

[Jan Mercl]

On Monday, January 2, 2012 1:21:20 PM UTC+1, pongad wrote:

Hi All,
  I do not see any thread on this topic, so I have taken the liberty
to start my own.
  I have been playing with Go for a while, and I see it does not have
an "always sorted" data structure like binary tree. Here is my idea so
far:

You might want to have a look at e.g.: https://github.com/petar/GoLLRB

I've just checked it to be OK with latest weekly. The only minor thing is in llrb/llrb_test.go: s|"rand"|"math/rand"| and s/math.Fabs/math.Abs/ as it is probably targeted at the stable (latest release) version.

[John Asmuth]

On Monday, January 2, 2012 7:49:19 AM UTC-5, Jan Mercl wrote:

You might want to have a look at e.g.: https://github.com/petar/GoLLRB

Seconded. GoLLRB is great. 

[pongad]

Thanks guys,
It would appear I forgot to look into goinstallable packages X_X.

Michael

[Kyle Lemons]

The non-obvious problem with such implementations is that, for now, all generic ones will have to use interface{} or some clever interface like sort.Interface, both of which will have performance implications (the former much more so than the latter) that a tuned implementation for your data structure would have.

[pongad]

Kyle,
I am not very familiar with the performance issue with type
assertions. Can you briefly discuss it here? Or is there any other
thread I can look at? (My search didn't give me any.)

Thanks,
Michael

[Kyle Lemons]

You can always try these things yourself with the benchmark package.  For a simple assignment, for example:

package main

import (

        "fmt"

        . "testing"

)

func main() {

        fmt.Println("(interface{}).(int)", Benchmark(func(b *B) {

                var v interface{} = 5

                for i := 0; i < b.N; i++ {

                        _ = v.(int)

                }

        }))

        fmt.Println("               int ", Benchmark(func(b *B) {

                var v = 5

                for i := 0; i < b.N; i++ {

                        _ = v

                }

        }))

}

Yields the results:

(interface{}).(int) 100000000           14.7 ns/op

               int  1000000000           2.29 ns/op