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

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
}

func NewAVLTree

func NewAVLTree(c Comparator) *AVLTree

func (*AVLTree) BSTDump

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

func (*AVLTree) CheckHeight

func (t *AVLTree) CheckHeight(checker heightChecker)

func (*AVLTree) Clear

func (t *AVLTree) Clear()

func (*AVLTree) Contains

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

func (*AVLTree) Empty

func (t *AVLTree) Empty() bool

func (*AVLTree) EnumerateAsc

func (t *AVLTree) EnumerateAsc(f Enumerator)

func (*AVLTree) EnumerateDesc

func (t *AVLTree) EnumerateDesc(f Enumerator)

func (*AVLTree) Erase

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

func (*AVLTree) Find

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

func (*AVLTree) Insert

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

func (*AVLTree) Size

func (t *AVLTree) Size() uint

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