Documentation
¶
Overview ¶
Package avltree implements an AVL balanced binary tree.
References: - https://en.wikipedia.org/wiki/AVL_tree - https://en.wikipedia.org/wiki/Binary_search_tree
Index ¶
- type Node
- type Tree
- func (t *Tree[K, V]) Ceiling(k K) *Node[K, V]
- func (t *Tree[K, V]) Clear()
- func (t *Tree[K, V]) Floor(k K) *Node[K, V]
- func (t *Tree[K, V]) Get(k K) (value V, ok bool)
- func (t *Tree[K, V]) InOrder() ([]K, []V)
- func (t *Tree[K, V]) Insert(k K, v V)
- func (t *Tree[K, V]) Keys() []K
- func (t *Tree[K, V]) Len() int
- func (t *Tree[K, V]) LevelOrder() ([]K, []V)
- func (t *Tree[K, V]) MarshalJSON() ([]byte, error)
- func (t *Tree[K, V]) Max() *Node[K, V]
- func (t *Tree[K, V]) Min() *Node[K, V]
- func (t *Tree[K, V]) PostOrder() ([]K, []V)
- func (t *Tree[K, V]) PreOrder() ([]K, []V)
- func (t *Tree[K, V]) Range(f func(k K, v V) bool)
- func (t *Tree[K, V]) Remove(k K)
- func (t *Tree[K, V]) Root() *Node[K, V]
- func (t *Tree[K, V]) Search(k K) *Node[K, V]
- func (t *Tree[K, V]) String() string
- func (t *Tree[K, V]) UnmarshalJSON(data []byte) error
- func (t *Tree[K, V]) Values() []V
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node[K comparable, V any] struct { // The value stored with this node. Value V // contains filtered or unexported fields }
Node is a node of a binary tree.
func (*Node[K, V]) Len ¶
Len returns the number of nodes of subtree with node n as the root. The complexity is O(n).
func (*Node[K, V]) Max ¶
Max returns the node which key is the maximum key of subtree with node n as the root.
type Tree ¶
type Tree[K comparable, V any] struct { // contains filtered or unexported fields }
Tree represents an avl tree.
func New ¶
New returns an initialized tree with cmp.Compare as the cmp function.
func NewFunc ¶
func NewFunc[K comparable, V any](cmp container.Compare[K]) *Tree[K, V]
NewFunc returns an initialized tree with the given function cmp as the cmp function.
func (*Tree[K, V]) Ceiling ¶
Ceiling returns the ceiling node of key k, or nil if no such node found.
A ceiling node is defined as the smallest node which key is larger than or equal to the given key k. A ceiling node may not be found, either because the tree is empty, or because all keys in the tree is smaller than the given key k.
func (*Tree[K, V]) Floor ¶
Floor returns the floor node of the given key k, or nil if no such node found.
A floor node is defined as the largest node which key is smaller than or equal to the given key k. A floor node may not be found, either because the tree is empty, or because all keys in the tree is larger than the given key k.
func (*Tree[K, V]) Get ¶
Get returns the value which key equals to the given key k. The ok result indicates whether such value was found in tree.
func (*Tree[K, V]) InOrder ¶
func (t *Tree[K, V]) InOrder() ([]K, []V)
InOrder performs in-order traversal for tree, and returns a pair of slices (keys, values) as the result.
func (*Tree[K, V]) Insert ¶
func (t *Tree[K, V]) Insert(k K, v V)
Insert inserts a new node with the given key-value pair (k, v) to tree, or update the key and value if key k already exists in tree.
func (*Tree[K, V]) Keys ¶
func (t *Tree[K, V]) Keys() []K
Values returns all keys in tree (in in-order traversal order).
func (*Tree[K, V]) LevelOrder ¶
func (t *Tree[K, V]) LevelOrder() ([]K, []V)
LevelOrder performs level-order traversal for tree, and returns a pair of slices (keys, values) as the result.
func (*Tree[K, V]) MarshalJSON ¶
MarshalJSON marshals tree into valid JSON. Ref: std json.Marshaler.
func (*Tree[K, V]) PostOrder ¶
func (t *Tree[K, V]) PostOrder() ([]K, []V)
PostOrder performs post-order traversal for tree, and returns a pair of slices (keys, values) as the result.
func (*Tree[K, V]) PreOrder ¶
func (t *Tree[K, V]) PreOrder() ([]K, []V)
PreOrder performs pre-order traversal for tree, and returns a pair of slices (keys, values) as the result.
func (*Tree[K, V]) Range ¶
Range calls f sequentially for each key-value pair (k, v) present in tree in in-order traversal order. If f returns false, range stops the iteration.
func (*Tree[K, V]) Remove ¶
func (t *Tree[K, V]) Remove(k K)
Remove removes the node which key equals to the given key k from tree.
func (*Tree[K, V]) Search ¶
Search returns the node which key equals to the given key k, or nil if no such node found.
func (*Tree[K, V]) String ¶
String returns the string representation of tree. Ref: std fmt.Stringer.
func (*Tree[K, V]) UnmarshalJSON ¶
UnmarshalJSON unmarshals a JSON description of tree. The input can be assumed to be a valid encoding of a JSON value. UnmarshalJSON must copy the JSON data if it wishes to retain the data after returning. Ref: std json.Unmarshaler.
Source Files