Documentation
¶
Index ¶
- Constants
- 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]) BlackCount() int
- 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) (V, bool)
- func (t *Tree[K, V]) Floor(key K) (K, V, bool)
- func (t *Tree[K, V]) Get(key K) (value V, found bool)
- func (t *Tree[K, V]) InOrder(fn func(K, V) bool)
- func (t *Tree[K, V]) IsEmpty() bool
- func (t *Tree[K, V]) Keys() []K
- func (t *Tree[K, V]) LeafCount() int
- func (t *Tree[K, V]) LevelOrder(fn func(K, V) bool)
- func (t *Tree[K, V]) MarshalJSON() ([]byte, error)
- func (t *Tree[K, V]) Max() (K, V, bool)
- func (t *Tree[K, V]) MaxDepth() int
- func (t *Tree[K, V]) Min() (K, V, bool)
- func (t *Tree[K, V]) MinDepth() int
- func (t *Tree[K, V]) PostOrder(fn func(K, V) bool)
- func (t *Tree[K, V]) PreOrder(fn func(K, V) bool)
- func (t *Tree[K, V]) Put(key K, val V)
- func (t *Tree[K, V]) RedCount() int
- 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 ¶
const ( Reset = "\033[0m" RedTxt = "\033[31m" BlkTxt = "\033[30m" RedBg = "\033[41;37m" BlackBg = "\033[40;37m" )
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 represents a node in red-black tree.
type Option ¶
type Option[K comparable, V any] func(t *Tree[K, V]) error
Option is a functional option type for configuring a red-black tree.
func WithColorfulString ¶
func WithColorfulString[K comparable, V any]() Option[K, V]
WithColorfulString creates a option that make the red-black tree colorful output.
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 red-black tree safe for concurrent use.
type Tree ¶
type Tree[K comparable, V any] struct { // contains filtered or unexported fields }
Tree represents a generic red-black 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 red-black 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 red-black tree from a given map. The provided function "cmp" is determines the order of the keys.
func NewFromOrderedMap ¶
NewFromOrderedMap creates and returns a red-black 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 red-black tree from a given slice. It use the cmp.Compare[K] as the default comparsion function.
func NewOrderedKeys ¶
NewOrderedKeys creates and returns a red-black 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]) BlackCount ¶
func (*Tree[K, V]) Ceiling ¶
Ceiling returns the smallest node with a key greater than or equal to the given key. If such a node exists, it is returned along with true; otherwise, nil and false are returned.
func (*Tree[K, V]) Floor ¶
Floor returns the largest node with a key less than or equal to the given key. If such a node exists, it is returned along with true; otherwise, nil and false are returned.
func (*Tree[K, V]) InOrder ¶
InOrder call function "fn" on each node in inorder traversal order. The traversal 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 node in the tree. If the tree is empty, it returns the nil.
func (*Tree[K, V]) Min ¶
Min returns the minimum node in the tree. If the tree is empty, it returns the nil.
func (*Tree[K, V]) PostOrder ¶
PostOrder call function "fn" on each node in postorder traversal order. The traversal 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 inserts a key-value pair into the tree. if the key already exists, its value will be updated.
func (*Tree[K, V]) String ¶
String returns a visual representation of the Red-Black Tree. If t.color is true, nodes will be displayed in terminal colors.
func (*Tree[K, V]) UnmarshalJSON ¶
UnmarshalJSON implements the json.Unmarshaler interface.
Source Files