avltree

README

avltree

This is AVL Tree implementations.

Installation

$ go get github.com/OlexiyKhokhlov/avltree

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

Order 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) Contains(key interface{}) bool
  • func (t *AVLTree) Empty() bool
  • 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

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) Contains

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

func (*AVLTree) Empty

func (t *AVLTree) Empty() bool

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