The highest tagged major version is
Documentation
¶
Overview ¶
Package avltree provides a self balancing binary search tree. See https://en.wikipedia.org/wiki/AVL_tree for details pertaining to the AVL tree data structure. The main methods Add, Find and Remove should behave the same as operations operating on Go's built-in map type.
Index ¶
- type Tree
- func (tree *Tree[K, V]) Add(key K, value V)
- func (tree *Tree[K, V]) All() iter.Seq2[K, V]
- func (tree *Tree[K, V]) Backward() iter.Seq2[K, V]
- func (tree *Tree[K, V]) Clear(release func(K, V))
- func (tree *Tree[K, V]) Find(key K) (V, bool)
- func (tree *Tree[K, V]) FindEqualOrGreater(key K) (K, V, bool)
- func (tree *Tree[K, V]) FindEqualOrLesser(key K) (K, V, bool)
- func (tree *Tree[K, V]) FindHighest() (K, V, bool)
- func (tree *Tree[K, V]) FindLowest() (K, V, bool)
- func (tree *Tree[K, V]) Length() int
- func (tree *Tree[K, V]) Remove(key K)
- func (tree *Tree[K, V]) Validate() (balanced, sorted bool)
- type TreeOption
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Tree ¶
type Tree[K, V any] struct { // contains filtered or unexported fields }
Tree is an AVL tree.
func New ¶
func New[K, V any](compareKeys math.Comparator[K], options ...TreeOption[K, V]) *Tree[K, V]
New creates an AVL tree using the supplied compare function and tree options. Avoid using pointer keys that are dereferenced by the compare function as modifying such keys outside of the tree invalidates the ordering invariant of the tree.
func (*Tree[K, V]) Add ¶
func (tree *Tree[K, V]) Add(key K, value V)
Add association between key and value to the tree. Any existing association for key is overwritten with key and value.
func (*Tree[K, V]) All ¶
All returns a "left to right" iterator over the tree. Any tree mutation while iterating, except for updating the value of an existing association, invalidates the iterator and iteration terminates prematurely.
func (*Tree[K, V]) Backward ¶
Backward returns a "right to left" iterator over the tree. Any tree mutation while iterating, except for updating the value of an existing association, invalidates the iterator and iteration terminates prematurely.
func (*Tree[K, V]) Clear ¶
func (tree *Tree[K, V]) Clear(release func(K, V))
Clear removes all associations from the tree. A non-nil release function is called on each association in the tree. The release function must not fail. Remove each association by itself if the release operation can fail and handle errors properly.
func (*Tree[K, V]) Find ¶
Find value associated with key. Returns the found value and true or the zero value of V and false if no assocation was found.
func (*Tree[K, V]) FindEqualOrGreater ¶
FindEqualOrGreater returns the association that match key or the immediately greater association and true. The zero values of K and V and false is returned if no assocation was found.
func (*Tree[K, V]) FindEqualOrLesser ¶
FindEqualOrLesser returns the association that match key or the association with the immediately lesser key and true. The zero values of K and V and false is returned if no assocation was found.
func (*Tree[K, V]) FindHighest ¶
FindHighest returns the association with the highest key and true. The zero value of K and V and false is returned if the tree is empty.
func (*Tree[K, V]) FindLowest ¶
FindLowest returns the association with the lowest key and true. The zero value of K and V and false is returned if the tree is empty.
type TreeOption ¶
func WithSyncPool ¶
func WithSyncPool[K, V any]() TreeOption[K, V]
WithSyncPool creates a tree option to use a sync.Pool to reuse nodes to reduce pressure on the garbage collector. It may improve performance for trees with lots of updates. The option holds an instance of a sync.Pool that may be used by multiple trees in multiple go routines in a safe manner.
Source Files