This is a fork of the original GoLLRB to make the nodes immutable. This makes it slower by an order of magnitude, but makes it possible to serialize/iterate over a tree while it is still being updated live.
Well, it isn't completely immutable. Node colors are still mutable, but you probably don't care about that. This also means that you can't fork a tree and use it as a separate sovereign tree, as the colors will get mixed up.
GoLLRB is a Left-Leaning Red-Black (LLRB) implementation of 2-3 balanced binary search trees in Go Language.
As of this writing and to the best of the author's knowledge, Go still does not have a balanced binary search tree (BBST) data structure. These data structures are quite useful in a variety of cases. A BBST maintains elements in sorted order under dynamic updates (inserts and deletes) and can support various order-specific queries. Furthermore, in practice one often implements other common data structures like Priority Queues, using BBST's.
2-3 trees (a type of BBST's), as well as the runtime-similar 2-3-4 trees, are the de facto standard BBST algoritms found in implementations of Python, Java, and other libraries. The LLRB method of implementing 2-3 trees is a recent improvement over the traditional implementation. The LLRB approach was discovered relatively recently (in 2008) by Robert Sedgewick of Princeton University.
GoLLRB is a Go implementation of LLRB 2-3 trees.
GoLLRB has been used in some pretty heavy-weight machine learning tasks over many gigabytes of data. I consider it to be in stable, perhaps even production, shape. There are no known bugs.
With a healthy Go Language installed, simply run go get github.com/petar/GoLLRB/llrb
package main
import (
"fmt"
"github.com/petar/GoLLRB/llrb"
)
func lessInt(a, b interface{}) bool { return a.(int) < b.(int) }
func main() {
tree := llrb.New(lessInt)
tree.ReplaceOrInsert(1)
tree.ReplaceOrInsert(2)
tree.ReplaceOrInsert(3)
tree.ReplaceOrInsert(4)
tree.DeleteMin()
tree.Delete(4)
c := tree.IterAscend()
for {
u := <-c
if u == nil {
break
}
fmt.Printf("%d\n", int(u.(int)))
}
}
GoLLRB was written by Petar Maymounkov.
Follow me on Twitter @maymounkov!