README
¶
GoLLRB
GoLLRB is a Left-Leaning Red-Black (LLRB) implementation of 2-3 balanced binary search trees in Go Language.
Overview
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.
Maturity
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.
Installation
With a healthy Go Language installed, simply run go get github.com/petar/GoLLRB/llrb
Example
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)))
}
}
About
GoLLRB was written by Petar Maymounkov.
Follow me on Twitter @maymounkov!
Documentation
¶
Overview ¶
A Left-Leaning Red-Black (LLRB) implementation of 2-3 balanced binary search trees, based on the following work:
http://www.cs.princeton.edu/~rs/talks/LLRB/08Penn.pdf http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf http://www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java 2-3 trees (and the run-time equivalent 2-3-4 trees) are the de facto standard BST algoritms found in implementations of Python, Java, and other libraries. The LLRB implementation of 2-3 trees is a recent improvement on the traditional implementation, observed and documented by Robert Sedgewick.
Index ¶
- type Int
- type Item
- type Iterator
- type LLRB
- func (t *LLRB) Ascend() *Iterator
- func (t *LLRB) AscendAbove(pivot Item) *Iterator
- func (t *LLRB) AscendAtOrAbove(pivot Item) *Iterator
- func (t *LLRB) AscendAtOrBelow(pivot Item) *Iterator
- func (t *LLRB) AscendBelow(pivot Item) *Iterator
- func (t *LLRB) Delete(key Item) Item
- func (t *LLRB) DeleteMax() Item
- func (t *LLRB) DeleteMin() Item
- func (t *LLRB) Descend() *Iterator
- func (t *LLRB) DescendAbove(pivot Item) *Iterator
- func (t *LLRB) DescendAtOrAbove(pivot Item) *Iterator
- func (t *LLRB) DescendAtOrBelow(pivot Item) *Iterator
- func (t *LLRB) DescendBelow(pivot Item) *Iterator
- func (t *LLRB) Get(key Item) Item
- func (t *LLRB) GetHeight(key Item) (result Item, depth int)
- func (t *LLRB) Has(key Item) bool
- func (t *LLRB) HeightStats() (avg, stddev float64)
- func (t *LLRB) InsertNoReplace(item Item)
- func (t *LLRB) InsertNoReplaceBulk(items ...Item)
- func (t *LLRB) Len() int
- func (t *LLRB) Max() Item
- func (t *LLRB) Min() Item
- func (t *LLRB) ReplaceOrInsert(item Item) Item
- func (t *LLRB) ReplaceOrInsertBulk(items ...Item)
- func (t *LLRB) Root() *Node
- func (t *LLRB) SetRoot(r *Node)
- type Node
- type String
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type LLRB ¶
type LLRB struct {
// contains filtered or unexported fields
}
Tree is a Left-Leaning Red-Black (LLRB) implementation of 2-3 trees
func (*LLRB) AscendAbove ¶
func (*LLRB) AscendAtOrAbove ¶
func (*LLRB) AscendAtOrBelow ¶
func (*LLRB) AscendBelow ¶
func (*LLRB) Delete ¶
Delete deletes an item from the tree whose key equals key. The deleted item is return, otherwise nil is returned.
func (*LLRB) DeleteMax ¶
DeleteMax deletes the maximum element in the tree and returns the deleted item or nil otherwise
func (*LLRB) DeleteMin ¶
DeleteMin deletes the minimum element in the tree and returns the deleted item or nil otherwise.
func (*LLRB) DescendAbove ¶
func (*LLRB) DescendAtOrAbove ¶
func (*LLRB) DescendAtOrBelow ¶
func (*LLRB) DescendBelow ¶
func (*LLRB) GetHeight ¶
GetHeight returns an item in the tree with key @key, and it's height in the tree
func (*LLRB) Has ¶
Has returns true if the tree contains an element whose order is the same as that of key.
func (*LLRB) HeightStats ¶
HeightStats returns the average and standard deviation of the height of elements in the tree
func (*LLRB) InsertNoReplace ¶
InsertNoReplace inserts item into the tree. If an existing element has the same order, both elements remain in the tree.
func (*LLRB) InsertNoReplaceBulk ¶
func (*LLRB) ReplaceOrInsert ¶
ReplaceOrInsert inserts item into the tree. If an existing element has the same order, it is removed from the tree and returned.
Source Files