redblack

Documentation

Index

• type Tree
  • func New[K, V any](compareFunc func(a, b K) int) *Tree[K, V]
  • func (t *Tree[K, V]) Count() int
  • func (t *Tree[K, V]) Dump()
  • func (t *Tree[K, V]) Empty() bool
  • func (t *Tree[K, V]) First() (value V, exists bool)
  • func (t *Tree[K, V]) Get(key K) (value V, exists bool)
  • func (t *Tree[K, V]) Insert(key K, value V)
  • func (t *Tree[K, V]) Last() (value V, exists bool)
  • func (t *Tree[K, V]) Remove(key K)
  • func (t *Tree[K, V]) ReverseTraverse(visitorFunc func(key K, value V) bool)
  • func (t *Tree[K, V]) ReverseTraverseStartingAt(key K, visitorFunc func(key K, value V) bool)
  • func (t *Tree[K, V]) Traverse(visitorFunc func(key K, value V) bool)
  • func (t *Tree[K, V]) TraverseStartingAt(key K, visitorFunc func(key K, value V) bool)

Types

type Tree

type Tree[K, V any] struct {
	// contains filtered or unexported fields
}

Tree implements a Red-black Tree, as described here: https://en.wikipedia.org/wiki/Red–black_tree

func New

func New[K, V any](compareFunc func(a, b K) int) *Tree[K, V]

New creates a new red-black tree.

func (*Tree[K, V]) Count

func (t *Tree[K, V]) Count() int

Count returns the number of nodes in the tree.

func (*Tree[K, V]) Dump

func (t *Tree[K, V]) Dump()

Dump a text version of the tree for debugging purposes.

func (*Tree[K, V]) Empty

func (t *Tree[K, V]) Empty() bool

Empty returns true if the tree is empty.

func (*Tree[K, V]) First

func (t *Tree[K, V]) First() (value V, exists bool)

First returns the first value in the tree.

func (*Tree[K, V]) Get

func (t *Tree[K, V]) Get(key K) (value V, exists bool)

Get returns the first value that matches the given key.

func (*Tree[K, V]) Insert

func (t *Tree[K, V]) Insert(key K, value V)

Insert a node into the tree.

func (*Tree[K, V]) Last

func (t *Tree[K, V]) Last() (value V, exists bool)

Last returns the last value in the tree.

func (*Tree[K, V]) Remove

func (t *Tree[K, V]) Remove(key K)

Remove a node from the tree. Note that if the key is not unique within the tree, the first key that matches on traversal will be chosen as the one to remove.

func (*Tree[K, V]) ReverseTraverse

func (t *Tree[K, V]) ReverseTraverse(visitorFunc func(key K, value V) bool)

ReverseTraverse traverses the tree, calling visitorFunc for each node, in reverse order. If the visitorFunc returns false, the traversal will be aborted.

func (*Tree[K, V]) ReverseTraverseStartingAt

func (t *Tree[K, V]) ReverseTraverseStartingAt(key K, visitorFunc func(key K, value V) bool)

ReverseTraverseStartingAt traverses the tree starting with the last node whose key is equal to or less than the given key, calling visitorFunc for each node, in order. If the visitorFunc returns false, the traversal will be aborted.

func (*Tree[K, V]) Traverse

func (t *Tree[K, V]) Traverse(visitorFunc func(key K, value V) bool)

Traverse the tree, calling visitorFunc for each node, in order. If the visitorFunc returns false, the traversal will be aborted.

func (*Tree[K, V]) TraverseStartingAt

func (t *Tree[K, V]) TraverseStartingAt(key K, visitorFunc func(key K, value V) bool)

TraverseStartingAt traverses the tree starting with the first node whose key is equal to or greater than the given key, calling visitorFunc for each node, in order. If the visitorFunc returns false, the traversal will be aborted.