README
¶
AVL - AVL tree
forked from 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. Replace cmpFunc with Itemer interface, slower about 15% than cmpFunc
Features:
- Size
- Insertion
- Deletion
- Search
- In-order traversal (forward only) with an iterator or callback.
- Non-recursive.
Note:
- The package itself is free from external dependencies, the unit tests use [testify][3].
Documentation
¶
Overview ¶
Package avl implements an AVL tree.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
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.
type Node ¶
type Node struct {
// Value is the value stored by the Node.
Value Itemer
// 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.
Source Files