`import "github.com/biogo/store/llrb"`

Package llrb implements Left-Leaning Red Black trees as described by Robert Sedgewick.

More details relating to the implementation are available at the following locations:

http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf http://www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java http://www.teachsolaisgames.com/articles/balanced_left_leaning.html

Code:

package main import ( "fmt" "github.com/biogo/store/llrb" ) type ( Int int IntUpperBound int ) func (c Int) Compare(b llrb.Comparable) int { switch i := b.(type) { case Int: return int(c - i) case IntUpperBound: return int(c) - int(i) } panic("unknown type") } func (c IntUpperBound) Compare(b llrb.Comparable) int { var d int switch i := b.(type) { case Int: d = int(c) - int(i) case IntUpperBound: d = int(c - i) } if d == 0 { return 1 } return d } func main() { values := []int{0, 1, 2, 3, 4, 2, 3, 5, 5, 65, 32, 3, 23} // Insert using a type that reports equality: { t := &llrb.Tree{} for _, v := range values { t.Insert(Int(v)) // Insert with replacement. } results := []int(nil) // More efficiently retrieved using Get(Int(3))... t.DoMatching(func(c llrb.Comparable) (done bool) { results = append(results, int(c.(Int))) return }, Int(3)) fmt.Println("With replacement: ", results) } // Insert using a type that does not report equality: { t := &llrb.Tree{} for _, v := range values { t.Insert(IntUpperBound(v)) // Insert without replacement. } results := []int(nil) t.DoMatching(func(c llrb.Comparable) (done bool) { results = append(results, int(c.(IntUpperBound))) return }, Int(3)) fmt.Println("Without replacement:", results) } }

- Constants
- type Color
- type Comparable
- type Node
- type Operation
- type Tree
- func (t *Tree) Ceil(q Comparable) Comparable
- func (t *Tree) Delete(e Comparable)
- func (t *Tree) DeleteMax()
- func (t *Tree) DeleteMin()
- func (t *Tree) Do(fn Operation) bool
- func (t *Tree) DoMatching(fn Operation, q Comparable) bool
- func (t *Tree) DoRange(fn Operation, from, to Comparable) bool
- func (t *Tree) DoRangeReverse(fn Operation, from, to Comparable) bool
- func (t *Tree) DoReverse(fn Operation) bool
- func (t *Tree) Floor(q Comparable) Comparable
- func (t *Tree) Get(q Comparable) Comparable
- func (t *Tree) Insert(e Comparable)
- func (t *Tree) Len() int
- func (t *Tree) Max() Comparable
- func (t *Tree) Min() Comparable

Operation mode of the LLRB tree.

A Color represents the color of a Node.

❖

const ( // Red as false give us the defined behaviour that new nodes are red. Although this // is incorrect for the root node, that is resolved on the first insertion. Red Color = false Black Color = true )

String returns a string representation of a Color.

❖

type Comparable interface { // Compare returns a value indicating the sort order relationship between the // receiver and the parameter. // // Given c = a.Compare(b): // c < 0 if a < b; // c == 0 if a == b; and // c > 0 if a > b. // Compare(Comparable) int }

A Comparable is a type that can be inserted into a Tree or used as a range or equality query on the tree,

❖

type Node struct { Elem Comparable Left, Right *Node Color Color }

A Node represents a node in the LLRB tree.

❖

type Operation func(Comparable) (done bool)

An Operation is a function that operates on a Comparable. If done is returned true, the Operation is indicating that no further work needs to be done and so the Do function should traverse no further.

A Tree manages the root node of an LLRB tree. Public methods are exposed through this type.

❖

func (t *Tree) Ceil(q Comparable) Comparable

Ceil returns the smallest value equal to or greater than the query q according to q.Compare().

❖

func (t *Tree) Delete(e Comparable)

Delete deletes the node that matches e according to Compare(). Note that Compare must identify the target node uniquely and in cases where non-unique keys are used, attributes used to break ties must be used to determine tree ordering during insertion.

DeleteMax deletes the node with the maximum value in the tree. If insertion without replacement has been used, the right-most maximum will be deleted.

DeleteMin deletes the node with the minimum value in the tree. If insertion without replacement has been used, the left-most minimum will be deleted.

Do performs fn on all values stored in the tree. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.

❖

func (t *Tree) DoMatching(fn Operation, q Comparable) bool

DoMatch performs fn on all values stored in the tree that match q according to Compare, with q.Compare() used to guide tree traversal, so DoMatching() will out perform Do() with a called conditional function if the condition is based on sort order, but can not be reliably used if the condition is independent of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.

❖

func (t *Tree) DoRange(fn Operation, from, to Comparable) bool

DoRange performs fn on all values stored in the tree over the interval [from, to) from left to right. If to is less than from DoRange will panic. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships future tree operation behaviors are undefined.

❖

func (t *Tree) DoRangeReverse(fn Operation, from, to Comparable) bool

DoRangeReverse performs fn on all values stored in the tree over the interval (to, from] from right to left. If from is less than to DoRange will panic. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships future tree operation behaviors are undefined.

DoReverse performs fn on all values stored in the tree, but in reverse of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.

❖

func (t *Tree) Floor(q Comparable) Comparable

Floor returns the greatest value equal to or less than the query q according to q.Compare().

❖

func (t *Tree) Get(q Comparable) Comparable

Get returns the first match of q in the Tree. If insertion without replacement is used, this is probably not what you want.

❖

func (t *Tree) Insert(e Comparable)

Insert inserts the Comparable e into the Tree at the first match found with e or when a nil node is reached. Insertion without replacement can specified by ensuring that e.Compare() never returns 0. If insert without replacement is performed, a distinct query Comparable must be used that can return 0 with a Compare() call.

Len returns the number of elements stored in the Tree.

❖

func (t *Tree) Max() Comparable

Return the maximum value stored in the tree. This will be the right-most maximum value if insertion without replacement has been used.

❖

func (t *Tree) Min() Comparable

Return the minimum value stored in the tree. This will be the left-most minimum value if insertion without replacement has been used.

Package llrb is imported by 212 packages. Updated 2016-07-17. Refresh now. Tools for package owners.