Documentation ¶
Index ¶
- Constants
- Variables
- type Color
- type Node
- type RbTree
- func (t *RbTree[K, V]) Begin() *Node[K, V]
- func (t *RbTree[K, V]) Clear()
- func (t *RbTree[K, V]) Delete(node *Node[K, V])
- func (t *RbTree[K, V]) Empty() bool
- func (t *RbTree[K, V]) Find(key K) (V, error)
- func (t *RbTree[K, V]) FindLowerBoundNode(key K) *Node[K, V]
- func (t *RbTree[K, V]) FindNode(key K) *Node[K, V]
- func (t *RbTree[K, V]) FindUpperBoundNode(key K) *Node[K, V]
- func (t *RbTree[K, V]) First() *Node[K, V]
- func (t *RbTree[K, V]) Insert(key K, value V)
- func (t *RbTree[K, V]) IsRbTree() (bool, error)
- func (t *RbTree[K, V]) IterFirst() *RbTreeIterator[K, V]
- func (t *RbTree[K, V]) IterLast() *RbTreeIterator[K, V]
- func (t *RbTree[K, V]) Last() *Node[K, V]
- func (t *RbTree[K, V]) RBegin() *Node[K, V]
- func (t *RbTree[K, V]) Size() int
- func (t *RbTree[K, V]) Traversal(visitor visitor.KvVisitor[K, V])
- type RbTreeIterator
- func (iter *RbTreeIterator[K, V]) Clone() iterator.ConstIterator[V]
- func (iter *RbTreeIterator[K, V]) Equal(other iterator.ConstIterator[V]) bool
- func (iter *RbTreeIterator[K, V]) IsValid() bool
- func (iter *RbTreeIterator[K, V]) Key() K
- func (iter *RbTreeIterator[K, V]) Next() iterator.ConstIterator[V]
- func (iter *RbTreeIterator[K, V]) Prev() iterator.ConstBidIterator[V]
- func (iter *RbTreeIterator[K, V]) SetValue(val V) error
- func (iter *RbTreeIterator[K, V]) Value() V
Constants ¶
const ( RED = false BLACK = true )
Define node 's colors
Variables ¶
var ErrorNotFound = errors.New("not found")
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node[K, V any] struct { // contains filtered or unexported fields }
Node is a tree node
type RbTree ¶
type RbTree[K, V any] struct { // contains filtered or unexported fields }
RbTree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.
func (*RbTree[K, V]) Find ¶
Find finds the first node that the key is equal to the passed key, and returns its value
func (*RbTree[K, V]) FindLowerBoundNode ¶
FindLowerBoundNode finds the first node that its key is equal or greater than the passed key, and returns it
func (*RbTree[K, V]) FindNode ¶
FindNode the first node that the key is equal to the passed key and return it
func (*RbTree[K, V]) FindUpperBoundNode ¶ added in v1.1.0
FindUpperBoundNode finds the first node that its key is greater than the passed key, and returns it
func (*RbTree[K, V]) Insert ¶
func (t *RbTree[K, V]) Insert(key K, value V)
Insert inserts a key-value pair into the RbTree.
func (*RbTree[K, V]) IterFirst ¶
func (t *RbTree[K, V]) IterFirst() *RbTreeIterator[K, V]
IterFirst returns the iterator of first node
func (*RbTree[K, V]) IterLast ¶
func (t *RbTree[K, V]) IterLast() *RbTreeIterator[K, V]
IterLast returns the iterator of first node
type RbTreeIterator ¶
type RbTreeIterator[K, V any] struct { // contains filtered or unexported fields }
RbTreeIterator is an iterator implementation of RbTree
func NewIterator ¶
func NewIterator[K, V any](node *Node[K, V]) *RbTreeIterator[K, V]
NewIterator creates a RbTreeIterator from the passed node
func (*RbTreeIterator[K, V]) Clone ¶
func (iter *RbTreeIterator[K, V]) Clone() iterator.ConstIterator[V]
Clone clones the iterator into a new RbTreeIterator
func (*RbTreeIterator[K, V]) Equal ¶
func (iter *RbTreeIterator[K, V]) Equal(other iterator.ConstIterator[V]) bool
Equal returns true if the iterator is equal to the passed iterator
func (*RbTreeIterator[K, V]) IsValid ¶
func (iter *RbTreeIterator[K, V]) IsValid() bool
IsValid returns true if the iterator is valid, otherwise returns false
func (*RbTreeIterator[K, V]) Key ¶
func (iter *RbTreeIterator[K, V]) Key() K
Key returns the node's key of the iterator point to
func (*RbTreeIterator[K, V]) Next ¶
func (iter *RbTreeIterator[K, V]) Next() iterator.ConstIterator[V]
Next moves the pointer of the iterator to the next node, and returns itself
func (*RbTreeIterator[K, V]) Prev ¶
func (iter *RbTreeIterator[K, V]) Prev() iterator.ConstBidIterator[V]
Prev moves the pointer of the iterator to the previous node, and returns itself
func (*RbTreeIterator[K, V]) SetValue ¶
func (iter *RbTreeIterator[K, V]) SetValue(val V) error
SetValue sets the node's value of the iterator point to
func (*RbTreeIterator[K, V]) Value ¶
func (iter *RbTreeIterator[K, V]) Value() V
Value returns the node's value of the iterator point to