immutable_rb_tree

Documentation

Overview

Implementation of Red-Black Trees in a Functional Setting

References: - Insertion: https://www.cs.tufts.edu/comp/150FP/archive/chris-okasaki/redblack99.pdf - Deletion: https://matt.might.net/articles/red-black-delete/

Index

• type RBTree
  • func FromValues[Value any](cmp comparator.Comparator[Value], values ...Value) *RBTree[Value]
  • func New[Value any](cmp comparator.Comparator[Value]) *RBTree[Value]
  • func (rbTree *RBTree[Value]) All() iter.Seq[Value]
  • func (rbTree *RBTree[Value]) Count() int
  • func (rbTree *RBTree[Value]) Delete(value Value) (newTree *RBTree[Value], affected bool)
  • func (rbTree *RBTree[Value]) Empty() bool
  • func (rbTree *RBTree[Value]) InorderTraversal() iter.Seq[Value]
  • func (rbTree *RBTree[Value]) Insert(value Value) (newTree *RBTree[Value], affected bool)
  • func (rbTree *RBTree[Value]) Lookup(value Value) *Value
  • func (rbTree *RBTree[Value]) Maximum() Value
  • func (rbTree *RBTree[Value]) Minimum() Value
  • func (rbTree *RBTree[Value]) Values() []Value

Types

type RBTree

type RBTree[Value any] struct {
	// contains filtered or unexported fields
}

The zero value of `RBTree` makes nonsense.

func FromValues

func FromValues[Value any](cmp comparator.Comparator[Value], values ...Value) *RBTree[Value]

func New

func New[Value any](cmp comparator.Comparator[Value]) *RBTree[Value]

func (*RBTree[Value]) All

func (rbTree *RBTree[Value]) All() iter.Seq[Value]

`All()` Returns an iterator of all values in an in-order traversal.

func (*RBTree[Value]) Count

func (rbTree *RBTree[Value]) Count() int

func (*RBTree[Value]) Delete

func (rbTree *RBTree[Value]) Delete(value Value) (newTree *RBTree[Value], affected bool)

`affected` is true, meaning that a real deletion occurred, `newTree` will be different from the original; otherwise nothing happens, `newTree` is the original one.

func (*RBTree[Value]) Empty

func (rbTree *RBTree[Value]) Empty() bool

func (*RBTree[Value]) InorderTraversal

func (rbTree *RBTree[Value]) InorderTraversal() iter.Seq[Value]

func (*RBTree[Value]) Insert

func (rbTree *RBTree[Value]) Insert(value Value) (newTree *RBTree[Value], affected bool)

`newTree` returned by `Insert()` is always different from the original one. `affected` is true, meaning an actual insertion occurred; otherwise, a replacement occurred.

func (*RBTree[Value]) Lookup

func (rbTree *RBTree[Value]) Lookup(value Value) *Value

func (*RBTree[Value]) Maximum

func (rbTree *RBTree[Value]) Maximum() Value

CAUTION: Only invoke `Maximum` with non-empty RBTree.

func (*RBTree[Value]) Minimum

func (rbTree *RBTree[Value]) Minimum() Value

CAUTION: Only invoke `Minimum` with non-empty RBTree.

func (*RBTree[Value]) Values

func (rbTree *RBTree[Value]) Values() []Value