avl

README

AVL - AVL tree

Yawning Angel (yawning at schwanenlied dot me)

A generic Go AVL tree implementation, derived from Eric Biggers' C code, in the spirt of the runtime library's containers.

Features:

• Size
• Insertion
• Deletion
• Search
• In-order traversal (forward and backward) with an iterator or callback.
• Non-recursive.

Note:

• The package itself is free from external dependencies, the unit tests use testify.

Documentation

Overview

Package avl implements an AVL tree.

Example

// example_test.go - AVL tree example.
//
// To the extent possible under law, Yawning Angel has waived all copyright
// and related or neighboring rights to avl, using the Creative
// Commons "CC0" public domain dedication. See LICENSE or
// <http://creativecommons.org/publicdomain/zero/1.0/> for full details.

package main

import "fmt"

func CompareIntegers(a, b interface{}) int {
	// Returns < 0, 0, > 1 if a < b, a == b, a > b respectively.
	return a.(int) - b.(int)
}

func main() {
	// Create a new tree that will store integers.
	tree := New(CompareIntegers)

	// Insert a handful of integers in random order.
	s := []int{5, 2, 6, 3, 1, 4}
	for _, i := range s {
		tree.Insert(i)
	}

	// Traverse the tree forward in-order.
	forwardInOrder := make([]int, 0, len(s))
	tree.ForEach(Forward, func(node *Node) bool {
		forwardInOrder = append(forwardInOrder, node.Value.(int))
		return true
	})

	fmt.Println(forwardInOrder)

	// Traverse the tree backward using an interator.
	backwardInOrder := make([]int, 0, len(s))
	iter := tree.Iterator(Backward)
	for node := iter.First(); node != nil; node = iter.Next() {
		backwardInOrder = append(backwardInOrder, node.Value.(int))

		// It is safe to remove the current node while iterating.
		tree.Remove(node)
	}

	fmt.Println(backwardInOrder)

	// The tree is empty after the Remove() calls.
	fmt.Println(tree.Len())

}

Output:

[1 2 3 4 5 6]
[6 5 4 3 2 1]
0

Index

• type CompareFunc
• type Direction
• type Iterator
  • func (it *Iterator) First() *Node
  • func (it *Iterator) Get() *Node
  • func (it *Iterator) Next() *Node
• type Node
• type Tree
  • func New(cmpFn CompareFunc) *Tree
  • func (t *Tree) Find(v interface{}) *Node
  • func (t *Tree) First() *Node
  • func (t *Tree) ForEach(direction Direction, fn func(*Node) bool)
  • func (t *Tree) Insert(v interface{}) *Node
  • func (t *Tree) Iterator(direction Direction) *Iterator
  • func (t *Tree) Last() *Node
  • func (t *Tree) Len() int
  • func (t *Tree) Remove(node *Node)

Examples

• Package

Types

type CompareFunc

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

CompareFunc is the function used to compare entries in the Tree to maintain ordering. It MUST return < 0, 0, or > 0 if a is less than, equal to, or greater than b respectively.

Note: All calls made to the comparison function will pass the user supplied value as a, and the in-Tree value as b.

type Direction

type Direction int8

Direction is the direction associated with an iterator.

const (
	// Backward is backward in-order.
	Backward Direction = -1

	// Forward is forward in-order.
	Forward Direction = 1
)

type Iterator

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

Iterator is a Tree iterator. Modifying the Tree while iterating is unsupported except for removing the current Node.

func (*Iterator) First

func (it *Iterator) First() *Node

First moves the iterator to the first Node in the Tree and returns the first Node or nil iff the Tree is empty. Note that "first" in this context is dependent on the direction specified when constructing the iterator.

func (*Iterator) Get

func (it *Iterator) Get() *Node

Get returns the Node currently pointed to by the iterator. It is safe to remove the Node returned from the Tree.

func (*Iterator) Next

func (it *Iterator) Next() *Node

Next advances the iterator and returns the Node or nil iff the end of the Tree has been reached.

type Node

type Node struct {
	// Value is the value stored by the Node.
	Value interface{}
	// contains filtered or unexported fields
}

Node is a node of a Tree.

type Tree

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

Tree represents an AVL tree.

func New

func New(cmpFn CompareFunc) *Tree

New returns an initialized Tree.

func (*Tree) Find

func (t *Tree) Find(v interface{}) *Node

Find finds the value in the Tree, and returns the Node or nil iff the value is not present.

func (*Tree) First

func (t *Tree) First() *Node

First returns the first node in the Tree (in-order) or nil iff the Tree is empty.

func (*Tree) ForEach

func (t *Tree) ForEach(direction Direction, fn func(*Node) bool)

ForEach executes a function for each Node in the tree, visiting the nodes in-order in the direction specified. If the provided function returns false, the iteration is stopped. Modifying the Tree from within the function is unsupprted except for removing the current Node.

func (*Tree) Insert

func (t *Tree) Insert(v interface{}) *Node

Insert inserts the value into the Tree, and returns the newly created Node or the existing Node iff the value is already present in the tree.

func (*Tree) Iterator

func (t *Tree) Iterator(direction Direction) *Iterator

Iterator returns an iterator that traverses the tree (in-order) in the specified direction. Modifying the Tree while iterating is unsupported except for removing the current Node.

func (*Tree) Last

func (t *Tree) Last() *Node

Last returns the last element in the Tree (in-order) or nil iff the Tree is empty.

func (*Tree) Len

func (t *Tree) Len() int

Len returns the number of elements in the Tree.

func (*Tree) Remove

func (t *Tree) Remove(node *Node)

Remove removes the Node from the Tree.