Documentation
¶
Overview ¶
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
Index ¶
- type Color
- type Node
- type Tree
- func (t *Tree[K, V]) Begin() (key K, value V, found bool)
- func (t *Tree[K, V]) Ceiling(key K) (*Node[K, V], bool)
- func (t *Tree[K, V]) Clear()
- func (t *Tree[K, V]) Clone() container.Map[K, V]
- func (t *Tree[K, V]) Comparator() cmp.Comparator[K]
- func (t *Tree[K, V]) Delete(key K) (value V, found bool)
- func (t *Tree[K, V]) DeleteBegin() (key K, value V, removed bool)
- func (t *Tree[K, V]) DeleteEnd() (key K, value V, removed bool)
- func (t *Tree[K, V]) End() (key K, value V, found bool)
- func (t *Tree[K, V]) Entries() ([]K, []V)
- func (t *Tree[K, V]) Floor(key K) (*Node[K, V], bool)
- func (t *Tree[K, V]) Get(key K) (val V, ok bool)
- func (t *Tree[K, V]) GetBeginNode() *Node[K, V]
- func (t *Tree[K, V]) GetEndNode() *Node[K, V]
- func (t *Tree[K, V]) GetNode(key K) *Node[K, V]
- func (t *Tree[K, V]) Has(key K) bool
- func (t *Tree[K, V]) IsEmpty() bool
- func (t *Tree[K, V]) Iter() iter.Seq2[K, V]
- func (t *Tree[K, V]) Keys() []K
- 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]) RIter() iter.Seq2[K, V]
- func (t *Tree[K, V]) String() string
- func (t *Tree[K, V]) ToSlice() []V
- 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 Color ¶ added in v0.2.0
type Color bool
Color represents the color of a red-black tree node (red or black).
type Node ¶
type Node[K comparable, V any] struct { // contains filtered or unexported fields }
Node represents a single element in the red-black tree.
func (*Node[K, V]) Color ¶ added in v0.2.0
Color returns the color of the node (red or black). This method provides read-only access to the node's color. Time complexity: O(1).
func (*Node[K, V]) Key ¶
func (n *Node[K, V]) Key() K
Key returns the key stored in the node. This key is used for ordering within the red-black tree. This method provides read-only access to the node's key. Time complexity: O(1).
func (*Node[K, V]) Left ¶
Left returns the left child of the node. It returns nil if the node has no left child. This method provides read-only access to the node's left child. Time complexity: O(1).
func (*Node[K, V]) Parent ¶
Parent returns the parent of the node. It returns nil if the node is the root or has no parent. This method provides read-only access to the node's parent. Time complexity: O(1).
func (*Node[K, V]) Right ¶
Right returns the right child of the node. It returns nil if the node has no right child. This method provides read-only access to the node's right child. Time complexity: O(1).
func (*Node[K, V]) Size ¶
Size returns the number of nodes in the subtree rooted at this node.
Computed dynamically by traversing the subtree. Time complexity: O(n).
type Tree ¶
type Tree[K comparable, V any] struct { // 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](cmp cmp.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]) Begin ¶ added in v0.2.3
Begin returns the minimum key and value in the tree. Returns found as true if an element is found, otherwise false. Time complexity: O(log n).
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]) Clone ¶ added in v0.2.3
Clone creates a deep copy of the tree. The new tree will have its own nodes, independent of the original tree. Time complexity: O(n), where n is the number of nodes in the tree.
func (*Tree[K, V]) Comparator ¶
func (t *Tree[K, V]) Comparator() cmp.Comparator[K]
Comparator returns the comparator used by the tree.
Time complexity: O(1).
func (*Tree[K, V]) Delete ¶ added in v0.2.3
Delete deletes the node with the given key from the tree.
Does nothing if key not found. Panics if key type is incompatible with comparator. Time complexity: O(log n).
func (*Tree[K, V]) DeleteBegin ¶ added in v0.2.3
DeleteBegin removes the minimum key-value pair from the tree. Returns the removed key, value, and true if an element was removed, otherwise false. Time complexity: O(log n).
func (*Tree[K, V]) DeleteEnd ¶ added in v0.2.3
DeleteEnd removes the maximum key-value pair from the tree. Returns the removed key, value, and true if an element was removed, otherwise false. Time complexity: O(log n).
func (*Tree[K, V]) End ¶ added in v0.2.3
End returns the maximum key and value in the tree. Returns found as true if an element is found, otherwise false. Time complexity: O(log n).
func (*Tree[K, V]) Entries ¶ added in v0.2.1
func (t *Tree[K, V]) Entries() ([]K, []V)
Entries 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]) 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]) 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]) GetBeginNode ¶ added in v0.2.3
GetLeftNode returns the leftmost (minimum key) node or nil if the tree is empty. Renamed from MinNode for clarity. Time complexity: O(log n).
func (*Tree[K, V]) GetEndNode ¶ added in v0.2.3
GetEndNode returns the rightmost (maximum key) node or nil if the tree is empty. Renamed from MaxNode for clarity. 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]) Has ¶ added in v0.2.3
Has checks if the given key exists in the tree. Returns true if the key is found, false otherwise. Panics if the key type is incompatible with the comparator. Time complexity: O(log n).
func (*Tree[K, V]) IsEmpty ¶ added in v0.2.3
IsEmpty checks if the tree contains no nodes.
Time complexity: O(1).
func (*Tree[K, V]) Iter ¶ added in v0.2.3
Iter returns an iterator over all key-value pairs in sorted order. Yields pairs in in-order traversal.
Time complexity: O(log n) per element.
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]) MarshalJSON ¶
MarshalJSON 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.
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]) RIter ¶ added in v0.4.0
RIter returns an iterator over all key-value pairs in reverse sorted order. Yields pairs in reverse in-order traversal.
Time complexity: O(log n) per element.
func (*Tree[K, V]) String ¶
String returns a string representation of the tree.
Time complexity: O(n).
func (*Tree[K, V]) ToSlice ¶ added in v0.2.3
func (t *Tree[K, V]) ToSlice() []V
ToSlice returns all values in in-order traversal based on keys.
Time complexity: O(n).
func (*Tree[K, V]) UnmarshalJSON ¶
UnmarshalJSON 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.
Time complexity: O(n log n), where n is the number of key-value pairs in the JSON.
Source Files