README
¶
AVL tree for key-value store
This package implements an AVL tree for key-value store.
What is an AVL tree?
An AVL tree is a self-balancing binary search tree.
Features
| Feature | Implemented |
|---|---|
| Insertion | yes |
| Deletion | yes |
| Searching | yes |
| Get inorder successor | yes |
| Get inorder predecessor | yes |
| Inorder traversal | yes |
| Preorder traversal | yes |
| Postorder traversal | yes |
| Balancing | yes (AVL) |
Serialization of the tree will not be implemented since the key and value can be an arbitrary type. It would be better for the caller to implement the serialization that fits the use case the best.
Documentation
¶
Overview ¶
Example ¶
package main
import (
"fmt"
"github.com/somebadcode/avltree"
)
func main() {
tree := avltree.New[int, string](1)
tree.Insert(45, "rabbit")
tree.Insert(10, "sparrow")
tree.Insert(87, "capybara")
tree.Insert(90, "pig")
tree.Insert(89, "dog")
tree.Insert(33, "cat")
tree.Insert(29, "tiger")
tree.Insert(55, "lion")
tree.InorderTraversal(func(k int, s string) bool {
fmt.Println(k, s)
return true
})
fmt.Println("Tree size:", tree.Size())
}
Output: 10 sparrow 29 tiger 33 cat 45 rabbit 55 lion 87 capybara 89 dog 90 pig Tree size: 8
Index ¶
- Constants
- type AVLTree
- func (tree *AVLTree[K, V]) Delete(key K)
- func (tree *AVLTree[K, V]) InorderPredecessor(key K) (K, V, bool)
- func (tree *AVLTree[K, V]) InorderSuccessor(key K) (K, V, bool)
- func (tree *AVLTree[K, V]) InorderTraversal(visitFunc VisitFunc[K, V])
- func (tree *AVLTree[K, V]) Insert(key K, value V)
- func (tree *AVLTree[K, V]) PostorderTraversal(visitFunc VisitFunc[K, V])
- func (tree *AVLTree[K, V]) PreorderTraversal(visitFunc VisitFunc[K, V])
- func (tree *AVLTree[K, V]) RootKey() K
- func (tree *AVLTree[K, V]) Search(key K) (V, bool)
- func (tree *AVLTree[K, V]) Size() uint
- type Node
- type NodeType
- type VisitFunc
Examples ¶
Constants ¶
const DefaultThreshold = 1
DefaultThreshold is optimal for fast searching.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type AVLTree ¶
AVLTree is a self-balancing binary search tree.
func New ¶
New returns an AVL tree. The threshold is used for balancing. Higher value means faster inserts and deletes but slower searches. Recommended value is DefaultThreshold.
func (*AVLTree[K, V]) InorderPredecessor ¶
InorderPredecessor returns the key and value of the inorder predecessor of the specified key.
func (*AVLTree[K, V]) InorderSuccessor ¶
InorderSuccessor returns the key and value of the inorder successor of the specified key.
func (*AVLTree[K, V]) InorderTraversal ¶
InorderTraversal will do an inorder traversal of the whole tree.
func (*AVLTree[K, V]) PostorderTraversal ¶
PostorderTraversal will do a postorder traversal of the whole tree.
func (*AVLTree[K, V]) PreorderTraversal ¶
PreorderTraversal will do a preorder traversal of the whole tree.
Source Files