llrb

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

Index

• Constants
• type Color
  • func (c Color) String() string
• 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

Constants

const (
	// TD234 ...
	TD234 = iota
	// BU23 ...
	BU23
)

const Mode = BU23

Mode of the LLRB tree.

Types

type Color

type Color bool

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 ...
	Black Color = true
)

func (Color) String

func (c Color) String() string

String returns a string representation of a Color.

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
}

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

type Tree struct {
	Root  *Node // Root node of the tree.
	Count int   // Number of elements stored.
}

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

func (t *Tree) Do(fn Operation) bool

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

DoMatching 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

func (t *Tree) DoReverse(fn Operation) bool

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) Len

func (t *Tree) Len() int

Len returns the number of elements stored in the Tree.

func (*Tree) Max

func (t *Tree) Max() Comparable

Max returns 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

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