README
¶
goavl
An AVL tree implementation in Go.
Badges
Installation
To start using this package, run:
$ go get github.com/avdva/goavl
Features
- Support for Go generics (Go 1.18+).
- Forward and reverse iterators.
- Provides an efficient way of getting items by index (if
CountChildrenis on).
API
create:
New[int, int](intCmp, WithCountChildren(true)) // creates a new int --> int tree.
NewComparable[int, int]() // Works for the keys that satisfy constraints.Ordered.
search:
Find(k K) (v *V, found bool) // finds a value for given key.
Min() (entry Entry[K, V], found bool) // returns the minimum element of the array.
Max() (entry Entry[K, V], found bool) // returns the maximum element of the array.
At(position int) Entry[K, V] // returns the i'th element.
Len() int // returns the number of elements.
modify:
Insert(k K, v V) (v *V, inserted bool) // inserts a kv pair.
Delete(k K) (v V, deleted bool) // deletes a value.
DeleteAt(position int) (k K, v V) // deletes the i'th element.
Clear() // deletes all the elements.
iterate:
AscendFromStart() Iterator[K, V] // returns an iterator pointing to the smallest element.
DescendFromEnd() Iterator[K, V] // returns an iterator pointing to the largest element.
Ascend(from K) Iterator[K, V] // returns an iterator pointing to the element that's >= `from`.
Descend(from K) Iterator[K, V] // returns an iterator pointing to the element that's <= `from`.
AscendAt(position int) Iterator[K, V] // returns an iterator pointing to the i'th element.
Please see the examples for more details.
Contact
License
Source code is available under the Apache License Version 2.0.
Documentation
¶
Index ¶
- type Entry
- type Iterator
- type Option
- type Options
- type Tree
- 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]) 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 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 usage of the `At` function.
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]) 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]) 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