The highest tagged major version is
README
¶
go-avltree
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
- type CompareFunc
- type Interface
- type IterateFunc
- type ObjectTree
- type Pair
- type PairIterateFunc
- type PairTree
- func (t *PairTree) Add(o Pair) (val *Pair, isDupe bool)
- func (t *PairTree) At(index int) *Pair
- func (t *PairTree) Data() []Pair
- func (t *PairTree) Do(f PairIterateFunc)
- func (t *PairTree) Find(key string) *Pair
- func (t *PairTree) Init(flags byte) *PairTree
- func (t *PairTree) Iter() <-chan Pair
- func (t *PairTree) Print(w io.Writer, f PairIterateFunc, itemSiz int)
- func (t *PairTree) Remove(ptr string) *Pair
- func (t *PairTree) RemoveAt(index int) *Pair
- type StringIterateFunc
- type StringTree
- func (t *StringTree) Add(o string) (val string, isDupe bool)
- func (t *StringTree) At(index int) string
- func (t *StringTree) Data() []string
- func (t *StringTree) Do(f StringIterateFunc)
- func (t *StringTree) Find(key string) string
- func (t *StringTree) Init(flags byte) *StringTree
- func (t *StringTree) Iter() <-chan string
- func (t *StringTree) Print(w io.Writer, f StringIterateFunc, itemSiz int)
- func (t *StringTree) Remove(ptr string) string
- func (t *StringTree) RemoveAt(index int) string
- type Tree
- func (t *Tree) Add(o interface{}) (val interface{}, isDupe bool)
- func (t *Tree) At(index int) interface{}
- func (t *Tree) Cap() int
- func (t *Tree) Clear()
- func (t *Tree) Data() []interface{}
- func (t *Tree) Do(f IterateFunc)
- func (t *Tree) Find(key interface{}) interface{}
- func (t *Tree) Height() int
- func (t *Tree) Init(c CompareFunc, flags byte) *Tree
- func (t *Tree) Iter() <-chan interface{}
- func (t *Tree) Len() int
- func (t *Tree) Print(w io.Writer, f IterateFunc, itemSiz int)
- func (t *Tree) Remove(ptr interface{}) interface{}
- func (t *Tree) RemoveAt(index int) interface{}
Constants ¶
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 PairIterateFunc ¶
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 ¶
NewPairTree returns an initialized PairTree.
func (*PairTree) Add ¶
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) 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 ¶
Find returns the element where the comparison function matches the node's value and the given key value.
func (*PairTree) Print ¶
func (t *PairTree) Print(w io.Writer, f PairIterateFunc, itemSiz int)
Print prints the values in the tree to the writer.
type StringIterateFunc ¶
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 (*Tree) Add ¶
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) Cap ¶
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) 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) 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) Print ¶
func (t *Tree) Print(w io.Writer, f IterateFunc, itemSiz int)
Print prints the values of the Tree to the given writer.
Source Files