Documentation ¶
Overview ¶
AVLTree are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order. In a AVLTree, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key. The types of key and mapped value may differ. Internally, the elements in a AVLTree are always sorted by its key following a specific strict weak ordering criterion indicated by its internal comparison object (of type Comparator). AVLTree containers are generally slower than go map container to access individual elements by their key, but they allow the direct iteration on subsets based on their order.
Index ¶
- Constants
- type AVLTree
- func (t *AVLTree) BSTDump(w io.Writer)
- func (t *AVLTree) Clear()
- func (t *AVLTree) Contains(key interface{}) bool
- func (t *AVLTree) Empty() bool
- func (t *AVLTree) Enumerate(order EnumerationOrder, f Enumerator)
- func (t *AVLTree) EnumerateDiapason(left, right interface{}, order EnumerationOrder, f Enumerator) error
- func (t *AVLTree) Erase(key interface{}) error
- func (t *AVLTree) Find(key interface{}) interface{}
- func (t *AVLTree) FindNextElement(key interface{}) (interface{}, interface{})
- func (t *AVLTree) FindPrevElement(key interface{}) (interface{}, interface{})
- func (t *AVLTree) First() (interface{}, interface{})
- func (t *AVLTree) Insert(key interface{}, value interface{}) error
- func (t *AVLTree) Last() (interface{}, interface{})
- func (t *AVLTree) Size() uint
- type Comparator
- type EnumerationOrder
- type Enumerator
- type Node
Constants ¶
const ( ASCENDING = 0 DESCENDING = 1 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type AVLTree ¶
type AVLTree struct {
// contains filtered or unexported fields
}
AVLTree is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function `Comparator`. Search, removal, and insertion operations have logarithmic complexity.
func NewAVLTree ¶
func NewAVLTree(c Comparator) *AVLTree
Creates a new AVLTree instance with the given Comparator
func (*AVLTree) BSTDump ¶
Writes BST Tree in graphviz digraph textual format See here https://graphviz.org/ for the details
func (*AVLTree) Enumerate ¶ added in v1.0.0
func (t *AVLTree) Enumerate(order EnumerationOrder, f Enumerator)
Calls 'Enumerator' for every Tree's element. Enumeration order can be one from ASCENDING or DESCENDING Enumerator should return `false` for stop enumerating or `true` for continue
func (*AVLTree) EnumerateDiapason ¶ added in v1.0.0
func (t *AVLTree) EnumerateDiapason(left, right interface{}, order EnumerationOrder, f Enumerator) error
Works like Enumerate but has two additional args - left and right These are left and right borders for enumeration. Enumeration includes left and right borders. Note: left must be always lesser than right. Otherwise returns error Note: left and right should be nil. In means the lesser/greater key in the tree is a border.
So call EnumerateDiapason where both borders are nil is equivalent to call Enumerate.
Note: If you want to enumerate whole tree call Enumerate since it`s faster!
func (*AVLTree) Find ¶
func (t *AVLTree) Find(key interface{}) interface{}
Finds element with specific key Returns an interface{} for associated with the key value. When key isn't present returns nil
func (*AVLTree) FindNextElement ¶ added in v1.0.0
func (t *AVLTree) FindNextElement(key interface{}) (interface{}, interface{})
Returns key and value with the key that is nearest to the given key and greater then given key. Can return (nil, nil) when no such node in the tree
func (*AVLTree) FindPrevElement ¶ added in v1.0.0
func (t *AVLTree) FindPrevElement(key interface{}) (interface{}, interface{})
Returns key and value that is nearest to the given key and lesser then given key. Can return (nil, nil) when no such node in the tree
func (*AVLTree) First ¶ added in v1.0.0
func (t *AVLTree) First() (interface{}, interface{})
Returns key, value interfaces for the first tree node Returns (nil, nil) when a tree is empty
func (*AVLTree) Insert ¶
Inserts an element with the given key and value. Value can be nil It the given key is already present returns an error
type Comparator ¶
type Comparator func(a interface{}, b interface{}) int
Function type that whould be defined for a key type in the tree
type EnumerationOrder ¶ added in v1.0.0
type EnumerationOrder int
This a type of enumeration for Enumerate, EnumerateLowerBound, EnumerateUpperBound methods There are two acceptable values - ASCENDING and DESCENDING. All other values provides a runtime error. Unfortunately Go doesn't provide any possibiltiy to check wrong values for that in the compile time. So be carefull here!
type Enumerator ¶ added in v0.0.2
type Enumerator func(key interface{}, value interface{}) bool
Function type for AVLTree traversal