Documentation
¶
Index ¶
- type Node
- func (n *Node) GrandParent() *Node
- func (n *Node) IsBlack() bool
- func (n *Node) Key() interface{}
- func (n *Node) Max() (node *Node)
- func (n *Node) Min() (node *Node)
- func (n *Node) Parent() *Node
- func (n *Node) Predecessor() *Node
- func (n *Node) Sibling() *Node
- func (n *Node) String() string
- func (n *Node) Successor() *Node
- func (n *Node) Uncle() *Node
- func (n *Node) Value() interface{}
- type RedBlackTree
- func (t *RedBlackTree) Ceiling(key interface{}) (ceiling *Node)
- func (t *RedBlackTree) Clear()
- func (t *RedBlackTree) Delete(key interface{}) (node *Node, success bool)
- func (t *RedBlackTree) DeleteNode(node *Node)
- func (t *RedBlackTree) Empty() bool
- func (t *RedBlackTree) Floor(key interface{}) (floor *Node)
- func (t *RedBlackTree) ForEach(iterator func(node *Node) bool)
- func (t *RedBlackTree) Get(key interface{}) (value interface{}, found bool)
- func (t *RedBlackTree) Keys() (keys []interface{})
- func (t *RedBlackTree) Max() *Node
- func (t *RedBlackTree) Min() *Node
- func (t *RedBlackTree) Node(key interface{}) (node *Node)
- func (t *RedBlackTree) Set(key interface{}, value interface{}) (node *Node, inserted bool)
- func (t *RedBlackTree) Size() int
- func (t *RedBlackTree) String() string
- func (t *RedBlackTree) Values() (values []interface{})
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node represents a Node in the RedBlackTree.
func (*Node) GrandParent ¶
GrandParent returns the parent of the parent Node (or nil if it does not exist).
func (*Node) IsBlack ¶
IsBlack returns true if the Node is marked as black (colors are used for the self-balancing properties of the RedBlackTree).
func (*Node) Key ¶
func (n *Node) Key() interface{}
Key returns the key that is used to identify the Node.
func (*Node) Parent ¶
Parent returns the parent of the Node (or nil if the Node is the root of the RedBlackTree).
func (*Node) Predecessor ¶
Predecessor returns the Node with the next lower key (or nil if none exists).
type RedBlackTree ¶
type RedBlackTree struct {
// contains filtered or unexported fields
}
RedBlackTree represents a self balancing binary search tree, that can be used to efficiently look up value associated to a set of keys.
func New ¶
func New(optionalComparator ...genericcomparator.Type) *RedBlackTree
New creates a new red-black RedBlackTree that uses the given comparator (or the default Comparator if the parameter is omitted) to compare the keys used to identify the nodes.
func (*RedBlackTree) Ceiling ¶
func (t *RedBlackTree) Ceiling(key interface{}) (ceiling *Node)
Ceiling returns the Node with the smallest key that is >= the given key (or nil if no ceiling was found).
func (*RedBlackTree) Clear ¶
func (t *RedBlackTree) Clear()
Clear removes all Nodes from the RedBlackTree.
func (*RedBlackTree) Delete ¶
func (t *RedBlackTree) Delete(key interface{}) (node *Node, success bool)
Delete removes a Node belonging to the given key from the RedBlackTree and returns it (if it existed) together with a flag that indicates if it existed.
func (*RedBlackTree) DeleteNode ¶
func (t *RedBlackTree) DeleteNode(node *Node)
DeleteNode removes the Node from the RedBlackTree (which can be i.e. useful for modifying the RedBlackTree while iterating.
func (*RedBlackTree) Empty ¶
func (t *RedBlackTree) Empty() bool
Empty returns true if the RedBlackTree has no Nodes.
func (*RedBlackTree) Floor ¶
func (t *RedBlackTree) Floor(key interface{}) (floor *Node)
Floor returns the Node with the largest key that is <= the given key (or nil if no floor was found).
func (*RedBlackTree) ForEach ¶
func (t *RedBlackTree) ForEach(iterator func(node *Node) bool)
ForEach iterates through the Nodes of the RedBlackTree in ascending order and calls the iterator function for each Node. The iteration aborts as soon as the iterator function returns false.
func (*RedBlackTree) Get ¶
func (t *RedBlackTree) Get(key interface{}) (value interface{}, found bool)
Get returns the value stored with the given key (or nil if the value does not exist with found being false).
func (*RedBlackTree) Keys ¶
func (t *RedBlackTree) Keys() (keys []interface{})
Keys returns an ordered list of keys that are stored in the RedBlackTree.
func (*RedBlackTree) Max ¶
func (t *RedBlackTree) Max() *Node
Max returns the Node with the largest key (or nil if the RedBlackTree is empty).
func (*RedBlackTree) Min ¶
func (t *RedBlackTree) Min() *Node
Min returns the Node with the smallest key (or nil if the RedBlackTree is empty).
func (*RedBlackTree) Node ¶
func (t *RedBlackTree) Node(key interface{}) (node *Node)
Node returns the Node that belongs to the given key (or nil if it doesn't exist).
func (*RedBlackTree) Set ¶
func (t *RedBlackTree) Set(key interface{}, value interface{}) (node *Node, inserted bool)
Set inserts or updates a Node in the RedBlackTree and returns it together with a flag that indicates if it was inserted.
func (*RedBlackTree) Size ¶
func (t *RedBlackTree) Size() int
Size returns the amount of Nodes in the RedBlackTree.
func (*RedBlackTree) String ¶
func (t *RedBlackTree) String() string
String returns a human readable version of the RedBlackTree.
func (*RedBlackTree) Values ¶
func (t *RedBlackTree) Values() (values []interface{})
Values returns an ordered list of values that are stored in the RedBlackTree.
Source Files