avltree

README

avltree

Go maps are hash based. They have a good performance for the searching but don't provide any possibility to arange keys in the order. Also hash-maps are hungry for the memory usage. AVL tree's aren't so extremely fast in searching but they aren't so hungry for memory usage. Also AVL tree's can provide a possibility to get map contens be ascending or by descending.

Installation

Like any other Go package just call

$ go get github.com/OlexiyKhokhlov/avltree

Notes

Go is very simple language so it has any protection for dummy developer. I can't write a code that blocks any possibility to change a key that is already inserted in AVLTree. You must don't do that! It provides broken AVL balancing!

How to use

package main

import (
    "fmt"
    "github.com/OlexiyKhokhlov/avltree"
)

func main() {
    //Tree creation.
    //You have to pass into NewAVLTree a Key comparator function
    //Example uses int comparator. So Key type is int here
    tree := avltree.NewAVLTree(func(a interface{}, b interface{}) int {
	first := a.(int)
	second := b.(int)

	if first == second {
	    return 0
	}
	if first < second {
	    return -1
	}
	return 1
    })
    
    //Inserting
    tree.Insert(2, "this is value for key 2")
    tree.Insert(22, "this is value for key 22")

    //Tree info
    tree.Empty() //returns false
    tree.Count() //returns 2
    
    //Get values 
    tree.Contains(3) //returns false
    tree.Contains(2) //returns true
    tree.Find(2)     //returns interface{} for string that has been inserted 
    tree.Find(22)    //returns interface{} for string that has been inserted
    tree.Find(33)    //returns nil 

    //Erasing
    tree.Erase(2)
    tree.Erase(22)
}

Implementations details

• Every node has only two pointers
• Insert and Erase methods aren't recursive

TODO

Extend and Improve enumerating methods

Documentation

Overview

AVLTree are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order. In a AVLTree, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key. The types of key and mapped value may differ. Internally, the elements in a AVLTree are always sorted by its key following a specific strict weak ordering criterion indicated by its internal comparison object (of type Comparator). AVLTree containers are generally slower than go map container to access individual elements by their key, but they allow the direct iteration on subsets based on their order.

Index

• type AVLTree
  • func NewAVLTree(c Comparator) *AVLTree
  • func (t *AVLTree) BSTDump(w io.Writer)
  • func (t *AVLTree) CheckHeight(checker heightChecker)
  • func (t *AVLTree) Clear()
  • func (t *AVLTree) Contains(key interface{}) bool
  • func (t *AVLTree) Empty() bool
  • func (t *AVLTree) EnumerateAsc(f Enumerator)
  • func (t *AVLTree) EnumerateDesc(f Enumerator)
  • func (t *AVLTree) Erase(key interface{}) error
  • func (t *AVLTree) Find(key interface{}) interface{}
  • func (t *AVLTree) Insert(key interface{}, value interface{}) error
  • func (t *AVLTree) Size() uint
• type Comparator
• type Enumerator

Types

type AVLTree

type AVLTree struct {
	// contains filtered or unexported fields
}

AVLTree is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function `Comparator`. Search, removal, and insertion operations have logarithmic complexity.

func NewAVLTree

func NewAVLTree(c Comparator) *AVLTree

Creates a new AVLTree instance with the given Comparator

func (*AVLTree) BSTDump

func (t *AVLTree) BSTDump(w io.Writer)

Writes BST Tree for graphviz visualizator See here https://graphviz.org/ for the details

func (*AVLTree) CheckHeight

func (t *AVLTree) CheckHeight(checker heightChecker)

Test stuff. You do need to use it

func (*AVLTree) Clear

func (t *AVLTree) Clear()

clears the contents

func (*AVLTree) Contains

func (t *AVLTree) Contains(key interface{}) bool

Checks if the container contains element with specific key

func (*AVLTree) Empty

func (t *AVLTree) Empty() bool

Checks whether the container is empty

func (*AVLTree) EnumerateAsc

func (t *AVLTree) EnumerateAsc(f Enumerator)

Calls 'Enumerator' for every Tree's element in ascending order

func (*AVLTree) EnumerateDesc

func (t *AVLTree) EnumerateDesc(f Enumerator)

Calls 'Enumerator' for every Tree's element in descending order

func (*AVLTree) Erase

func (t *AVLTree) Erase(key interface{}) error

Removes a element by the given key

func (*AVLTree) Find

func (t *AVLTree) Find(key interface{}) interface{}

Finds element with specific key Returns an interface{} for associtaed with the key value. When key isn't present returns nil

func (*AVLTree) Insert

func (t *AVLTree) Insert(key interface{}, value interface{}) error

Inserts an element with the given key and value. Value can be nil It the given key is already present returns an error

func (*AVLTree) Size

func (t *AVLTree) Size() uint

Returns the number of elements

type Comparator

type Comparator func(a interface{}, b interface{}) int

Function type that whould be defined for a key type in the tree

type Enumerator

type Enumerator func(key interface{}, value interface{}) bool

Function type for AVLTree traversal