llrb

README

LLRB-Tree implementation for Go

Documentation

Overview

Package llrb implements LLRB 2-3 trees, based on this paper:

• https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf

A left-leaning red–black (LLRB) tree is a type of self-balancing binary search tree. It is a variant of the red–black tree and guarantees the same asymptotic complexity for operations, but is designed to be easier to implement.

Index

• type CompareFunc
• type IterFunc
• type LLRBTree
  • func New[T any](compare CompareFunc[T]) *LLRBTree[T]
  • func (t *LLRBTree[T]) Ascend(iter IterFunc[T])
  • func (t *LLRBTree[T]) AscendGreaterOrEqual(pivot T, iter IterFunc[T])
  • func (t *LLRBTree[T]) AscendLessThan(pivot T, iter IterFunc[T])
  • func (t *LLRBTree[T]) AscendRange(greaterOrEqual, lessThan T, iter IterFunc[T])
  • func (t *LLRBTree[T]) Clear()
  • func (t *LLRBTree[T]) Delete(item T) (deleted T, ok bool)
  • func (t *LLRBTree[T]) DeleteMax() (deleted T, ok bool)
  • func (t *LLRBTree[T]) DeleteMin() (deleted T, ok bool)
  • func (t *LLRBTree[T]) Descend(iter IterFunc[T])
  • func (t *LLRBTree[T]) DescendGreaterThan(pivot T, iter IterFunc[T])
  • func (t *LLRBTree[T]) DescendLessOrEqual(pivot T, iter IterFunc[T])
  • func (t *LLRBTree[T]) DescendRange(lessOrEqual, greaterThan T, iter IterFunc[T])
  • func (t *LLRBTree[T]) Get(item T) (T, bool)
  • func (t *LLRBTree[T]) Has(item T) bool
  • func (t *LLRBTree[T]) Len() int
  • func (t *LLRBTree[T]) ReplaceOrInsert(item T) (prev T, exist bool)

Types

type CompareFunc

type CompareFunc[T any] func(a, b T) int

type IterFunc

type IterFunc[T any] func(a T) bool

type LLRBTree

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

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

func New

func New[T any](compare CompareFunc[T]) *LLRBTree[T]

New creates a new LLRB-Tree with the given compare function.

func (*LLRBTree[T]) Ascend

func (t *LLRBTree[T]) Ascend(iter IterFunc[T])

Ascend calls the iterator for every value in the tree within the range [first, last], until iterator returns false.

func (*LLRBTree[T]) AscendGreaterOrEqual

func (t *LLRBTree[T]) AscendGreaterOrEqual(pivot T, iter IterFunc[T])

AscendGreaterOrEqual calls the iterator for every value in the tree within the range [pivot, last], until iterator returns false.

func (*LLRBTree[T]) AscendLessThan

func (t *LLRBTree[T]) AscendLessThan(pivot T, iter IterFunc[T])

AscendLessThan calls the iterator for every value in the tree within the range [first, pivot), until iterator returns false.

func (*LLRBTree[T]) AscendRange

func (t *LLRBTree[T]) AscendRange(greaterOrEqual, lessThan T, iter IterFunc[T])

AscendRange calls the iterator for every value in the tree within the range [greaterOrEqual, lessThan), until iterator returns false.

func (*LLRBTree[T]) Clear

func (t *LLRBTree[T]) Clear()

Clear removes all items from the LLRB-Tree.

func (*LLRBTree[T]) Delete

func (t *LLRBTree[T]) Delete(item T) (deleted T, ok bool)

Delete removes an item equal to the passed in item from the tree, returning it. If no such item exists, returns nil.

func (*LLRBTree[T]) DeleteMax

func (t *LLRBTree[T]) DeleteMax() (deleted T, ok bool)

DeleteMax removes the largest item in the tree and returns it. If no such item exists, returns nil.

func (*LLRBTree[T]) DeleteMin

func (t *LLRBTree[T]) DeleteMin() (deleted T, ok bool)

DeleteMin removes the smallest item in the tree and returns it. If no such item exists, returns nil.

func (*LLRBTree[T]) Descend

func (t *LLRBTree[T]) Descend(iter IterFunc[T])

Descend calls the iterator for every value in the tree within the range [last, first], until iterator returns false.

func (*LLRBTree[T]) DescendGreaterThan

func (t *LLRBTree[T]) DescendGreaterThan(pivot T, iter IterFunc[T])

DescendGreaterThan calls the iterator for every value in the tree within the range [last, pivot), until iterator returns false.

func (*LLRBTree[T]) DescendLessOrEqual

func (t *LLRBTree[T]) DescendLessOrEqual(pivot T, iter IterFunc[T])

DescendLessOrEqual calls the iterator for every value in the tree within the range [pivot, first], until iterator returns false.

func (*LLRBTree[T]) DescendRange

func (t *LLRBTree[T]) DescendRange(lessOrEqual, greaterThan T, iter IterFunc[T])

DescendRange calls the iterator for every value in the tree within the range [lessOrEqual, greaterThan), until iterator returns false.

func (*LLRBTree[T]) Get

func (t *LLRBTree[T]) Get(item T) (T, bool)

Get looks for the key item in the tree, returning it. It returns (zeroValue, false) if unable to find that item.

func (*LLRBTree[T]) Has

func (t *LLRBTree[T]) Has(item T) bool

Has returns true if the given key is in the tree.

func (*LLRBTree[T]) Len

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

Len returns the number of items currently in the tree.

func (*LLRBTree[T]) ReplaceOrInsert

func (t *LLRBTree[T]) ReplaceOrInsert(item T) (prev T, exist bool)

ReplaceOrInsert adds the given item to the tree. If an item in the tree already equals the given one, it is removed from the tree and returned, and the second return value is true. Otherwise, (zeroValue, false)

nil cannot be added to the tree (will panic).