Documentation
¶
Overview ¶
Package redblacktree implements a red-black tree.
Used by TreeSet and TreeMap.
Structure is not thread safe.
References: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Index ¶
- Constants
- type Key
- type Node
- type Tree
- func (tree *Tree) Ceiling(key *Key) (ceiling *Node, found bool)
- func (tree *Tree) Clear()
- func (tree *Tree) Empty() bool
- func (tree *Tree) Floor(key *Key) (floor *Node, found bool)
- func (tree *Tree) Get(key *Key) (found bool)
- func (tree *Tree) Left() *Node
- func (tree *Tree) Put(key *Key)
- func (tree *Tree) Remove(key *Key)
- func (tree *Tree) Right() *Node
- func (tree *Tree) Size() int
- func (tree *Tree) String() string
Constants ¶
const (
KeySize = 64
)
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node struct {
Key Key
Left *Node
Right *Node
Parent *Node
// contains filtered or unexported fields
}
Node is a single element within the tree
type Tree ¶
Tree holds elements of the red-black tree
func (*Tree) Ceiling ¶
Ceiling finds 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 are smaller than the given node.
Key should adhere to the comparator's type assertion, otherwise method panics.
func (*Tree) Floor ¶
Floor Finds floor node of the input key, return the floor node or nil if no floor 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 are larger than the given node.
Key should adhere to the comparator's type assertion, otherwise method panics.
func (*Tree) Get ¶
Get 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) Put ¶
Put inserts node into the tree. Key should adhere to the comparator's type assertion, otherwise method panics.
func (*Tree) Remove ¶
Remove remove the node from the tree by key. Key should adhere to the comparator's type assertion, otherwise method panics.
Source Files