Documentation
¶
Index ¶
- type Node
- type Option
- type Tree
- func New[K comparable, V any](cmp func(K, K) int, ops ...Option[K, V]) (*Tree[K, V], error)
- func NewFromMap[K comparable, V any](m map[K]V, cmp func(K, K) int, ops ...Option[K, V]) (*Tree[K, V], error)
- func NewFromOrderedMap[K cmp.Ordered, V any](m map[K]V, ops ...Option[K, V]) (*Tree[K, V], error)
- func NewFromSlice[V any](slice []V, ops ...Option[int, V]) (*Tree[int, V], error)
- func NewOrderedKeys[K cmp.Ordered, V any](ops ...Option[K, V]) (*Tree[K, V], error)
- func (t *Tree[K, V]) Ceiling(key K) (K, V, bool)
- func (t *Tree[K, V]) Clear()
- func (t *Tree[K, V]) Delete(key K)
- func (t *Tree[K, V]) Floor(key K) (K, V, bool)
- func (t *Tree[K, V]) Get(key K) (v V, found bool)
- func (t *Tree[K, V]) Height() int
- func (t *Tree[K, V]) InOrder(fn func(key K, value V) bool)
- func (t *Tree[K, V]) IsEmpty() bool
- func (t *Tree[K, V]) Keys() []K
- func (t *Tree[K, V]) LevelOrder(fn func(key K, value V) bool)
- func (t *Tree[K, V]) MarshalJSON() ([]byte, error)
- func (t *Tree[K, V]) Max() (K, V, bool)
- func (t *Tree[K, V]) Min() (K, V, bool)
- func (t *Tree[K, V]) PostOrder(fn func(key K, value V) bool)
- func (t *Tree[K, V]) PreOrder(fn func(key K, value V) bool)
- func (t *Tree[K, V]) Put(key K, val V)
- func (t *Tree[K, V]) Size() int
- 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 { Key K Value V Parent *Node[K, V] Children [2]*Node[K, V] // contains filtered or unexported fields }
type Option ¶
type Option[K comparable, V any] func(*Tree[K, V]) error
Option is a functional option type for configuring a AVL tree.
func WithNodeFormatter ¶
func WithNodeFormatter[K comparable, V any](fn func(K, V) string) Option[K, V]
WithNodeFormatter creates a option that sets the node formatter when call tree.String(). Example usage:
tree.WithNodeFormatter(func(k string, v int) string {
return fmt.Sprintf("%s:%d ", k, v)
})
func WithSafe ¶
func WithSafe[K comparable, V any]() Option[K, V]
WithSafe creates a option that make the AVL tree safe for concurrent use.
type Tree ¶
type Tree[K comparable, V any] struct { // contains filtered or unexported fields }
Tree represents a generic AVL tree. It support keys of any comparable type and value of any type. The tree use a custom comparison function to matain order.
func New ¶
New creates and returns a AVL tree. The provided function "cmp" is determines the order of the keys.
func NewFromMap ¶
func NewFromMap[K comparable, V any](m map[K]V, cmp func(K, K) int, ops ...Option[K, V]) (*Tree[K, V], error)
NewFromMap creates and returns a AVL tree from a given map. The provided function "cmp" is determines the order of the keys.
func NewFromOrderedMap ¶
NewFromOrderedMap creates and returns a AVL tree from a given map. It uses cmp.Compare[K] as the default comparison function, which is suitable for types that implement the cmp.Ordered interface, such as int, float64, and string.
func NewFromSlice ¶
NewFromSlice creates and returns a AVL tree from a given slice. It use the cmp.Compare[K] as the default comparsion function.
func NewOrderedKeys ¶
NewOrderedKeys creates and returns a AVL tree. It use the cmp.Compare[K] as the default comparsion function. This is suitable for types that implement the cmp.Ordered interface, such as int, float64 and string
func (*Tree[K, V]) Ceiling ¶
Ceiling returns the smallest key in the tree that is greater than or equal to the given key. If no such key exists, returns zero values and false. If the exact key exists, returns that key-value pair and true.
func (*Tree[K, V]) Delete ¶
func (t *Tree[K, V]) Delete(key K)
Delete delete the node from the tree by key.
func (*Tree[K, V]) Floor ¶
Floor returns the largest key in the tree that is less than or equal to the given key. If no such key exists, returns zero values and false. If the exact key exists, returns that key-value pair and true.
func (*Tree[K, V]) Height ¶
Height returns the height of the tree. The height is the length of the longest path from root to leaf.
func (*Tree[K, V]) InOrder ¶
Inorder call function "fn" on each node in inorder traversal order. The traversal starts from the root and follows: left subtree → node → right subtree
func (*Tree[K, V]) Keys ¶
func (t *Tree[K, V]) Keys() []K
Keys returns a slice containing all keys in sorted order.
func (*Tree[K, V]) LevelOrder ¶
LevelOrder call function "fn" on each node in levelorder traversal order
func (*Tree[K, V]) MarshalJSON ¶
MarshalJSON implements the json.Marshaler interface.
func (*Tree[K, V]) Max ¶
Max returns the maximum key in the tree and its associated value. If the tree is empty, it returns the zero values for K and V, and false. Otherwise returns the key-value pair and true.
func (*Tree[K, V]) Min ¶
Min returns the minimum key in the tree and its associated value. If the tree is empty, it returns the zero values for K and V, and false. Otherwise returns the key-value pair and true.
func (*Tree[K, V]) PostOrder ¶
Postorder call function "fn" on each node in postorder traversal order. The traversal starts from the root and follows: left subtree → right subtree → node
func (*Tree[K, V]) PreOrder ¶
Preorder call function "fn" on each node in preorder traversal order. The traversal starts from the root and follows: node → left subtree → right subtree
func (*Tree[K, V]) Put ¶
func (t *Tree[K, V]) Put(key K, val V)
Put insert a key-pair into the tree. If the key already exists, its value will be updated.
func (*Tree[K, V]) UnmarshalJSON ¶
UnmarshalJSON implements the json.Unmarshaler interface.
Source Files