GoLLRB: github.com/petar/GoLLRB/llrb Index | Files

package llrb

import "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

Package Files

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

type Int Uses

type Int int

func (Int) Less Uses

func (x Int) Less(than Item) bool

type Item Uses

type Item interface {
    Less(than Item) bool
}

func Inf Uses

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 Uses

type ItemIterator func(i Item) bool

type LLRB Uses

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

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

func New Uses

func New() *LLRB

New() allocates a new tree

func (*LLRB) AscendGreaterOrEqual Uses

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 Uses

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

func (*LLRB) AscendRange Uses

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

func (*LLRB) Delete Uses

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 Uses

func (t *LLRB) DeleteMax() Item

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

func (*LLRB) DeleteMin Uses

func (t *LLRB) DeleteMin() Item

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

func (*LLRB) DescendLessOrEqual Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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

func (*LLRB) Len Uses

func (t *LLRB) Len() int

Len returns the number of nodes in the tree.

func (*LLRB) Max Uses

func (t *LLRB) Max() Item

Max returns the maximum element in the tree.

func (*LLRB) Min Uses

func (t *LLRB) Min() Item

Min returns the minimum element in the tree.

func (*LLRB) ReplaceOrInsert Uses

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 Uses

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

func (*LLRB) Root Uses

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 Uses

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 Uses

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 Uses

type String string

func (String) Less Uses

func (x String) Less(than Item) bool

Package llrb imports 1 packages (graph) and is imported by 70 packages. Updated 2018-05-09. Refresh now. Tools for package owners.