rbtree

Documentation

Index

• type LessFunc
• type Node
  • func (node *Node[K, V]) GetChildByIndex(i int) *Node[K, V]
  • func (node *Node[K, V]) Key() K
  • func (node *Node[K, V]) Next() *Node[K, V]
  • func (node *Node[K, V]) NumChild() int
  • func (node *Node[K, V]) Parent() *Node[K, V]
  • func (node *Node[K, V]) Prev() *Node[K, V]
  • func (node *Node[K, V]) SetValue(value V)
  • func (node *Node[K, V]) Value() V
• type RBTree
  • func New[K constraints.Ordered, V any]() *RBTree[K, V]
  • func NewFunc[K comparable, V any](less LessFunc[K]) *RBTree[K, V]
  • func (tree *RBTree[K, V]) Clear()
  • func (tree RBTree[K, V]) Contains(key K) bool
  • func (tree *RBTree[K, V]) Erase(node *Node[K, V]) bool
  • func (tree RBTree[K, V]) Find(key K) *Node[K, V]
  • func (tree RBTree[K, V]) First() *Node[K, V]
  • func (tree RBTree[K, V]) Get(key K) V
  • func (tree *RBTree[K, V]) Insert(key K, value V) (*Node[K, V], bool)
  • func (tree *RBTree[K, V]) Keys() []K
  • func (tree RBTree[K, V]) Last() *Node[K, V]
  • func (tree RBTree[K, V]) Len() int
  • func (tree *RBTree[K, V]) Remove(key K) bool
  • func (tree RBTree[K, V]) Root() *Node[K, V]
  • func (tree *RBTree[K, V]) Values() []V

Types

type LessFunc

type LessFunc[T any] func(x, y T) bool

LessFunc represents a comparation function which reports whether x "less" than y

type Node

type Node[K comparable, V any] struct {
	// contains filtered or unexported fields
}

Node represents the Node of RBTree

func (*Node[K, V]) GetChildByIndex

func (node *Node[K, V]) GetChildByIndex(i int) *Node[K, V]

GetChildByIndex implements container.Node GetChildByIndex method

func (*Node[K, V]) Key

func (node *Node[K, V]) Key() K

Key returns node's key

func (*Node[K, V]) Next

func (node *Node[K, V]) Next() *Node[K, V]

func (*Node[K, V]) NumChild

func (node *Node[K, V]) NumChild() int

NumChild implements container.Node NumChild method

func (*Node[K, V]) Parent

func (node *Node[K, V]) Parent() *Node[K, V]

Parent implements container.Node Parent method

func (*Node[K, V]) Prev

func (node *Node[K, V]) Prev() *Node[K, V]

func (*Node[K, V]) SetValue

func (node *Node[K, V]) SetValue(value V)

SetValue sets node's value

func (*Node[K, V]) Value

func (node *Node[K, V]) Value() V

Value returns node's value

type RBTree

type RBTree[K comparable, V any] struct {
	// contains filtered or unexported fields
}

RBTree represents an red-black tree

func New

func New[K constraints.Ordered, V any]() *RBTree[K, V]

New creates an RBTree for ordered K

func NewFunc

func NewFunc[K comparable, V any](less LessFunc[K]) *RBTree[K, V]

NewFunc creates an RBTree with custom less function

func (*RBTree[K, V]) Clear

func (tree *RBTree[K, V]) Clear()

Clear clears the map

func (RBTree[K, V]) Contains

func (tree RBTree[K, V]) Contains(key K) bool

Contains reports whether the map contains the key

func (*RBTree[K, V]) Erase

func (tree *RBTree[K, V]) Erase(node *Node[K, V]) bool

Erase deletes the node, false returned if the node not found.

func (RBTree[K, V]) Find

func (tree RBTree[K, V]) Find(key K) *Node[K, V]

Find finds node by key, nil returned if the key not found.

func (RBTree[K, V]) First

func (tree RBTree[K, V]) First() *Node[K, V]

First returns the first node.

func (RBTree[K, V]) Get

func (tree RBTree[K, V]) Get(key K) V

Get retrives value by key

func (*RBTree[K, V]) Insert

func (tree *RBTree[K, V]) Insert(key K, value V) (*Node[K, V], bool)

Insert inserts a key-value pair, inserted node and true returned if the key not found, otherwise, existed node and false returned.

func (*RBTree[K, V]) Keys

func (tree *RBTree[K, V]) Keys() []K

Keys collects all keys of the tree as a slice

func (RBTree[K, V]) Last

func (tree RBTree[K, V]) Last() *Node[K, V]

Last returns the first node.

func (RBTree[K, V]) Len

func (tree RBTree[K, V]) Len() int

Len returns the number of elements

func (*RBTree[K, V]) Remove

func (tree *RBTree[K, V]) Remove(key K) bool

Remove removes an element by key, false returned if the key not found.

func (RBTree[K, V]) Root

func (tree RBTree[K, V]) Root() *Node[K, V]

Root returns root node

func (*RBTree[K, V]) Values

func (tree *RBTree[K, V]) Values() []V

Values collects all values of the tree as a slice