llrb

Documentation

Overview

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) (deleted Item, pos int)
  • 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) int
  • 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, int)
  • func (t *LLRB) ReplaceOrInsertBulk(items ...Item)
  • func (t *LLRB) Root() *Node
  • func (t *LLRB) SetRoot(r *Node)
• type Node
  • func (h *Node) Len() int
• 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) (deleted Item, pos int)

Delete deletes an item from the tree whose key equals key. Returns the deleted item, if any matches, and its position from the smallest item in the tree.

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

InsertNoReplace inserts item into the tree. If an existing element has the same order, both elements remain in the tree. Returns the position of the inserted item from the smallest item 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, int)

ReplaceOrInsert inserts item into the tree. If an existing element has the same order, it is removed from the tree and returned. Returns the replaced item, if any, and the item's position from the smallest item in the tree.

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
	NLeft, NRight int
	Black         bool // If set, the color of the link (incoming from the parent) is black

}

func (*Node) Len

func (h *Node) Len() int

type String

type String string

func (String) Less

func (x String) Less(than Item) bool