avltree

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 New[K cmp.Ordered, V any](threshold int) *AVLTree[K, V]
  • 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
  • func (node *Node[K, V]) Type() NodeType
• type NodeType
• type VisitFunc

Examples

• Package

Constants

const DefaultThreshold = 1

DefaultThreshold is optimal for fast searching.

Types

type AVLTree

type AVLTree[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

AVLTree is a self-balancing binary search tree.

func New

func New[K cmp.Ordered, V any](threshold int) *AVLTree[K, V]

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]) Delete

func (tree *AVLTree[K, V]) Delete(key K)

func (*AVLTree[K, V]) InorderPredecessor

func (tree *AVLTree[K, V]) InorderPredecessor(key K) (K, V, bool)

InorderPredecessor returns the key and value of the inorder predecessor of the specified key.

func (*AVLTree[K, V]) InorderSuccessor

func (tree *AVLTree[K, V]) InorderSuccessor(key K) (K, V, bool)

InorderSuccessor returns the key and value of the inorder successor of the specified key.

func (*AVLTree[K, V]) InorderTraversal

func (tree *AVLTree[K, V]) InorderTraversal(visitFunc VisitFunc[K, V])

InorderTraversal will do an inorder traversal of the whole tree.

func (*AVLTree[K, V]) Insert

func (tree *AVLTree[K, V]) Insert(key K, value V)

func (*AVLTree[K, V]) PostorderTraversal

func (tree *AVLTree[K, V]) PostorderTraversal(visitFunc VisitFunc[K, V])

PostorderTraversal will do a postorder traversal of the whole tree.

func (*AVLTree[K, V]) PreorderTraversal

func (tree *AVLTree[K, V]) PreorderTraversal(visitFunc VisitFunc[K, V])

PreorderTraversal will do a preorder traversal of the whole tree.

func (*AVLTree[K, V]) RootKey

func (tree *AVLTree[K, V]) RootKey() K

RootKey returns the key of the root node.

func (*AVLTree[K, V]) Search

func (tree *AVLTree[K, V]) Search(key K) (V, bool)

func (*AVLTree[K, V]) Size

func (tree *AVLTree[K, V]) Size() uint

Size returns the amounts of nodes in the tree.

type Node

type Node[K cmp.Ordered, V any] struct {
	Key    K           `json:"k,omitempty"`
	Value  V           `json:"v,omitempty"`
	Left   *Node[K, V] `json:"l,omitempty"`
	Right  *Node[K, V] `json:"r,omitempty"`
	Height int         `json:"h,omitempty"`
}

func (*Node[K, V]) Type

func (node *Node[K, V]) Type() NodeType

type NodeType

type NodeType uint8

const (
	TypeLeaf NodeType = iota
	TypeSingleChild
	TypeFull
)

type VisitFunc

type VisitFunc[K cmp.Ordered, V any] func(K, V) bool

VisitFunc is used when traversing the tree. The function will be called with the key and value. The traversal can be stopped by returning false.