Documentation
¶
Overview ¶
Package rbtree provides an iterator for traversing the red-black tree.
This file implements a stateful iterator for the Tree type, supporting both forward and reverse iteration over key-value pairs with O(log n) access time.
Package rbtree implements a red-black tree for ordered key-value storage.
It provides a self-balancing binary search tree with O(log n) operations for insertion, deletion, and lookup. Used by TreeSet and TreeMap. Not thread-safe.
Reference: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Package rbtree provides JSON serialization and deserialization for the red-black tree.
This file extends the Tree type with methods to convert to and from JSON format, implementing the container.JSONSerializer and container.JSONDeserializer interfaces.
Index ¶
- Variables
- type Iterator
- func (it *Iterator[K, V]) Begin()
- func (it *Iterator[K, V]) End()
- func (it *Iterator[K, V]) First() bool
- func (it *Iterator[K, V]) Key() K
- func (it *Iterator[K, V]) Last() bool
- func (it *Iterator[K, V]) Next() bool
- func (it *Iterator[K, V]) NextTo(f func(key K, value V) bool) bool
- func (it *Iterator[K, V]) Node() *Node[K, V]
- func (it *Iterator[K, V]) Prev() bool
- func (it *Iterator[K, V]) PrevTo(f func(key K, value V) bool) bool
- func (it *Iterator[K, V]) Value() V
- type Node
- type Tree
- func (t *Tree[K, V]) Ceiling(key K) (*Node[K, V], bool)
- func (t *Tree[K, V]) Clear()
- func (t *Tree[K, V]) Empty() bool
- func (t *Tree[K, V]) Floor(key K) (*Node[K, V], bool)
- func (t *Tree[K, V]) FromJSON(data []byte) error
- func (t *Tree[K, V]) Get(key K) (val V, found bool)
- func (t *Tree[K, V]) GetNode(key K) *Node[K, V]
- func (t *Tree[K, V]) Iterator() *Iterator[K, V]
- func (t *Tree[K, V]) IteratorAt(node *Node[K, V]) *Iterator[K, V]
- func (t *Tree[K, V]) Keys() []K
- func (t *Tree[K, V]) KeysAndValues() ([]K, []V)
- func (t *Tree[K, V]) Left() *Node[K, V]
- func (t *Tree[K, V]) Len() int
- func (t *Tree[K, V]) MarshalJSON() ([]byte, error)
- func (t *Tree[K, V]) Put(key K, val 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]) ToJSON() ([]byte, error)
- func (t *Tree[K, V]) UnmarshalJSON(data []byte) error
- func (t *Tree[K, V]) Values() []V
Constants ¶
This section is empty.
Variables ¶
var ( ErrMarshalJSONFailure = errors.New("failed to marshal tree to JSON") ErrUnmarshalJSONFailure = errors.New("failed to unmarshal JSON into tree") )
Predefined errors for JSON operations.
var (
ErrInvalidIteratorPosition = errors.New("iterator accessed at invalid position")
)
Predefined errors for iterator operations.
var (
ErrInvalidKeyType = errors.New("key type does not match comparator")
)
Predefined errors for tree operations.
Functions ¶
This section is empty.
Types ¶
type Iterator ¶
type Iterator[K comparable, V any] struct { // contains filtered or unexported fields }
Iterator provides forward and reverse traversal over a Tree's key-value pairs.
It maintains a position in the tree, allowing O(log n) navigation between elements. The iterator is read-only and does not modify the underlying tree. Most operations are O(log n) due to tree traversal, except Begin and End which are O(1).
func (*Iterator[K, V]) Begin ¶
func (it *Iterator[K, V]) Begin()
Begin resets the iterator to before the first element.
Use Next() to move to the first element. Time complexity: O(1).
func (*Iterator[K, V]) End ¶
func (it *Iterator[K, V]) End()
End moves the iterator past the last element.
Use Prev() to move to the last element. Time complexity: O(1).
func (*Iterator[K, V]) First ¶
First moves the iterator to the first element.
Returns true if the tree is non-empty, false otherwise. Time complexity: O(log n).
func (*Iterator[K, V]) Key ¶
func (it *Iterator[K, V]) Key() K
Key returns the current element's key.
Panics if the iterator is not at a valid position (begin or end state). Time complexity: O(1).
func (*Iterator[K, V]) Last ¶
Last moves the iterator to the last element.
Returns true if the tree is non-empty, false otherwise. Time complexity: O(log n).
func (*Iterator[K, V]) Next ¶
Next advances the iterator to the next element in in-order traversal.
Returns true if the iterator is at a valid element after moving, false if it reaches the end. Updates the iterator's state. Time complexity: O(log n).
func (*Iterator[K, V]) NextTo ¶
NextTo advances to the next element satisfying the given condition.
Moves forward from the current position until an element matches the predicate or the end is reached. Returns true if a match is found. Time complexity: O(n) in the worst case.
func (*Iterator[K, V]) Node ¶
Node returns the current node.
Returns nil if the iterator is at begin or end. Time complexity: O(1).
func (*Iterator[K, V]) Prev ¶
Prev moves the iterator to the previous element in in-order traversal.
Returns true if the iterator is at a valid element after moving, false if it reaches the beginning. Updates the iterator's state. Time complexity: O(log n).
type Node ¶
type Node[K comparable, V any] struct { Key K // Key for ordering. Value V // Associated value. Left *Node[K, V] // Left child. Right *Node[K, V] // Right child. Parent *Node[K, V] // Parent node. // contains filtered or unexported fields }
Node represents a single element in the red-black tree.
type Tree ¶
type Tree[K comparable, V any] struct { Root *Node[K, V] // Root node of the tree. Comparator util.Comparator[K] // Comparator for ordering keys. // contains filtered or unexported fields }
Tree manages a red-black tree with key-value pairs.
K must be comparable and compatible with the provided comparator. V can be any type.
func New ¶
New creates a new red-black tree with the built-in comparator for ordered types.
K must implement cmp.Ordered (e.g., int, string). Time complexity: O(1).
func NewWith ¶
func NewWith[K comparable, V any](comparator util.Comparator[K]) *Tree[K, V]
NewWith creates a new red-black tree with a custom comparator.
The comparator defines the ordering of keys. Time complexity: O(1).
func (*Tree[K, V]) Ceiling ¶
Ceiling finds the smallest node greater than or equal to the given key.
Returns the node and true if found, nil and false otherwise. Panics if the key type is incompatible with the comparator. Time complexity: O(log n).
func (*Tree[K, V]) Clear ¶
func (t *Tree[K, V]) Clear()
Clear removes all nodes from the tree.
Time complexity: O(1).
func (*Tree[K, V]) Floor ¶
Floor finds the largest node less than or equal to the given key.
Returns the node and true if found, nil and false otherwise. Panics if the key type is incompatible with the comparator. Time complexity: O(log n).
func (*Tree[K, V]) FromJSON ¶
FromJSON populates the tree from a JSON object.
Expects a JSON object (e.g., `{"a":1, "b":2}`). Clears the tree before loading and inserts each key-value pair. Returns an error if the JSON is invalid or unmarshaling fails.
Example:
t := New[string, int]()
err := t.FromJSON([]byte(`{"a":1, "b":2}`)) // Tree contains {a:1, b:2}
Time complexity: O(n log n), where n is the number of key-value pairs in the JSON.
func (*Tree[K, V]) Get ¶
Get retrieves the value associated with the given key.
Returns the value and true if found, zero value and false otherwise. Panics if the key type is incompatible with the comparator. Time complexity: O(log n).
func (*Tree[K, V]) GetNode ¶
GetNode retrieves the node associated with the given key.
Returns the node if found, nil otherwise. Panics if the key type is incompatible with the comparator. Time complexity: O(log n).
func (*Tree[K, V]) Iterator ¶
Iterator creates a new iterator for the tree.
Starts before the first element (begin state). Use Next() to reach the first element or End() followed by Prev() for the last. Time complexity: O(1).
func (*Tree[K, V]) IteratorAt ¶
IteratorAt creates a new iterator starting at a specific node.
Starts in the between state at the given node. Time complexity: O(1).
func (*Tree[K, V]) Keys ¶
func (t *Tree[K, V]) Keys() []K
Keys returns all keys in in-order traversal.
Time complexity: O(n).
func (*Tree[K, V]) KeysAndValues ¶
func (t *Tree[K, V]) KeysAndValues() ([]K, []V)
KeysAndValues returns all keys and values in in-order traversal.
More efficient than calling Keys() and Values() separately as it traverses the tree only once. Time complexity: O(n).
func (*Tree[K, V]) Left ¶
Left returns the leftmost (minimum) node or nil if the tree is empty.
Time complexity: O(log n).
func (*Tree[K, V]) MarshalJSON ¶
MarshalJSON implements json.Marshaler for seamless JSON encoding.
Delegates to ToJSON() for consistency. Returns the JSON byte slice or an error if serialization fails.
Time complexity: O(n), where n is the number of nodes in the tree.
func (*Tree[K, V]) Put ¶
func (t *Tree[K, V]) Put(key K, val V)
Put inserts or updates a key-value pair in the tree.
If the key exists, its value is updated; otherwise, a new node is inserted. Panics if the key type is incompatible with the comparator. Time complexity: O(log n).
func (*Tree[K, V]) Remove ¶
func (t *Tree[K, V]) Remove(key K)
Remove deletes the node with the given key from the tree.
Does nothing if the key is not found. Panics if the key type is incompatible with the comparator. Time complexity: O(log n).
func (*Tree[K, V]) Right ¶
Right returns the rightmost (maximum) node or nil if the tree is empty.
Time complexity: O(log n).
func (*Tree[K, V]) String ¶
String returns a string representation of the tree.
Time complexity: O(n).
func (*Tree[K, V]) ToJSON ¶
ToJSON serializes the tree into a JSON object.
Converts the tree's key-value pairs into a JSON object where keys are the tree's keys and values are their corresponding values. Returns the JSON-encoded byte slice or an error if marshaling fails.
Example:
t := New[string, int]()
t.Put("a", 1)
data, err := t.ToJSON() // Returns []byte(`{"a":1}`), nil
Time complexity: O(n), where n is the number of nodes in the tree.
func (*Tree[K, V]) UnmarshalJSON ¶
UnmarshalJSON implements json.Unmarshaler for seamless JSON decoding.
Delegates to FromJSON() to populate the tree. Returns an error if deserialization fails.
Time complexity: O(n log n), where n is the number of key-value pairs in the JSON.
Source Files