llrb

Documentation

Overview

Copyright 2010 Petar Maymounkov. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Index

• type Item
• type ItemIterator
• type LessFunc
• type Node
• type Tree
  • func New(lessfunc LessFunc) *Tree
  • func (t *Tree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator)
  • func (t *Tree) Delete(key Item) Item
  • func (t *Tree) DeleteMax() Item
  • func (t *Tree) DeleteMin() Item
  • func (t *Tree) DescendLessOrEqual(pivot Item, iterator ItemIterator)
  • 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() int
  • 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)

Types

type Item

type Item interface{}

type ItemIterator

type ItemIterator func(i Item) bool

type LessFunc

type LessFunc func(a, b interface{}) bool

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 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 New

func New(lessfunc LessFunc) *Tree

New() allocates a new tree

func (*Tree) AscendGreaterOrEqual

func (t *Tree) 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 (*Tree) Delete

func (t *Tree) 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 (*Tree) DeleteMax

func (t *Tree) DeleteMax() Item

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

func (*Tree) DeleteMin

func (t *Tree) DeleteMin() Item

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

func (*Tree) DescendLessOrEqual

func (t *Tree) 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 (*Tree) Get

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

Get retrieves an element from the tree whose LessThan order equals that of key.

func (*Tree) GetHeight

func (t *Tree) 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 (*Tree) Has

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

Has returns true if the tree contains an element whose LessThan order equals that of key.

func (*Tree) HeightStats

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

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

func (*Tree) Init

func (t *Tree) Init(lessfunc LessFunc)

Init resets (empties) the tree

func (*Tree) InsertNoReplace

func (t *Tree) InsertNoReplace(item Item)

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

func (*Tree) InsertNoReplaceBulk

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

func (*Tree) IterAscend

func (t *Tree) IterAscend() <-chan Item

IterAscend returns a chan that iterates through all elements in in ascending order. TODO: This is a deprecated interface for iteration.

func (*Tree) IterDescend

func (t *Tree) IterDescend() <-chan Item

IterDescend returns a chan that iterates through all elements in descending order. TODO: This is a deprecated interface for iteration.

func (*Tree) IterRange

func (t *Tree) IterRange(lower, upper Item) <-chan Item

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

func (t *Tree) IterRangeInclusive(lower, upper Item) <-chan Item

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

func (t *Tree) Len() int

Len returns the number of nodes in the tree.

func (*Tree) Max

func (t *Tree) Max() Item

Max returns the maximum element in the tree.

func (*Tree) Min

func (t *Tree) Min() Item

Min returns the minimum element in the tree.

func (*Tree) ReplaceOrInsert

func (t *Tree) 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 (*Tree) ReplaceOrInsertBulk

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

func (*Tree) Root

func (t *Tree) Root() *Node

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

func (*Tree) SetRoot

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

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