avltree

README

AVL Tree Go's module

Installation

$ go get github.com/OlexiyKhokhlov/avltree

Motivation

Go's standard library is still lean. Unlike other programming languages it hasn't got a container that holds a pair key-value in the determined order. This module tries to fix it!

Internal details

Ordered containsers usually based on RB-Tree. But it uses AVL Tree. There are a several reasons for that:

• AVL-Tree always provides more balanced tree.
• RB-Tree balancer is really lame in the inserting of ordered sequences.
• RB-Tree is more popular so I don't want to implement one more of that.

This implementation has the next features:

• Every tree node contains only two pointers. It helps to reduce memory usage but it blocks possibility to implement iterators. So iterators isn't present but you can use enumerator methods instead. I guess it is completely usefull.
• Go doesn't allow ordinary developers to write generics like Go's map or slices. So this implentations uses interface{} type a lot. For you it means - you must cast interface{} to key or value every time when you want to reach your data. Also it reduces a performance since interally I have to cast interfaces in the key processing.
• Go hasn't const qualifier. So there is no flex way to block possibility to change a key inside of the tree. Of course I know about copying. But isn't a good solution. First of all Go hasn't got unified way to copy any type of data. And secondly it provides a bad performance when your key is a big structure. So be carefull, avoid key changing!
• Regarding Go's interface{} again - you can insert a different types for values data. I don't recomend to do it but it will works correctly in any time. Just keep in the mind - correct casting to the value type back is completely on you! Also you can the tree like a set without values. In the such case you can use nil for every value.
• Inserting and Erasing methods are non-recursive. So it helps to reduse stack memory usage. And also it is cool!

Tutorial

Creating a container

First of all you should implement a Comparator. This is a function that gets two keys via their interface{} and returns an int value that means:

• 0 if both arguments are equivalent
• -1 if the first argument is lesser then second
• 1 if the first argument is greater then second

Example #1 Where key type is int:

func IntComparator func(a interface{}, b interface{}) int  {
	first := a.(int) //cast to key type here
	second := b.(int) //and here

	if first == second {
	    return 0
	}
	if first < second {
	    return -1
	}
	return 1
    }

Example #2 where key type is a custom struct:

type MyKey struct {
    field1 int
    key    uint64 //assume we want to use only this field like a key
    title  string
}

func MyKeyComparator func(a interface{}, b interface{}) int  {
	first := a.(MyKey) //cast to key type here
	second := b.(MyKey) //and here

	if first.key == second.key {
	    return 0
	}
	if first.key < second.key {
	    return -1
	}
	return 1
    }

And Example #3 Where key is a string:

func StringComparator func(a interface{}, b interface{}) int  {
	first := a.(string) //cast to key type here
	second := b.(string) //and here

	return first.Compare(second) //Use Compare method since it doing all needed
    }

And when you got a Comparator you can create a tree instance in a simple way:

package main

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

func StringComparator(a interface{}, b interface{}) int {
	first := a.(string)  //cast to key type here
	second := b.(string) //and here

	return strings.Compare(first, second) //Use Compare method since it doing all needed
}
func main() {
	StringTree := avltree.NewAVLTree(StringComparator)
}
}

Or create a tree where key has int type:

package main

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

func main() {
IntTree :=  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 and Erasing

Well, if you have a tree you want to insert and erase some data.

package main

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

func main() {
	IntTree := 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
	})

	//Insert a value here
	err := IntTree.Insert(10, nil)
	if err != nil {
		fmt.Println(err)
	}

	//Or insert a variable
	v := 20
	err = IntTree.Insert(v, nil)
	if err != nil {
		fmt.Println(err)
	}

	//The same key isn't allowed
	err = IntTree.Insert(20, nil)
	if err != nil {
		fmt.Println(err)
	}

	//Now IntTree contains 10 and 20
	//Lets try to remove 20
	err = IntTree.Erase(20)
	if err != nil {
		fmt.Println(err)
	}

	//Lets try to do the same again
	err = IntTree.Erase(20)
	if err != nil {
		fmt.Println(err)
	}

	//At the end clear all data in the tree
	IntTree.Clear()
}

Element access, checking

package main

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

func main() {
	IntTree := 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
	})

	//Insert some data
	IntTree.Insert(1, "one")
	IntTree.Insert(2, "two")
	IntTree.Insert(3, "three")

	//Check if a tree contains some key
	if IntTree.Contains(1) {
		fmt.Println("IntTree truly contains 10")
	}

	//Find a value that is associated with a key
	value := IntTree.Find(2)
	if value != nil {
		str := value.(string)
		fmt.Println("Value for key 2 is: ", str)
	}
}

