bst

Documentation

Overview

Package bst provides a simple key-value pair accepting Bst implementation and a Keyless variant for user-defined key generation based on provided values.

Index

• type Bst
  • func New[K cmp.Ordered, V any]() *Bst[K, V]
  • func (bst *Bst[K, V]) Contains(key K) bool
  • func (bst *Bst[K, V]) Delete(key K) (removed bool)
  • func (bst *Bst[K, V]) Len() int
  • func (bst *Bst[K, V]) Put(key K, value V) (added bool)
  • func (bst *Bst[K, V]) String() (inOrder string)
• type KeyFunc
• type Keyless
  • func NewKeyless[K cmp.Ordered, V any](generateKey KeyFunc[K, V]) *Keyless[K, V]
  • func (k *Keyless[K, V]) Contains(value V) bool
  • func (k *Keyless[K, V]) Delete(value V) (removed bool)
  • func (k *Keyless[K, V]) Len() int
  • func (k *Keyless[K, V]) Put(value V) (added bool)
  • func (k *Keyless[K, V]) String() string

Types

type Bst

type Bst[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Bst is the simplest implementation of a binary search tree. It provides logarithmic O(log n) operation for insertion, deletion and search. This variant provides no self-balancing, so worst-case (insertion of a sequence e.g. 1, 2, 3...) the tree performs at the level of a linked list O(n).

func New

func New[K cmp.Ordered, V any]() *Bst[K, V]

New returns a new and empty *Bst[Key, Value].

func (*Bst[K, V]) Contains

func (bst *Bst[K, V]) Contains(key K) bool

Contains implements obt.Obt.Contains.

func (*Bst[K, V]) Delete

func (bst *Bst[K, V]) Delete(key K) (removed bool)

Delete implements obt.Obt.Delete.

func (*Bst[K, V]) Len

func (bst *Bst[K, V]) Len() int

Len implements obt.Obt.Len.

func (*Bst[K, V]) Put

func (bst *Bst[K, V]) Put(key K, value V) (added bool)

Put implements obt.Obt.Put.

func (*Bst[K, V]) String

func (bst *Bst[K, V]) String() (inOrder string)

String implements fmt.Stringer by showing the tree in a slice format, ignoring keys.

type KeyFunc

type KeyFunc[K cmp.Ordered, V any] func(V) K

KeyFunc is a key generating function signature for Bst variants with no explicit keys.

type Keyless

type Keyless[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Keyless is essentially a wrapper over a normal Bst with user-provided key generation out of inserted values. The overhead is miniscule (~15-20 nanoseconds more per op in comparison to the ordinary variant).

func NewKeyless

func NewKeyless[K cmp.Ordered, V any](generateKey KeyFunc[K, V]) *Keyless[K, V]

NewKeyless constructs a *Keyless[Key, Value] with a key generating function for ordering.

func (*Keyless[K, V]) Contains

func (k *Keyless[K, V]) Contains(value V) bool

Contains implements obt.KeylessObt.Contains

func (*Keyless[K, V]) Delete

func (k *Keyless[K, V]) Delete(value V) (removed bool)

Delete implements obt.KeylessObt.Delete

func (*Keyless[K, V]) Len

func (k *Keyless[K, V]) Len() int

Len implements obt.KeylessObt.Len

func (*Keyless[K, V]) Put

func (k *Keyless[K, V]) Put(value V) (added bool)

Put implements obt.KeylessObt.Put

func (*Keyless[K, V]) String

func (k *Keyless[K, V]) String() string

String implements fmt.Stringer by showing the tree in a slice format, ignoring keys.