package llrb

import "k8s.io/kubernetes/Godeps/_workspace/src/github.com/petar/GoLLRB/llrb"

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
• func (x Int) Less(than Item) bool
• type Item
• func Inf(sign int) Item
• type ItemIterator
• type LLRB
• func New() *LLRB
• func (t *LLRB) AscendGreaterOrEqual(pivot Item, iterator ItemIterator)
• func (t *LLRB) AscendLessThan(pivot Item, iterator ItemIterator)
• func (t *LLRB) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator)
• func (t *LLRB) Delete(key Item) Item
• func (t *LLRB) DeleteMax() Item
• func (t *LLRB) DeleteMin() Item
• func (t *LLRB) DescendLessOrEqual(pivot Item, iterator ItemIterator)
• 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
• func (x String) Less(than Item) bool

Types ¶

type Int ¶

type Int int

func (Int) Less ¶

func (x Int) Less(than Item) bool

type Item ¶

type Item interface {
	Less(than Item) bool
}

func Inf ¶

func Inf(sign int) Item

Inf returns an Item that is "bigger than" any other item, if sign is positive. Otherwise it returns an Item that is "smaller than" any other item.

type ItemIterator ¶

type ItemIterator func(i Item) bool

type LLRB ¶

type LLRB struct {
	// contains filtered or unexported fields
}

Tree is a Left-Leaning Red-Black (LLRB) implementation of 2-3 trees

func New ¶

func New() *LLRB

New() allocates a new tree

func (*LLRB) AscendGreaterOrEqual ¶

func (t *LLRB) AscendGreaterOrEqual(pivot Item, iterator ItemIterator)

AscendGreaterOrEqual will call iterator once for each element greater or equal to pivot in ascending order. It will stop whenever the iterator returns false.

func (*LLRB) AscendLessThan ¶

func (t *LLRB) AscendLessThan(pivot Item, iterator ItemIterator)

func (*LLRB) AscendRange ¶

func (t *LLRB) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator)

func (*LLRB) Delete ¶

func (t *LLRB) Delete(key Item) Item

Delete deletes an item from the tree whose key equals key. The deleted item is return, otherwise nil is returned.

func (*LLRB) DeleteMax ¶

func (t *LLRB) DeleteMax() Item

DeleteMax deletes the maximum element in the tree and returns the deleted item or nil otherwise

func (*LLRB) DeleteMin ¶

func (t *LLRB) DeleteMin() Item

DeleteMin deletes the minimum element in the tree and returns the deleted item or nil otherwise.

func (*LLRB) DescendLessOrEqual ¶

func (t *LLRB) DescendLessOrEqual(pivot Item, iterator ItemIterator)

DescendLessOrEqual will call iterator once for each element less than the pivot in descending order. It will stop whenever the iterator returns false.

func (*LLRB) Get ¶

func (t *LLRB) Get(key Item) Item

Get retrieves an element from the tree whose order is the same as that of key.

func (*LLRB) GetHeight ¶

func (t *LLRB) GetHeight(key Item) (result Item, depth int)

GetHeight() returns an item in the tree with key @key, and it's height in the tree

func (*LLRB) Has ¶

func (t *LLRB) Has(key Item) bool

Has returns true if the tree contains an element whose order is the same as that of key.

func (*LLRB) HeightStats ¶

func (t *LLRB) HeightStats() (avg, stddev float64)

HeightStats() returns the average and standard deviation of the height of elements in the tree

func (*LLRB) InsertNoReplace ¶

func (t *LLRB) InsertNoReplace(item Item)

InsertNoReplace inserts item into the tree. If an existing element has the same order, both elements remain in the tree.

func (*LLRB) InsertNoReplaceBulk ¶

func (t *LLRB) InsertNoReplaceBulk(items ...Item)

func (*LLRB) Len ¶

func (t *LLRB) Len() int

Len returns the number of nodes in the tree.

func (*LLRB) Max ¶

func (t *LLRB) Max() Item

Max returns the maximum element in the tree.

func (*LLRB) Min ¶

func (t *LLRB) Min() Item

Min returns the minimum element in the tree.

func (*LLRB) ReplaceOrInsert ¶

func (t *LLRB) ReplaceOrInsert(item Item) Item

ReplaceOrInsert inserts item into the tree. If an existing element has the same order, it is removed from the tree and returned.

func (*LLRB) ReplaceOrInsertBulk ¶

func (t *LLRB) ReplaceOrInsertBulk(items ...Item)

func (*LLRB) Root ¶

func (t *LLRB) Root() *Node

Root returns the root node of the tree. It is intended to be used by functions that serialize the tree.

func (*LLRB) SetRoot ¶

func (t *LLRB) SetRoot(r *Node)

SetRoot sets the root node of the tree. It is intended to be used by functions that deserialize the tree.

type Node ¶

type Node struct {
	Item
	Left, Right *Node // Pointers to left and right child nodes
	Black       bool  // If set, the color of the link (incoming from the parent) is black

}

type String ¶

type String string

func (String) Less ¶

func (x String) Less(than Item) bool

Source Files ¶

avgvar.go iterator.go llrb-stats.go llrb.go util.go