avltree

package module
Version: v1.0.2 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jul 7, 2020 License: MIT Imports: 3 Imported by: 12

README

Build Status Coverage Status GoDoc gocover

An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at most one and in which the left and right subtrees are again AVL trees.

With each node of an AVL tree is associated a balance factor that is Left High, Equal, or Right High according, respectively, as the left subtree has height greater than, equal to, or less than that of the right subtree.

The AVL tree is, in practice, balanced quite well. It can (at the worst case) become skewed to the left or right, but never so much that it becomes inefficient. The balancing is done as items are added or deleted.

This version is enhanced to allow "indexing" of values in the tree; however, the indexes are not stable as the tree could be resorted as items are added or removed.

It is safe to iterate or search a tree from multiple threads provided that no threads are modifying the tree.

The tree works on interface{} types and there is also a specialization for strings, pairs, and objects. Additionally, the tree supports iteration and a channel iterator.

t.Do(func(z interface{}) { if z.(int) % 3333 == 0 { fmt.Printf("%d ", z); } })

for v := range t.Iter() {
        if v.(int) % 3333 == 0 {
                fmt.Printf("%d ", v);
        }
}

To install, you can use:

go get github.com/ancientlore/go-avltree

See some sample code at https://gist.github.com/ancientlore/8855122

Documentation

Overview

Package avltree implements a height-balanced binary tree with array-like indexing capability.

An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at most one and in which the left and right subtrees are again AVL trees.

With each node of an AVL tree is associated a balance factor that is Left High, Equal, or Right High according, respectively, as the left subtree has height greater than, equal to, or less than that of the right subtree.

The AVL tree is, in practice, balanced quite well. It can (at the worst case) become skewed to the left or right, but never so much that it becomes inefficient. The balancing is done as items are added or deleted.

This version is enhanced to allow "indexing" of values in the tree; however, the indexes are not stable as the tree could be resorted as items are added or removed.

It is safe to iterate or search a tree from multiple threads provided that no threads are modifying the tree.

See also: Robert L. Kruse, Data Structures and Program Design, 2nd Ed., Prentice-Hall

Index

Constants

View Source
const (
	AllowDuplicates = 1
)

tree options

Variables

This section is empty.

Functions

This section is empty.

Types

type CompareFunc

type CompareFunc func(v1 interface{}, v2 interface{}) int

CompareFunc defines the function type used to compare values.

type Interface

type Interface interface {
	// Return -1 if this < b, 0 if this == b, and 1 if this > b
	Compare(b Interface) int
}

Interface should be implemented so that your object can be sorted in the tree.

type IterateFunc

type IterateFunc func(v interface{}) bool

IterateFunc defines the function type used for iterating a tree.

type ObjectTree

type ObjectTree struct {
	Tree
}

ObjectTree is a specialization of Tree that hides the wrapping of Elements around objects. The object just needs to implement Interface.

func NewObjectTree

func NewObjectTree(flags byte) *ObjectTree

NewObjectTree returns an initialized ObjectTree.

func (*ObjectTree) Add

func (t *ObjectTree) Add(o Interface) (val interface{}, isDupe bool)

Add adds an item to the tree, returning a pair indicating the added (or duplicate) item, and a flag indicating whether the item is the duplicate that was found. A duplicate will never be returned if the tree's AllowDuplicates flag is set.

func (*ObjectTree) Find

func (t *ObjectTree) Find(key Interface) interface{}

Find returns the element where the comparison function matches the node's value and the given key value

func (*ObjectTree) Init

func (t *ObjectTree) Init(flags byte) *ObjectTree

Init will initialize or reset an ObjectTree.

func (*ObjectTree) Remove

func (t *ObjectTree) Remove(ptr Interface) interface{}

Remove removes the element matching the given value.

type Pair

type Pair struct {
	Key   string
	Value interface{}
}

Pair combines a key and value.

func (Pair) Compare

func (a Pair) Compare(b Interface) int

Compare is the compare function for Pairs, based on Key.

type PairIterateFunc

type PairIterateFunc func(v Pair) bool

PairIterateFunc is the type of function used for iterating across Pairs.

type PairTree

type PairTree struct {
	ObjectTree
}

PairTree is a specialization of Tree that hides the wrapping of Elements around Pair structures.

func NewPairTree

func NewPairTree(flags byte) *PairTree

NewPairTree returns an initialized PairTree.

func (*PairTree) Add

func (t *PairTree) Add(o Pair) (val *Pair, isDupe bool)

Add adds an item to the tree, returning a pair indicating the added (or duplicate) item, and a flag indicating whether the item is the duplicate that was found. A duplicate will never be returned if the tree's AllowDuplicates flag is set.

func (*PairTree) At

func (t *PairTree) At(index int) *Pair

At returns the value at the given index.

func (*PairTree) Data

func (t *PairTree) Data() []Pair

Data returns all the elements as a slice.

func (*PairTree) Do

