rbtree

Documentation

Index

• type ItemIterator
• type LLRB
  • func New[T cmp.Ordered]() *LLRB[T]
  • func NewFunc[T any](less algorithm.LessFunc[T]) *LLRB[T]
  • func (t *LLRB[T]) AscendGreaterOrEqual(pivot T, iterator ItemIterator[T])
  • func (t *LLRB[T]) AscendLessThan(pivot T, iterator ItemIterator[T])
  • func (t *LLRB[T]) AscendRange(greaterOrEqual, lessThan T, iterator ItemIterator[T])
  • func (t *LLRB[T]) Delete(key T) (deletedItem T, deleted bool)
  • func (t *LLRB[T]) DeleteMax() (deletedItem T, deleted bool)
  • func (t *LLRB[T]) DeleteMin() (deletedItem T, deleted bool)
  • func (t *LLRB[T]) DescendLessOrEqual(pivot T, iterator ItemIterator[T])
  • func (t *LLRB[T]) Get(key T) (item T, present bool)
  • func (t *LLRB[T]) Has(key T) bool
  • func (t *LLRB[T]) Insert(item T)
  • func (t *LLRB[T]) Len() int
  • func (t *LLRB[T]) Max() (item T, present bool)
  • func (t *LLRB[T]) Min() (item T, present bool)
  • func (t *LLRB[T]) ReverseScan(iterator ItemIterator[T])
  • func (t *LLRB[T]) Root() *Node[T]
  • func (t *LLRB[T]) Scan(iterator ItemIterator[T])
  • func (t *LLRB[T]) SetRoot(r *Node[T])
  • func (t *LLRB[T]) Upsert(item T) (replacedItem T, replaced bool)
  • func (t *LLRB[T]) Values() []T
• type Node

Types

type ItemIterator

type ItemIterator[T any] func(i T) bool

ItemIterator is a function to iterate through items.

type LLRB

type LLRB[T any] struct {
	// contains filtered or unexported fields
}

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

func New

func New[T cmp.Ordered]() *LLRB[T]

New allocates a new tree

func NewFunc

func NewFunc[T any](less algorithm.LessFunc[T]) *LLRB[T]

NewFunc creates a new LLRB tree using less.

func (*LLRB[T]) AscendGreaterOrEqual

func (t *LLRB[T]) AscendGreaterOrEqual(pivot T, iterator ItemIterator[T])

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[T]) AscendLessThan

func (t *LLRB[T]) AscendLessThan(pivot T, iterator ItemIterator[T])

AscendLessThan will call iterator once for each element lower than pivot in ascending order. It will stop whenever the iterator returns false.

func (*LLRB[T]) AscendRange

func (t *LLRB[T]) AscendRange(greaterOrEqual, lessThan T, iterator ItemIterator[T])

func (*LLRB[T]) Delete

func (t *LLRB[T]) Delete(key T) (deletedItem T, deleted bool)

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

func (*LLRB[T]) DeleteMax

func (t *LLRB[T]) DeleteMax() (deletedItem T, deleted bool)

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

func (*LLRB[T]) DeleteMin

func (t *LLRB[T]) DeleteMin() (deletedItem T, deleted bool)

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

func (*LLRB[T]) DescendLessOrEqual

func (t *LLRB[T]) DescendLessOrEqual(pivot T, iterator ItemIterator[T])

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[T]) Get

func (t *LLRB[T]) Get(key T) (item T, present bool)

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

func (*LLRB[T]) Has

func (t *LLRB[T]) Has(key T) bool

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

func (*LLRB[T]) Insert

func (t *LLRB[T]) Insert(item T)

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

func (*LLRB[T]) Len

func (t *LLRB[T]) Len() int

Len returns the number of nodes in the tree.

func (*LLRB[T]) Max

func (t *LLRB[T]) Max() (item T, present bool)

Max returns the maximum element in the tree.

func (*LLRB[T]) Min

func (t *LLRB[T]) Min() (item T, present bool)

Min returns the minimum element in the tree.

func (*LLRB[T]) ReverseScan

func (t *LLRB[T]) ReverseScan(iterator ItemIterator[T])

ReverseScan will call iterator once for each element in descending order. It will stop whenever the iterator returns false.

func (*LLRB[T]) Root

func (t *LLRB[T]) Root() *Node[T]

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

func (*LLRB[T]) Scan

func (t *LLRB[T]) Scan(iterator ItemIterator[T])

Scan will call iterator once for each element in ascending order. It will stop whenever the iterator returns false.

func (*LLRB[T]) SetRoot

func (t *LLRB[T]) SetRoot(r *Node[T])

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

func (*LLRB[T]) Upsert

func (t *LLRB[T]) Upsert(item T) (replacedItem T, replaced bool)

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

func (*LLRB[T]) Values

func (t *LLRB[T]) Values() []T

Values returns all values from the tree in order.

type Node

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

}

Node represents a node in LLRB.