README
¶
go-avltree
Golang implementation of an AVL Tree. An AVL tree is a self-balancing binary search tree.
Each node in the tree has a key and a value which are currently implemented as integers. It supports the following methods: Add, Remove, Update, Search, DisplayInOrder. When adding a key that exists its value is updated with the new one.
Installation
$ go get github.com/karask/go-avltree
Example usage
package main
import (
"fmt"
"github.com/karask/go-avltree"
)
func main() {
tree := new(avltree.AVLTree)
keys := []int{3,2,4,1,5}
for _, key := range keys {
tree.Add(key, key*key)
}
tree.Remove(2)
tree.Update(5, 6, 6*6)
tree.DisplayInOrder()
val := tree.Search(3).Value
}
Notes
This code has not been thoroughly tested and is not production-ready; only basic error handling, no testing coverage, no profiling or code analysis.
Documentation
¶
Index ¶
- type AVLNode
- type AVLTree
- func (t *AVLTree[TKey, TValue]) Add(key TKey, value TValue)
- func (t *AVLTree[TKey, TValue]) AddOrUpdate(key TKey, value TValue, upd func(oldValue TValue) (TValue, error)) error
- func (t *AVLTree[TKey, TValue]) DisplayInOrder()
- func (t *AVLTree[TKey, TValue]) Erase() error
- func (t *AVLTree[TKey, TValue]) Remove(key TKey)
- func (t *AVLTree[TKey, TValue]) Search(key TKey) (node *AVLNode[TKey, TValue])
- func (t *AVLTree[TKey, TValue]) SetPool(pool *mempool.Pool[*AVLNode[TKey, TValue]])
- func (t *AVLTree[TKey, TValue]) Update(oldKey TKey, newKey TKey, newValue TValue)
- func (t *AVLTree[TKey, TValue]) VisitInOrder(visit func(node *AVLNode[TKey, TValue]) error) error
- type AVLTreeOption
- type Comparable
- type UnrestrictedAVLNode
- type UnrestrictedAVLTree
- func (t *UnrestrictedAVLTree[TKey, TValue]) Add(key TKey, value TValue)
- func (t *UnrestrictedAVLTree[TKey, TValue]) AddOrUpdate(key TKey, value TValue, upd func(oldValue TValue) (TValue, error)) error
- func (t *UnrestrictedAVLTree[TKey, TValue]) DisplayInOrder()
- func (t *UnrestrictedAVLTree[TKey, TValue]) Erase() error
- func (t *UnrestrictedAVLTree[TKey, TValue]) Remove(key TKey)
- func (t *UnrestrictedAVLTree[TKey, TValue]) Search(key TKey) (node *UnrestrictedAVLNode[TKey, TValue])
- func (t *UnrestrictedAVLTree[TKey, TValue]) SetPool(pool *mempool.Pool[*UnrestrictedAVLNode[TKey, TValue]])
- func (t *UnrestrictedAVLTree[TKey, TValue]) Update(oldKey TKey, newKey TKey, newValue TValue)
- func (t *UnrestrictedAVLTree[TKey, TValue]) VisitInOrder(visit func(node *UnrestrictedAVLNode[TKey, TValue]) error) error
- type UnrestrictedAVLTreeOption
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type AVLNode ¶
type AVLNode[TKey constraints.Ordered, TValue any] struct { Value TValue // contains filtered or unexported fields }
AVLNode structure
type AVLTree ¶
type AVLTree[TKey constraints.Ordered, TValue any] struct { // contains filtered or unexported fields }
AVLTree[TKey constraints.Ordered, TValue any] structure. Public methods are Add, Remove, Update, Search, DisplayTreeInOrder.
func NewAVLTree ¶
func NewAVLTree[ TKey constraints.Ordered, TValue any, ]( options ...AVLTreeOption[TKey, TValue], ) ( *AVLTree[TKey, TValue], error, )
NewAVLTree creates a new AVL tree with the specified options.
func (*AVLTree[TKey, TValue]) AddOrUpdate ¶
func (*AVLTree[TKey, TValue]) DisplayInOrder ¶
func (t *AVLTree[TKey, TValue]) DisplayInOrder()
type AVLTreeOption ¶
type AVLTreeOption[ TKey constraints.Ordered, TValue any, ] func(tree *AVLTree[TKey, TValue]) error
func AVLTreeOptionWithMemoryPool ¶
func AVLTreeOptionWithMemoryPool[ TKey constraints.Ordered, TValue any, ]( pool *mempool.Pool[*AVLNode[TKey, TValue]], ) AVLTreeOption[TKey, TValue]
type Comparable ¶
type Comparable interface {
Less(Comparable) bool
Greater(Comparable) bool
Equal(Comparable) bool
}
type UnrestrictedAVLNode ¶
type UnrestrictedAVLNode[TKey Comparable, TValue any] struct { Value TValue // contains filtered or unexported fields }
AVLNode structure
func (*UnrestrictedAVLNode[TKey, TValue]) Erase ¶
func (node *UnrestrictedAVLNode[TKey, TValue]) Erase() error
Erase nullifies all the fields of the AVL tree node.
func (*UnrestrictedAVLNode[TKey, TValue]) Key ¶
func (node *UnrestrictedAVLNode[TKey, TValue]) Key() TKey
Key returns the key of the AVL tree node.
type UnrestrictedAVLTree ¶
type UnrestrictedAVLTree[TKey Comparable, TValue any] struct { // contains filtered or unexported fields }
AVLTree[TKey constraints.Ordered, TValue any] structure. Public methods are Add, Remove, Update, Search, DisplayTreeInOrder.
func NewUnrestrictedAVLTree ¶
func NewUnrestrictedAVLTree[ TKey Comparable, TValue any, ]( options ...UnrestrictedAVLTreeOption[TKey, TValue], ) ( *UnrestrictedAVLTree[TKey, TValue], error, )
NewAVLTree creates a new AVL tree with the specified options.
func (*UnrestrictedAVLTree[TKey, TValue]) Add ¶
func (t *UnrestrictedAVLTree[TKey, TValue]) Add(key TKey, value TValue)
func (*UnrestrictedAVLTree[TKey, TValue]) AddOrUpdate ¶
func (t *UnrestrictedAVLTree[TKey, TValue]) AddOrUpdate( key TKey, value TValue, upd func(oldValue TValue) (TValue, error), ) error
func (*UnrestrictedAVLTree[TKey, TValue]) DisplayInOrder ¶
func (t *UnrestrictedAVLTree[TKey, TValue]) DisplayInOrder()
func (*UnrestrictedAVLTree[TKey, TValue]) Erase ¶
func (t *UnrestrictedAVLTree[TKey, TValue]) Erase() error
func (*UnrestrictedAVLTree[TKey, TValue]) Remove ¶
func (t *UnrestrictedAVLTree[TKey, TValue]) Remove(key TKey)
func (*UnrestrictedAVLTree[TKey, TValue]) Search ¶
func (t *UnrestrictedAVLTree[TKey, TValue]) Search(key TKey) (node *UnrestrictedAVLNode[TKey, TValue])
func (*UnrestrictedAVLTree[TKey, TValue]) SetPool ¶
func (t *UnrestrictedAVLTree[TKey, TValue]) SetPool(pool *mempool.Pool[*UnrestrictedAVLNode[TKey, TValue]])
func (*UnrestrictedAVLTree[TKey, TValue]) Update ¶
func (t *UnrestrictedAVLTree[TKey, TValue]) Update(oldKey TKey, newKey TKey, newValue TValue)
func (*UnrestrictedAVLTree[TKey, TValue]) VisitInOrder ¶
func (t *UnrestrictedAVLTree[TKey, TValue]) VisitInOrder(visit func(node *UnrestrictedAVLNode[TKey, TValue]) error) error
type UnrestrictedAVLTreeOption ¶
type UnrestrictedAVLTreeOption[ TKey Comparable, TValue any, ] func(tree *UnrestrictedAVLTree[TKey, TValue]) error
func UnrestrictedAVLTreeOptionWithMemoryPool ¶
func UnrestrictedAVLTreeOptionWithMemoryPool[ TKey Comparable, TValue any, ]( pool *mempool.Pool[*UnrestrictedAVLNode[TKey, TValue]], ) UnrestrictedAVLTreeOption[TKey, TValue]
Source Files
Directories
Click to show internal directories.
Click to hide internal directories.