avltree

package module
v1.0.3 Latest Latest
Warning

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

 Go to latest Published: Feb 4, 2023 License: MIT Imports: 3 Imported by: 14

README

go-avltree

Go Reference

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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.