Documentation ¶
Overview ¶
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
Example ¶
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) } }
Output: With replacement: [3] Without replacement: [3 3 3]
Index ¶
- 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
Examples ¶
Constants ¶
const ( TD234 = iota BU23 )
const Mode = BU23
Operation mode of the LLRB tree.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Comparable ¶
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 ¶
type Node struct { Elem Comparable Left, Right *Node Color Color }
A Node represents a node in the LLRB tree.
type Operation ¶
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.
type Tree ¶
A Tree manages the root node of an LLRB tree. Public methods are exposed through this type.
func (*Tree) Ceil ¶
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 (*Tree) Delete ¶
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.
func (*Tree) DeleteMax ¶
func (t *Tree) DeleteMax()
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.
func (*Tree) DeleteMin ¶
func (t *Tree) DeleteMin()
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.
func (*Tree) Do ¶
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 (*Tree) DoMatching ¶
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 (*Tree) DoRange ¶
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 (*Tree) DoRangeReverse ¶
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.
func (*Tree) DoReverse ¶
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 (*Tree) Floor ¶
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 (*Tree) Get ¶
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 (*Tree) Insert ¶
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.
func (*Tree) Max ¶
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 (*Tree) Min ¶
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.