Documentation
¶
Overview ¶
Package redblacktree implements a red-black tree.
Could be used as backed data-structure by TreeSet and TreeMap.
References: - http://en.wikipedia.org/wiki/Red%E2%80%93black_tree - https://en.wikipedia.org/wiki/AVL_tree - https://en.wikipedia.org/wiki/Binary_search_tree
Index ¶
- type Node
- type Tree
- func (t *Tree[K, V]) Ceiling(k K) *Node[K, V]
- func (t *Tree[K, V]) Clear()
- func (t *Tree[K, V]) Floor(k K) *Node[K, V]
- func (t *Tree[K, V]) Get(k K) (value V, ok bool)
- func (t *Tree[K, V]) InOrder() ([]K, []V)
- func (t *Tree[K, V]) Insert(k K, v V)
- func (t *Tree[K, V]) Keys() []K
- func (t *Tree[K, V]) Len() int
- func (t *Tree[K, V]) LevelOrder() ([]K, []V)
- func (t *Tree[K, V]) MarshalJSON() ([]byte, error)
- func (t *Tree[K, V]) Max() *Node[K, V]
- func (t *Tree[K, V]) Min() *Node[K, V]
- func (t *Tree[K, V]) Next(x *Node[K, V]) *Node[K, V]
- func (t *Tree[K, V]) PostOrder() ([]K, []V)
- func (t *Tree[K, V]) PostOrderByReverse() ([]K, []V)
- func (t *Tree[K, V]) PreOrder() ([]K, []V)
- func (t *Tree[K, V]) Prev(x *Node[K, V]) *Node[K, V]
- func (t *Tree[K, V]) Range(f func(k K, v V) bool)
- func (t *Tree[K, V]) Remove(k K)
- func (t *Tree[K, V]) Root() *Node[K, V]
- func (t *Tree[K, V]) Search(k K) *Node[K, V]
- func (t *Tree[K, V]) String() string
- func (t *Tree[K, V]) UnmarshalJSON(data []byte) error
- func (t *Tree[K, V]) Values() []V
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node[K comparable, V any] struct { // The value stored with this node. Value V // contains filtered or unexported fields }
Node is a node of a binary tree.
func (*Node[K, V]) Len ¶
Len returns the number of nodes of subtree with node n as the root. The complexity is O(n).
func (*Node[K, V]) Max ¶
Max returns the node which key is the maximum key of subtree with node n as the root.
func (*Node[K, V]) Min ¶
Min returns the node which key is the minimum key of subtree with node n as the root.
type Tree ¶
type Tree[K comparable, V any] struct { // contains filtered or unexported fields }
Tree represents an red-black tree.
Example ¶
package main
import (
"fmt"
"github.com/docodex/gopkg/container/tree/redblacktree"
)
func main() {
strs := []string{"Hello", "World", "Golang", "Python", "Rust", "C", "JavaScript", "Haskell", "Pascal", "ZZ"}
ints := []int{3, 5, 4, 1, 8, 6, 5, 7, 9, 0}
t1 := redblacktree.New[string, int]()
t2 := redblacktree.New[int, string]()
for i := range len(strs) {
t1.Insert(strs[i], ints[i])
t2.Insert(ints[i], strs[i])
}
k1 := t1.Keys()
v1 := t1.Values()
for i := range k1 {
fmt.Printf("%s:%d\n", k1[i], v1[i])
}
k2 := t2.Keys()
v2 := t2.Values()
for i := range k2 {
fmt.Printf("%d:%s\n", k2[i], v2[i])
}
}
Output: C:6 Golang:4 Haskell:7 Hello:3 JavaScript:5 Pascal:9 Python:1 Rust:8 World:5 ZZ:0 0:ZZ 1:Python 3:Hello 4:Golang 5:JavaScript 6:C 7:Haskell 8:Rust 9:Pascal
func New ¶
New returns an initialized tree with cmp.Compare as the cmp function.
func NewFunc ¶
func NewFunc[K comparable, V any](cmp container.Compare[K]) *Tree[K, V]
NewFunc returns an initialized tree with the given function cmp as the cmp function.
func (*Tree[K, V]) Ceiling ¶
Ceiling returns the ceiling node of key k, or nil if no such node found.
A ceiling node is defined as the smallest node which key is larger than or equal to the given key k. A ceiling node may not be found, either because the tree is empty, or because all keys in the tree is smaller than the given key k.
func (*Tree[K, V]) Floor ¶
Floor returns the floor node of the given key k, or nil if no such node found.
A floor node is defined as the largest node which key is smaller than or equal to the given key k. A floor node may not be found, either because the tree is empty, or because all keys in the tree is larger than the given key k.
func (*Tree[K, V]) Get ¶
Get returns the value which key equals to the given key k. The ok result indicates whether such value was found in tree.
func (*Tree[K, V]) InOrder ¶
func (t *Tree[K, V]) InOrder() ([]K, []V)
InOrder performs in-order traversal for tree, and returns a pair of slices (keys, values) as the result.
func (*Tree[K, V]) Insert ¶
func (t *Tree[K, V]) Insert(k K, v V)
Insert inserts a new node with the given key-value pair (k, v) to tree, or update the key and value if key k already exists in tree.
func (*Tree[K, V]) Keys ¶
func (t *Tree[K, V]) Keys() []K
Values returns all keys in tree (in in-order traversal order).
func (*Tree[K, V]) LevelOrder ¶
func (t *Tree[K, V]) LevelOrder() ([]K, []V)
LevelOrder performs level-order traversal for tree, and returns a pair of slices (keys, values) as the result.
func (*Tree[K, V]) MarshalJSON ¶
MarshalJSON marshals tree into valid JSON. Ref: std json.Marshaler.
func (*Tree[K, V]) Next ¶
Next returns the next node (in in-order traversal order) of the given node x, or nil if no such node found.
func (*Tree[K, V]) PostOrder ¶
func (t *Tree[K, V]) PostOrder() ([]K, []V)
PostOrder performs post-order traversal for tree, and returns a pair of slices (keys, values) as the result.
func (*Tree[K, V]) PostOrderByReverse ¶
func (t *Tree[K, V]) PostOrderByReverse() ([]K, []V)
PostOrderByReverse performs post-order traversal for tree by reverse the result slice, and returns a pair of slices (keys, values) as the result.
func (*Tree[K, V]) PreOrder ¶
func (t *Tree[K, V]) PreOrder() ([]K, []V)
PreOrder performs pre-order traversal for tree, and returns a pair of slices (keys, values) as the result.
func (*Tree[K, V]) Prev ¶
Prev returns the previous node (in in-order traversal order) of the given node x, or nil if no such node found.
func (*Tree[K, V]) Range ¶
Range calls f sequentially for each key-value pair (k, v) present in tree in in-order traversal order. If f returns false, range stops the iteration.
func (*Tree[K, V]) Remove ¶
func (t *Tree[K, V]) Remove(k K)
Remove removes the node which key equals to the given key k from tree.
func (*Tree[K, V]) Search ¶
Search returns the node which key equals to the given key k, or nil if no such node found.
func (*Tree[K, V]) String ¶
String returns the string representation of tree. Ref: std fmt.Stringer.
func (*Tree[K, V]) UnmarshalJSON ¶
UnmarshalJSON unmarshals a JSON description of tree. The input can be assumed to be a valid encoding of a JSON value. UnmarshalJSON must copy the JSON data if it wishes to retain the data after returning. Ref: std json.Unmarshaler.
Source Files