README
¶
go-avltree
An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at most one and in which the left and right subtrees are again AVL trees.
With each node of an AVL tree is associated a balance factor that is Left High, Equal, or Right High according, respectively, as the left subtree has height greater than, equal to, or less than that of the right subtree.
The AVL tree is, in practice, balanced quite well. It can (at the worst case) become skewed to the left or right, but never so much that it becomes inefficient. The balancing is done as items are added or deleted.
This version is enhanced to allow "indexing" of values in the tree; however, the indexes are not stable as the tree could be resorted as items are added or removed.
It is safe to iterate or search a tree from multiple threads provided that no threads are modifying the tree.
The tree works on generic types and there is also a specialization for maps. Additionally, the tree supports iteration and a channel iterator.
t.Do(func(z int) bool {
if z % 3333 == 0 {
fmt.Printf("%d ", z)
}
return true
})
for v := range t.Iter() {
if v % 3333 == 0 {
fmt.Printf("%d ", v);
}
}
To install, you can use:
go get github.com/ancientlore/go-avltree/v2@latest
For more information on generics see:
Documentation
¶
Overview ¶
Package avltree implements a height-balanced binary tree with array-like indexing capability.
An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at most one and in which the left and right subtrees are again AVL trees.
With each node of an AVL tree is associated a balance factor that is Left High, Equal, or Right High according, respectively, as the left subtree has height greater than, equal to, or less than that of the right subtree.
The AVL tree is, in practice, balanced quite well. It can (at the worst case) become skewed to the left or right, but never so much that it becomes inefficient. The balancing is done as items are added or deleted.
This version is enhanced to allow "indexing" of values in the tree; however, the indexes are not stable as the tree could be resorted as items are added or removed.
It is safe to iterate or search a tree from multiple threads provided that no threads are modifying the tree.
See also: Robert L. Kruse, Data Structures and Program Design, 2nd Ed., Prentice-Hall
Index ¶
- Constants
- func Print[T any](t *Tree[T], w io.Writer, f func(T) bool, itemSiz int)
- func PrintMap[K, V any](m *Map[K, V], w io.Writer, f func(K, V) bool, itemSiz int)
- type Map
- func (m *Map[K, V]) Add(k K, v V) (*V, bool)
- func (m *Map[K, V]) At(index int) *Pair[K, V]
- func (m *Map[K, V]) Cap() int
- func (m *Map[K, V]) Clear()
- func (m *Map[K, V]) Do(f func(K, V) bool)
- func (m *Map[K, V]) Find(key K) *V
- func (m *Map[K, V]) Height() int
- func (m *Map[K, V]) Iter() <-chan Pair[K, V]
- func (m *Map[K, V]) IterContext(ctx context.Context) <-chan Pair[K, V]
- func (m *Map[K, V]) Keys() []K
- func (m *Map[K, V]) Len() int
- func (m *Map[K, V]) Remove(key K) *V
- func (m *Map[K, V]) RemoveAt(index int) *Pair[K, V]
- func (m *Map[K, V]) Values() []V
- type Pair
- type Tree
- func (t *Tree[T]) Add(o T) (val *T, isDupe bool)
- func (t *Tree[T]) At(index int) *T
- func (t *Tree[T]) Cap() int
- func (t *Tree[T]) Clear()
- func (t *Tree[T]) Data() []T
- func (t *Tree[T]) Do(f func(T) bool)
- func (t *Tree[T]) Find(key T) *T
- func (t *Tree[T]) Height() int
- func (t *Tree[T]) Iter() <-chan T
- func (t *Tree[T]) IterContext(ctx context.Context) <-chan T
- func (t *Tree[T]) Len() int
- func (t *Tree[T]) Remove(ptr T) *T
- func (t *Tree[T]) RemoveAt(index int) *T
Constants ¶
const (
AllowDuplicates = 1
)
tree options
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Map ¶
type Map[K, V any] struct { // contains filtered or unexported fields }
func NewMapOrdered ¶
NewMapOrdered returns an initialized map using ordered types.
func (*Map[K, V]) Add ¶
Add adds an item to the map, returning a pair indicating the added (or duplicate) item, and a flag indicating whether the item is the duplicate that was found.
func (*Map[K, V]) Cap ¶
Cap returns the capacity of the map; that is, the maximum elements the tree can hold with at the current height. This is only useful as a measure of how skewed the map is.
func (*Map[K, V]) Clear ¶
func (m *Map[K, V]) Clear()
Clear removes all elements from the map, keeping the current options and compare function.
func (*Map[K, V]) Do ¶
Do calls function f for each element of the map, in order. The function should not change the structure of the map underfoot.
func (*Map[K, V]) Find ¶
func (m *Map[K, V]) Find(key K) *V
Find returns the element where the comparison function matches the node's value and the given key value.
func (*Map[K, V]) IterContext ¶
IterContext returns a channel you can read through to fetch all the items.
func (*Map[K, V]) Remove ¶
func (m *Map[K, V]) Remove(key K) *V
Remove removes the element matching the given value.
type Tree ¶
type Tree[T any] struct { // contains filtered or unexported fields }
Tree stores data about the binary tree.
func NewOrdered ¶
NewOrdered returns an initialized tree using ordered types.
func (*Tree[T]) Add ¶
Add adds an item to the tree, returning a pair indicating the added (or duplicate) item, and a flag indicating whether the item is the duplicate that was found. A duplicate will never be returned if the tree's AllowDuplicates flag is set.
func (*Tree[T]) Cap ¶
Cap returns the capacity of the tree; that is, the maximum elements the tree can hold with at the current height. This is only useful as a measure of how skewed the tree is.
func (*Tree[T]) Clear ¶
func (t *Tree[T]) Clear()
Clear removes all elements from the tree, keeping the current options and compare function.
func (*Tree[T]) Do ¶
Do calls function f for each element of the tree, in order. The function should not change the structure of the tree underfoot.
func (*Tree[T]) Find ¶
func (t *Tree[T]) Find(key T) *T
Find returns the element where the comparison function matches the node's value and the given key value.
func (*Tree[T]) Iter ¶
func (t *Tree[T]) Iter() <-chan T
Iter returns a channel you can read through to fetch all the items.
func (*Tree[T]) IterContext ¶
IterContext returns a channel you can read through to fetch all the items.
Source Files