README
¶
goavl
An AVL tree implementation in Go.
Badges
Installation
Package goavl requires Go 1.20+. To start, run:
$ go get github.com/avdva/goavl
Features
- Support for Go generics.
- Forward and reverse iterators.
- Go 1.23 style iterators support.
- Provides an efficient way of getting items by index (if
CountChildrenis on).
API
// Constructors:
// New creates a tree with a user-defined comparator:
//
// func intCmp(a, b int) int {
// if a < b {
// return -1
// }
// if a > b {
// return 1
// }
// return 0
// }
// tree := New[int, int](intCmp, WithCountChildren(true))
//
// Options:
// - WithCountChildren(bool) enables O(logn) complexity for the functions that operate
// on element positions.
// - WithSyncPool(*sync.Pool) makes Tree use sync.Pool to allocate tree nodes.
// - WithArena(*arena.Arena) makes Tree use arenas (currently experimental) to allocate
// tree nodes. This requires GOEXPERIMENT=arenas to be set.
New[K, V any, Cmp func(a, b K) int](cmp Cmp, opts ...Option) *Tree[K, V, Cmp] {}
// NewComparable works for the keys that satisfy constraints.Ordered.
NewComparable[K constraints.Ordered, V any](opts ...Option) *Tree[K, V, func(a, b K) int] {}
// Search for elements:
// Find finds a value for given key.
Find(k K) (v *V, found bool) {}
// Min returns the minimum element of the tree.
Min() (entry Entry[K, V], found bool) {}
// Max returns the maximum element of the tree.
Max() (entry Entry[K, V], found bool) {}
// At returns the i'th element of the tree.
At(position int) Entry[K, V] {}
// Len returns the number of elements.
Len() int {}
// Tree modifications:
// Insert inserts a kv pair.
Insert(k K, v V) (v *V, inserted bool) {}
// Delete deletes a key.
Delete(k K) (v V, deleted bool) {}
// DeleteAt deletes i'th element.
DeleteAt(position int) (k K, v V) {}
// DeleteIterator deletes the element pointed at by it.
DeleteIterator(it Iterator[K, V]) {}
// Clear deletes all the elements.
Clear() {}
// Iterators:
// AscendFromStart returns an iterator pointing to the smallest element.
AscendFromStart() Iterator[K, V] {}
// DescendFromEnd returns an iterator pointing to the largest element.
DescendFromEnd() Iterator[K, V] {}
// Ascend returns an iterator pointing to the element that's >= `from`.
Ascend(from K) Iterator[K, V] {}
// Descend returns an iterator pointing to the element that's <= `from`.
Descend(from K) Iterator[K, V] {}
// AscendAt returns an iterator pointing to the i'th element.
AscendAt(position int) Iterator[K, V]
/*
Go 1.23 iterators are also supported:
for k, v := range tree.All() {
fmt.Printf("k: %d, v: %d\n", k, v)
}
*/
Please see the examples, new Go 1.23 examples and arena examples for more details.
Contact
License
Source code is available under the Apache License Version 2.0.
Documentation
¶
Index ¶
- type Entry
- type Iterator
- type Mutator
- type Option
- type Options
- type Tree
- func (t *Tree[K, V, Cmp]) All() iter.Seq2[K, V]
- func (t *Tree[K, V, Cmp]) AllMut() iter.Seq[*Mutator[K, V, Cmp]]
- func (t *Tree[K, V, Cmp]) Ascend(from K) Iterator[K, V]
- func (t *Tree[K, V, Cmp]) AscendAt(position int) Iterator[K, V]
- func (t *Tree[K, V, Cmp]) AscendFromStart() Iterator[K, V]
- func (t *Tree[K, V, Cmp]) At(position int) Entry[K, V]
- func (t *Tree[K, V, Cmp]) Clear()
- func (t *Tree[K, V, Cmp]) Delete(k K) (v V, deleted bool)
- func (t *Tree[K, V, Cmp]) DeleteAt(position int) (k K, v V)
- func (t *Tree[K, V, Cmp]) DeleteIterator(it Iterator[K, V]) Iterator[K, V]
- func (t *Tree[K, V, Cmp]) Descend(from K) Iterator[K, V]
- func (t *Tree[K, V, Cmp]) DescendFromEnd() Iterator[K, V]
- func (t *Tree[K, V, Cmp]) Find(k K) (v *V, found bool)
- func (t *Tree[K, V, Cmp]) Insert(k K, v V) (valuePtr *V, inserted bool)
- func (t *Tree[K, V, Cmp]) Len() int
- func (t *Tree[K, V, Cmp]) Max() (entry Entry[K, V], found bool)
- func (t *Tree[K, V, Cmp]) Min() (entry Entry[K, V], found bool)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Entry ¶ added in v1.0.0
type Entry[K, V any] struct { Key K Value *V }
Entry is a pair of a key and a pointer to the value.
type Iterator ¶ added in v0.2.0
type Iterator[K, V any] struct { // contains filtered or unexported fields }
Iterator allows to iterate over a tree in ascending or descending order.
type Mutator ¶ added in v1.4.0
type Mutator[K, V any, Cmp func(a, b K) int] struct { E Entry[K, V] // contains filtered or unexported fields }
Mutator allows to modify values and delete keys from a tree in a for-range loop. Use mut.E.K and mut.E.V to access keys and modify values. Use Delete to delete current key from the tree.
type Option ¶
type Option func(o *Options)
Option is a function type used to configure tree's behavior.
func WithCountChildren ¶
WithCountChildren is used to set CountChildren option. If set, each node will have a count of children in the left and right sub-trees. This enables O(logn) complexity for the functions that operate key positions.
func WithSyncPool ¶ added in v1.6.0
WithSyncPool makes Tree use sync.Pool to allocate tree nodes. 's' can be nil. In this case new pool is created for each tree. if 's' is not nil, one pool can be shared between several instances of a tree, however
- all instances should be of the same generic type.
- s.New must be nil.
func WithSyncPoolAllocator ¶ added in v1.5.0
WithSyncPoolAllocator makes Tree use sync.Pool to allocate tree nodes. Deprecated: use WithSyncPool instead.
type Options ¶
type Options struct {
// contains filtered or unexported fields
}
Options defines some parameters of the tree.
type Tree ¶
Tree is a generic avl tree. AVL tree (https://en.wikipedia.org/wiki/AVL_tree) is a self-balancing binary search tree. For each node of the tree the heights of the left and right sub-trees differ by at most one. Find and Delete operations have O(logn) complexity.
Example ¶
// Define a new tree explicitly.
// Note that the comparator is a third generic argument.
// It allows Go compiler (but not forces it) to inline the comparator.
var _ *Tree[string, string, func(a, b string) int]
// if you use New(), the third generic argument can be omitted.
// in the options we specify `WithCountChildren` allowing `At` operation.
tree := New[string, string](func(a, b string) int {
if a < b {
return -1
}
if a > b {
return 1
}
return 0
}, WithCountChildren(true))
// insert some values
tree.Insert("a", "a")
tree.Insert("z", "z")
tree.Insert("m", "m")
tree.Insert("l", "l")
tree.Insert("b", "b")
// print tree, ascending
fmt.Println("tree, normal order")
fwdIt := tree.AscendFromStart()
for {
e, ok := fwdIt.Next()
if !ok {
break
}
fmt.Printf("k: %s, v: %s\n", e.Key, *e.Value)
}
// print tree, descending
fmt.Println("tree, reverse order")
revIt := tree.DescendFromEnd()
for {
e, ok := revIt.Prev()
if !ok {
break
}
fmt.Printf("k: %s, v: %s\n", e.Key, *e.Value)
}
v, found := tree.Find("b")
if found {
fmt.Printf("the value for 'b' is '%s'\n", *v)
}
e := tree.At(2)
fmt.Printf("the kv at position 2 is %s: %s", e.Key, *e.Value)
Output: tree, normal order k: a, v: a k: b, v: b k: l, v: l k: m, v: m k: z, v: z tree, reverse order k: z, v: z k: m, v: m k: l, v: l k: b, v: b k: a, v: a the value for 'b' is 'b' the kv at position 2 is l: l
func New ¶
New returns a new Tree. K - key type, V - value type can be any types, one only has to define a comparator func: func(a, b K) int that should return
-1, if a < b 0, if a == b 1, if a > b
Example:
func intCmp(a, b int) int {
if a < b {
return -1
}
if a > b {
return 1
}
return 0
}
tree := New[int, int](intCmp, WithCountChildren(true)).
func NewComparable ¶ added in v0.2.0
NewComparable returns a new tree. This is just a wrapper for New(), where K satisfies constraints.Ordered. Example: NewComparable[int, int]().
Example ¶
// no need to specify a comparator for NewComparable().
tree := NewComparable[int, int]()
for _, v := range [...]int{7, 1, 3, 10, 2} {
valuePtr, inserted := tree.Insert(v, v)
if !inserted || *valuePtr != v {
panic("invalid insert result")
}
}
fmt.Println("tree, normal order")
fwdIt := tree.AscendFromStart()
for {
e, ok := fwdIt.Value()
if !ok {
break
}
fmt.Printf("k: %d, v: %d\n", e.Key, *e.Value)
fwdIt.Next()
}
Output: tree, normal order k: 1, v: 1 k: 2, v: 2 k: 3, v: 3 k: 7, v: 7 k: 10, v: 10
func (*Tree[K, V, Cmp]) All ¶ added in v1.4.0
All returns an iterator over the tree's kv pairs. It can be used in a for-range loop (Go 1.23+).
Example ¶
// no need to specify a comparator for NewComparable().
tree := NewComparable[int, int]()
for _, v := range [...]int{7, 1, 3, 10, 2} {
valuePtr, inserted := tree.Insert(v, v)
if !inserted || *valuePtr != v {
panic("invalid insert result")
}
}
fmt.Println("tree, normal order")
for k, v := range tree.All() {
fmt.Printf("k: %d, v: %d\n", k, v)
}
Output: tree, normal order k: 1, v: 1 k: 2, v: 2 k: 3, v: 3 k: 7, v: 7 k: 10, v: 10
func (*Tree[K, V, Cmp]) AllMut ¶ added in v1.4.0
AllMut returns an iterator over the tree's kv pairs. Unlike Mut(), for-range loop will iterate over a sequence of Mutator objects. Via a Mutator object one can change a value, or delete current element from the tree.
Example ¶
// no need to specify a comparator for NewComparable().
tree := NewComparable[int, int]()
for _, v := range [...]int{7, 1, 3, 10, 2} {
valuePtr, inserted := tree.Insert(v, v)
if !inserted || *valuePtr != v {
panic("invalid insert result")
}
}
fmt.Println("tree, before modifications")
for m := range tree.AllMut() {
fmt.Printf("k: %d, v: %d\n", m.E.Key, *m.E.Value)
*m.E.Value *= 2
if m.E.Key == 2 {
m.Delete()
}
}
fmt.Println("tree, after modifications")
for m := range tree.AllMut() {
fmt.Printf("k: %d, v: %d\n", m.E.Key, *m.E.Value)
}
Output: tree, before modifications k: 1, v: 1 k: 2, v: 2 k: 3, v: 3 k: 7, v: 7 k: 10, v: 10 tree, after modifications k: 1, v: 2 k: 3, v: 6 k: 7, v: 14 k: 10, v: 20
func (*Tree[K, V, Cmp]) Ascend ¶ added in v0.3.0
Ascend returns an iterator pointing to the element that's >= `from`.
func (*Tree[K, V, Cmp]) AscendAt ¶ added in v1.3.0
AscendAt returns an iterator pointing to the i'th element. Panics if position >= tree.Len(). Time complexity:
O(logn) - if children node counts are enabled. O(n) - otherwise.
func (*Tree[K, V, Cmp]) AscendFromStart ¶ added in v0.3.0
AscendFromStart returns an iterator pointing to the minimum element.
func (*Tree[K, V, Cmp]) At ¶
At returns a (key, value) pair at the ith position of the sorted array. Panics if position >= tree.Len(). Time complexity:
O(logn) - if children node counts are enabled. O(n) - otherwise.
func (*Tree[K, V, Cmp]) Delete ¶
Delete deletes a node from the tree. Returns node's value and true, if the node was present in the tree. Time complexity: O(logn).
func (*Tree[K, V, Cmp]) DeleteAt ¶ added in v0.2.0
DeleteAt deletes a node at the given position. Returns node's value. Panics if position >= tree.Len(). Time complexity:
O(logn) - if children node counts are enabled. O(n) - otherwise.
func (*Tree[K, V, Cmp]) DeleteIterator ¶ added in v1.4.0
DeleteIterator deletes the element referenced by the iterator. Returns iterator to the next element. Time complexity: O(logn).
func (*Tree[K, V, Cmp]) Descend ¶ added in v0.3.0
Descend returns an iterator pointing to the element that's <= `from`.
func (*Tree[K, V, Cmp]) DescendFromEnd ¶ added in v0.3.0
DescendFromEnd returns an iterator pointing to the maximum element.
func (*Tree[K, V, Cmp]) Insert ¶
Insert inserts a node into the tree. Returns a pointer to the value and true, if a new node was added. If the key `k` was present in the tree, node's value is updated to `v`. Time complexity: O(logn).
Source Files