Documentation
¶
Index ¶
- type Node
- type Tree
- func (t *Tree[K, V]) Ceiling(key K) (ceiling *Node[K, V], found bool)
- func (tree *Tree[K, V]) Clear()
- func (tree *Tree[K, V]) Empty() bool
- func (t *Tree[K, V]) Floor(key K) (floor *Node[K, V], found bool)
- func (t *Tree[K, V]) Get(key K) (value V, found bool)
- func (t *Tree[K, V]) GetNode(key K) *Node[K, V]
- func (t *Tree[K, V]) Inorder(handler func(key K, value V))
- func (t *Tree[K, V]) Keys() []K
- func (t *Tree[K, V]) Left() *Node[K, V]
- func (tree *Tree[K, V]) Len() int
- func (t *Tree[K, V]) Put(key K, value V)
- func (t *Tree[K, V]) Remove(key K)
- func (t *Tree[K, V]) Right() *Node[K, V]
- func (t *Tree[K, V]) String() string
- 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 Left *Node[K, V] Right *Node[K, V] Parent *Node[K, V] // contains filtered or unexported fields }
Node is a single element within the tree
func (*Node[K, V]) Inorder ¶
func (n *Node[K, V]) Inorder(handler func(key K, value V))
Inorer travels the node as root in-order with a handler. Morris traversal used, the time complex is O(n), n is the total nodes in the tree, and the space complex is O(1)
type Tree ¶
type Tree[K comparable, V any] struct { Root *Node[K, V] Comparator dsgo.Comparator[K] // contains filtered or unexported fields }
Tree holds elements of the red-black tree
func NewWith ¶
func NewWith[K comparable, V any](comparator dsgo.Comparator[K]) *Tree[K, V]
NewWith instantiates a red-black tree with the custom comparator.
func (*Tree[K, V]) Ceiling ¶
Ceiling finds ceiling node of the input key, return the ceiling node or nil if no ceiling is found. Second return parameter is true if ceiling was found, otherwise false.
Ceiling node is defined as the smallest node that is larger than or equal to the given node. A ceiling node may not be found, either because the tree is empty, or because all nodes in the tree are smaller than the given node.
Key should adhere to the comparator's type assertion, otherwise method panics.
func (*Tree[K, V]) Floor ¶
Floor Finds floor node of the input key, return the floor node or nil if no floor is found. Second return parameter is true if floor was found, otherwise false.
Floor node is defined as the largest node that is smaller than or equal to the given node. A floor node may not be found, either because the tree is empty, or because all nodes in the tree are larger than the given node.
Key should adhere to the comparator's type assertion, otherwise method panics.
func (*Tree[K, V]) Get ¶
Get searches the node in the tree by key and returns its value or nil if key is not found in tree. Second return parameter is true if key was found, otherwise false. Key should adhere to the comparator's type assertion, otherwise method panics.
func (*Tree[K, V]) GetNode ¶
GetNode searches the node in the tree by key and returns its node or nil if key is not found in tree. Key should adhere to the comparator's type assertion, otherwise method panics.
func (*Tree[K, V]) Inorder ¶
func (t *Tree[K, V]) Inorder(handler func(key K, value V))
Inorer travels the tree in-order with a handler.
func (*Tree[K, V]) Put ¶
func (t *Tree[K, V]) Put(key K, value V)
Put inserts node into the tree or update the node's value if the key exsited. Key should adhere to the comparator's type assertion, otherwise method panics.
func (*Tree[K, V]) Remove ¶
func (t *Tree[K, V]) Remove(key K)
Remove remove the node from the tree by key. Key should adhere to the comparator's type assertion, otherwise method panics.
Source Files