Enumerating

TODO

TODO

• It will be interesting to provide some performance testing for this implementation and comparing with other not only Go.
• Implemet a generator that generates a Tree sources by the given types.

Links

Documentation

Overview

Package avltree provides associative container 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

• Constants
• type AVLTree
  • func NewAVLTree(c Comparator) *AVLTree
  • func (t *AVLTree) BSTDump(w io.Writer)
  • func (t *AVLTree) Clear()
  • func (t *AVLTree) Contains(key interface{}) bool
  • func (t *AVLTree) Empty() bool
  • func (t *AVLTree) Enumerate(order EnumerationOrder, f Enumerator)
  • func (t *AVLTree) EnumerateDiapason(left, right interface{}, order EnumerationOrder, f Enumerator) error
  • func (t *AVLTree) Erase(key interface{}) error
  • func (t *AVLTree) Find(key interface{}) interface{}
  • func (t *AVLTree) FindNextElement(key interface{}) (interface{}, interface{})
  • func (t *AVLTree) FindPrevElement(key interface{}) (interface{}, interface{})
  • func (t *AVLTree) First() (interface{}, interface{})
  • func (t *AVLTree) Insert(key interface{}, value interface{}) error
  • func (t *AVLTree) Last() (interface{}, interface{})
  • func (t *AVLTree) Size() uint
• type Comparator
• type EnumerationOrder
• type Enumerator

Constants

const (
	//ASCENDING is an id for Enumerate and EnumerateDiapason methods
	ASCENDING = 0
	//DESCENDING is an id for Enumerate and EnumerateDiapason methods
	DESCENDING = 1
)

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

NewAVLTree creates a new AVLTree instance with the given Comparator

func (*AVLTree) BSTDump

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

BSTDump writes a Tree in graphviz digraph textual format See here https://graphviz.org/ for the details

func (*AVLTree) Clear

func (t *AVLTree) Clear()

Clear clears and removes all tree content

func (*AVLTree) Contains

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

Contains checks if the container contains element with the specific key

func (*AVLTree) Empty

func (t *AVLTree) Empty() bool

Empty checks whether the container is empty

func (*AVLTree) Enumerate

func (t *AVLTree) Enumerate(order EnumerationOrder, f Enumerator)

Enumerate calls 'Enumerator' for every Tree's element. Enumeration order can be one from ASCENDING or DESCENDING Enumerator should return `false` for stop enumerating or `true` for continue

func (*AVLTree) EnumerateDiapason

func (t *AVLTree) EnumerateDiapason(left, right interface{}, order EnumerationOrder, f Enumerator) error

EnumerateDiapason works like Enumerate but has two additional args - left and right These are left and right borders for enumeration. Enumeration includes left and right borders. Note: left must be always lesser than right. Otherwise returns error Note: left and right should be nil. In means the lesser/greater key in the tree is a border.

So call EnumerateDiapason where both borders are nil is equivalent to call Enumerate.

Note: If you want to enumerate whole tree call Enumerate since it`s faster!

func (*AVLTree) Erase

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

Erase removes an element by the given key

func (*AVLTree) Find

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

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

func (*AVLTree) FindNextElement

func (t *AVLTree) FindNextElement(key interface{}) (interface{}, interface{})

FindNextElement returns a key and a value with the key that is nearest to the given key and greater then given key. Can return (nil, nil) when no such node in the tree

func (*AVLTree) FindPrevElement

func (t *AVLTree) FindPrevElement(key interface{}) (interface{}, interface{})

FindPrevElement returns a key and a value that is nearest to the given key and lesser then given key. Can return (nil, nil) when no such node in the tree

func (*AVLTree) First

func (t *AVLTree) First() (interface{}, interface{})

First returns key, value interfaces for the first tree node Returns (nil, nil) when a tree is empty

func (*AVLTree) Insert

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

Insert 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) Last

func (t *AVLTree) Last() (interface{}, interface{})

Last returns key, value interfaces for the last tree node Returns (nil, nil) when a tree is empty

func (*AVLTree) Size

func (t *AVLTree) Size() uint

Size returns the number of elements

type Comparator

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

Comparator is a function type that whould be defined for a key type in the tree

type EnumerationOrder

type EnumerationOrder int

EnumerationOrder a type of enumeration for Enumerate, EnumerateDiapason methods There are two acceptable values - ASCENDING and DESCENDING. All other values provides a runtime error. Unfortunately Go doesn't provide any possibiltiy to check wrong values for that in the compile time. So be careful here!

type Enumerator

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

Enumerator is a function type for AVLTree enumeration. See Enumerate and EnumerateDiapason