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
- type Node
- type 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 ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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 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 ¶
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 ¶
Get returns the Node currently pointed to by the iterator. It is safe to remove the Node returned from the Tree.
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 (*Tree) Find ¶
Find finds the value in the Tree, and returns the Node or nil iff the value is not present.
func (*Tree) First ¶
First returns the first node in the Tree (in-order) or nil iff the Tree is empty.
func (*Tree) ForEach ¶
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 ¶
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 ¶
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 ¶
Last returns the last element in the Tree (in-order) or nil iff the Tree is empty.
Source Files