func (t *PairTree) Do(f PairIterateFunc)

Do calls function f for each element of the tree, in order. The function should not change the structure of the tree underfoot.

func (*PairTree) Find

func (t *PairTree) Find(key string) *Pair

Find returns the element where the comparison function matches the node's value and the given key value.

func (*PairTree) Init

func (t *PairTree) Init(flags byte) *PairTree

Init will initialize or reset a PairTree.

func (*PairTree) Iter

func (t *PairTree) Iter() <-chan Pair

Iter returns a channel you can read through to fetch all the items.

func (*PairTree) Print

func (t *PairTree) Print(w io.Writer, f PairIterateFunc, itemSiz int)

Print prints the values in the tree to the writer.

func (*PairTree) Remove

func (t *PairTree) Remove(ptr string) *Pair

Remove removes the element matching the given value.

func (*PairTree) RemoveAt

func (t *PairTree) RemoveAt(index int) *Pair

RemoveAt removes the element at the given index.

type StringIterateFunc

type StringIterateFunc func(v string) bool

StringIterateFunc defines the function type used when iterating a StringTree.

type StringTree

type StringTree struct {
	Tree
}

StringTree is a specialization of Tree that hides the wrapping of Elements around strings.

func NewStringTree

func NewStringTree(flags byte) *StringTree

NewStringTree returns an initialized StringTree.

func (*StringTree) Add

func (t *StringTree) Add(o string) (val string, isDupe bool)

Add adds an item to the tree, returning a pair indicating the added (or duplicate) item, and a flag indicating whether the item is the duplicate that was found. A duplicate will never be returned if the tree's AllowDuplicates flag is set.

func (*StringTree) At

func (t *StringTree) At(index int) string

At returns the value at the given index.

func (*StringTree) Data

func (t *StringTree) Data() []string

Data returns all the elements as a slice.

func (*StringTree) Do

func (t *StringTree) Do(f StringIterateFunc)

Do calls function f for each element of the tree, in order. The function should not change the structure of the tree underfoot.

func (*StringTree) Find

func (t *StringTree) Find(key string) string

Find returns the element where the comparison function matches the node's value and the given key value.

func (*StringTree) Init

func (t *StringTree) Init(flags byte) *StringTree

Init will initialize or reset a StringTree.

func (*StringTree) Iter

func (t *StringTree) Iter() <-chan string

Iter returns a channel you can read through to fetch all the items.

func (*StringTree) Print

func (t *StringTree) Print(w io.Writer, f StringIterateFunc, itemSiz int)

Print prints the values of the StringTree to the given writer.

func (*StringTree) Remove

func (t *StringTree) Remove(ptr string) string

Remove removes the element matching the given value.

func (*StringTree) RemoveAt

func (t *StringTree) RemoveAt(index int) string

RemoveAt removes the element at the given index.

type Tree

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

Tree stores data about the binary tree.

func New

func New(c CompareFunc, flags byte) *Tree

New returns an initialized tree.

func (*Tree) Add

func (t *Tree) Add(o interface{}) (val interface{}, isDupe bool)

Add adds an item to the tree, returning a pair indicating the added (or duplicate) item, and a flag indicating whether the item is the duplicate that was found. A duplicate will never be returned if the tree's AllowDuplicates flag is set.

func (*Tree) At

func (t *Tree) At(index int) interface{}

At returns the value at the given index.

func (*Tree) Cap

func (t *Tree) Cap() int

Cap returns the capacity of the tree; that is, the maximum elements the tree can hold with at the current height. This is only useful as a measure of how skewed the tree is.

func (*Tree) Clear

func (t *Tree) Clear()

Clear removes all elements from the tree, keeping the current options and compare function.

func (*Tree) Data

func (t *Tree) Data() []interface{}

Data returns all the elements as a slice.

func (*Tree) Do

func (t *Tree) Do(f IterateFunc)

Do calls function f for each element of the tree, in order. The function should not change the structure of the tree underfoot.

func (*Tree) Find

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

Find returns the element where the comparison function matches the node's value and the given key value.

func (*Tree) Height

func (t *Tree) Height() int

Height returns the "height" of the tree, meaning the number of levels.

func (*Tree) Init

func (t *Tree) Init(c CompareFunc, flags byte) *Tree

Init initializes or resets a Tree.

func (*Tree) Iter

func (t *Tree) Iter() <-chan interface{}

Iter returns a channel you can read through to fetch all the items.

func (*Tree) Len

func (t *Tree) Len() int

Len returns the number of elements in the tree.

func (*Tree) Print

func (t *Tree) Print(w io.Writer, f IterateFunc, itemSiz int)

Print prints the values of the Tree to the given writer.

func (*Tree) Remove

func (t *Tree) Remove(ptr interface{}) interface{}

Remove removes the element matching the given value.

func (*Tree) RemoveAt

func (t *Tree) RemoveAt(index int) interface{}

RemoveAt removes the element at the given index.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL