Documentation
¶
Overview ¶
Package llrb provides a left-leaning red-black implementation of 2-3 balanced binary search trees
Index ¶
- type Item
- type LessFunc
- type Node
- type Tree
- func (t *Tree) Delete(key Item) Item
- func (t *Tree) DeleteMax() Item
- func (t *Tree) DeleteMin() Item
- func (t *Tree) Get(key Item) Item
- func (t *Tree) GetHeight(key Item) (result Item, depth int)
- func (t *Tree) Has(key Item) bool
- func (t *Tree) HeightStats() (avg, stddev float64)
- func (t *Tree) Init(lessfunc LessFunc)
- func (t *Tree) InsertNoReplace(item Item)
- func (t *Tree) InsertNoReplaceBulk(items ...Item)
- func (t *Tree) IterAscend() <-chan Item
- func (t *Tree) IterDescend() <-chan Item
- func (t *Tree) IterRange(lower, upper Item) <-chan Item
- func (t *Tree) IterRangeInclusive(lower, upper Item) <-chan Item
- func (t *Tree) Len() int64
- func (t *Tree) Max() Item
- func (t *Tree) Min() Item
- func (t *Tree) ReplaceOrInsert(item Item) Item
- func (t *Tree) ReplaceOrInsertBulk(items ...Item)
- func (t *Tree) Root() *Node
- func (t *Tree) SetRoot(r *Node)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree is a Left-Leaning Red-Black (LLRB) implementation of 2-3 trees, based on:
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.
func (*Tree) Delete ¶
Delete deletes an item from the tree whose key equals key. The deleted item is return, otherwise nil is returned.
func (*Tree) DeleteMax ¶
DeleteMax deletes the maximum element in the tree and returns the deleted item or nil otherwise
func (*Tree) DeleteMin ¶
DeleteMin deletes the minimum element in the tree and returns the deleted item or nil otherwise.
func (*Tree) GetHeight ¶
GetHeight() returns an item in the tree with key @key, and it's height in the tree
func (*Tree) Has ¶
Has returns true if the tree contains an element whose LessThan order equals that of key.
func (*Tree) HeightStats ¶
HeightStats() returns the average and standard deviation of the height of elements in the tree
func (*Tree) InsertNoReplace ¶
InsertNoReplace inserts item into the tree. If an existing element has the same order, both elements remain in the tree.
func (*Tree) InsertNoReplaceBulk ¶
func (*Tree) IterAscend ¶
IterAscend returns a chan that iterates through all elements in in ascending order. TODO: This is a deprecated interface for iteration.
func (*Tree) IterDescend ¶
IterDescend returns a chan that iterates through all elements in descending order. TODO: This is a deprecated interface for iteration.
func (*Tree) IterRange ¶
IterRange() returns a chan that iterates through all elements E in the tree with lower <= E < upper in ascending order. TODO: This is a deprecated interface for iteration.
func (*Tree) IterRangeInclusive ¶
IterRangeInclusive returns a chan that iterates through all elements E in the tree with lower <= E <= upper in ascending order. TODO: This is a deprecated interface for iteration.
func (*Tree) 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