redblacktree

Documentation

Index

• type Iterator
  • func (iterator *Iterator) Key() interface{}
  • func (iterator *Iterator) Next() bool
  • func (iterator *Iterator) Value() interface{}
• type Node
  • func (node *Node) String() string
• type Tree
  • func NewWith(comparator utils.Comparator) *Tree
  • func NewWithIntComparator() *Tree
  • func NewWithStringComparator() *Tree
  • func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool)
  • func (tree *Tree) Clear()
  • func (tree *Tree) Empty() bool
  • func (tree *Tree) Floor(key interface{}) (floor *Node, found bool)
  • func (tree *Tree) Get(key interface{}) (value interface{}, found bool)
  • func (tree *Tree) Iterator() Iterator
  • func (tree *Tree) Keys() []interface{}
  • func (tree *Tree) Left() *Node
  • func (tree *Tree) Put(key interface{}, value interface{})
  • func (tree *Tree) Remove(key interface{})
  • func (tree *Tree) Right() *Node
  • func (tree *Tree) Size() int
  • func (tree *Tree) String() string
  • func (tree *Tree) Values() []interface{}

Types

type Iterator

type Iterator struct {
	// contains filtered or unexported fields
}

func (*Iterator) Key

func (iterator *Iterator) Key() interface{}

Returns the current element's key. Does not modify the state of the iterator.

func (*Iterator) Next

func (iterator *Iterator) Next() bool

Moves the iterator to the next element and returns true if there was a next element in the container. If Next() returns true, then next element's key and value can be retrieved by Key() and Value(). Modifies the state of the iterator.

func (*Iterator) Value

func (iterator *Iterator) Value() interface{}

Returns the current element's value. Does not modify the state of the iterator.

type Node

type Node struct {
	Key   interface{}
	Value interface{}

	Left   *Node
	Right  *Node
	Parent *Node
	// contains filtered or unexported fields
}

func (*Node) String

func (node *Node) String() string

type Tree

type Tree struct {
	Root *Node

	Comparator utils.Comparator
	// contains filtered or unexported fields
}

func NewWith

func NewWith(comparator utils.Comparator) *Tree

Instantiates a red-black tree with the custom comparator.

func NewWithIntComparator

func NewWithIntComparator() *Tree

Instantiates a red-black tree with the IntComparator, i.e. keys are of type int.

func NewWithStringComparator

func NewWithStringComparator() *Tree

Instantiates a red-black tree with the StringComparator, i.e. keys are of type string.

func (*Tree) Ceiling

func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool)

Find ceiling node of the input key, return the ceiling node or nil if no ceiling is found. Second return parameter is true if ceiling was found, otherwise false.

Ceiling node is defined as the smallest node that is larger than or equal to the given node. A ceiling node may not be found, either because the tree is empty, or because all nodes in the tree is smaller than the given node.

Key should adhere to the comparator's type assertion, otherwise method panics.

func (*Tree) Clear

func (tree *Tree) Clear()

Removes all nodes from the tree.

func (*Tree) Empty

func (tree *Tree) Empty() bool

Returns true if tree does not contain any nodes

func (*Tree) Floor

func (tree *Tree) Floor(key interface{}) (floor *Node, found bool)

Find floor node of the input key, return the floor node or nil if no ceiling is found. Second return parameter is true if floor was found, otherwise false.

Floor node is defined as the largest node that is smaller than or equal to the given node. A floor node may not be found, either because the tree is empty, or because all nodes in the tree is larger than the given node.

Key should adhere to the comparator's type assertion, otherwise method panics.

func (*Tree) Get

func (tree *Tree) Get(key interface{}) (value interface{}, found bool)

Searches the node in the tree by key and returns its value or nil if key is not found in tree. Second return parameter is true if key was found, otherwise false. Key should adhere to the comparator's type assertion, otherwise method panics.

func (*Tree) Iterator

func (tree *Tree) Iterator() Iterator

Returns a stateful iterator whose elements are key/value pairs.

func (*Tree) Keys

func (tree *Tree) Keys() []interface{}

Returns all keys in-order

func (*Tree) Left

func (tree *Tree) Left() *Node

Returns the left-most (min) node or nil if tree is empty.

func (*Tree) Put

func (tree *Tree) Put(key interface{}, value interface{})

Inserts node into the tree. Key should adhere to the comparator's type assertion, otherwise method panics.

func (*Tree) Remove

func (tree *Tree) Remove(key interface{})

Remove the node from the tree by key. Key should adhere to the comparator's type assertion, otherwise method panics.

func (*Tree) Right

func (tree *Tree) Right() *Node

Returns the right-most (max) node or nil if tree is empty.

func (*Tree) Size

func (tree *Tree) Size() int

Returns number of nodes in the tree.

func (*Tree) String

func (tree *Tree) String() string

func (*Tree) Values

func (tree *Tree) Values() []interface{}

Returns all values in-order based on the key.