README
¶
avl
import "github.com/fufuok/utils/generic/avl"
Package avl provides an implementation of an AVL tree. An AVL tree is a self-balancing binary search tree. It stores key-value pairs that are sorted based on the key, and maintains that the tree is always balanced, ensuring logarithmic-time for all operations.
Example
package main
import (
"fmt"
g "github.com/fufuok/utils/generic"
"github.com/fufuok/utils/generic/avl"
)
func main() {
tree := avl.New[int, string](g.Less[int])
tree.Put(42, "foo")
tree.Put(-10, "bar")
tree.Put(0, "baz")
tree.Put(10, "quux")
tree.Remove(10)
tree.Each(func(key int, val string) {
fmt.Println(key, val)
})
}
Output
-10 bar
0 baz
42 foo
Index
type Tree
Tree implements an AVL tree.
type Tree[K, V any] struct {
// contains filtered or unexported fields
}
func New
func New[K, V any](less g.LessFn[K]) *Tree[K, V]
New returns an empty AVL tree.
func (*Tree[K, V]) Each
func (t *Tree[K, V]) Each(fn func(key K, val V))
Each calls 'fn' on every node in the tree in order
func (*Tree[K, V]) Get
func (t *Tree[K, V]) Get(key K) (V, bool)
Get returns the value associated with 'key'.
func (*Tree[K, V]) Height
func (t *Tree[K, V]) Height() int
Height returns the height of the tree.
func (*Tree[K, V]) Put
func (t *Tree[K, V]) Put(key K, value V)
Put associates 'key' with 'value'.
func (*Tree[K, V]) Remove
func (t *Tree[K, V]) Remove(key K)
Remove removes the value associated with 'key'.
func (*Tree[K, V]) Size
func (t *Tree[K, V]) Size() int
Size returns the number of elements in the tree.
Generated by gomarkdoc
Documentation
¶
Overview ¶
Package avl provides an implementation of an AVL tree. An AVL tree is a self-balancing binary search tree. It stores key-value pairs that are sorted based on the key, and maintains that the tree is always balanced, ensuring logarithmic-time for all operations.
Example ¶
package main
import (
"fmt"
g "github.com/fufuok/utils/generic"
"github.com/fufuok/utils/generic/avl"
)
func main() {
tree := avl.New[int, string](g.Less[int])
tree.Put(42, "foo")
tree.Put(-10, "bar")
tree.Put(0, "baz")
tree.Put(10, "quux")
tree.Remove(10)
tree.Each(func(key int, val string) {
fmt.Println(key, val)
})
}
Output: -10 bar 0 baz 42 foo
Index ¶
Examples ¶
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 implements an AVL tree.
func (*Tree[K, V]) Each ¶
func (t *Tree[K, V]) Each(fn func(key K, val V))
Each calls 'fn' on every node in the tree in order
func (*Tree[K, V]) Put ¶
func (t *Tree[K, V]) Put(key K, value V)
Put associates 'key' with 'value'.
Source Files