Documentation ¶
Overview ¶
Package rbtree provides Red-black search binary tree implementation that supports ordered statistic
Index ¶
- func GetInt(c Comparable) int
- func GetInt64(c Comparable) int64
- type Comparable
- type Enumerable
- func NewAscend(t RbTree) Enumerable
- func NewAscendRange(t RbTree, from, to Comparable) Enumerable
- func NewDescend(t RbTree) Enumerable
- func NewDescendRange(t RbTree, from, to Comparable) Enumerable
- func NewOpenAscendRange(t RbTree, from, to Comparable) Enumerable
- func NewOpenDescendRange(t RbTree, from, to Comparable) Enumerable
- func NewWalkInorder(t RbTree) Enumerable
- func NewWalkPostorder(t RbTree) Enumerable
- func NewWalkPreorder(t RbTree) Enumerable
- type Int
- type Int64
- type Iterator
- type Node
- type NodeAction
- type RbTree
- type String
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func GetInt64 ¶ added in v0.7.0
func GetInt64(c Comparable) int64
GetInt64 gets int64 value from Comparable
Types ¶
type Comparable ¶
type Comparable interface { // Less gets whether value specified less then current value Less(y Comparable) bool // Equal gets whether value specified equal current value Equal(y Comparable) bool }
Comparable defines comparable type interface
func NewString ¶
func NewString(v string) Comparable
NewString creates new string Comparable implementation
type Enumerable ¶ added in v0.9.0
type Enumerable interface { // Iterator gets underlying Iterator Iterator() Iterator // Foreach enumerates tree and calls the callback for // every value in the tree until callback returns false. Foreach(callback NodeAction) }
Enumerable represents tree enumeration interface
func NewAscend ¶ added in v0.5.0
func NewAscend(t RbTree) Enumerable
NewAscend creates Enumerable that walks tree in ascending order
Example ¶
tree := New() tree.Insert(Int(6)) tree.Insert(Int(18)) tree.Insert(Int(3)) it := NewAscend(tree) it.Foreach(func(n Comparable) { fmt.Println(n) })
Output: 3 6 18
func NewAscendRange ¶ added in v0.5.0
func NewAscendRange(t RbTree, from, to Comparable) Enumerable
NewAscendRange creates Enumerable that walks tree in ascending order within the range [from, to]
Example ¶
tree := New() tree.Insert(Int(6)) tree.Insert(Int(18)) tree.Insert(Int(3)) it := NewAscendRange(tree, Int(3), Int(6)) it.Foreach(func(n Comparable) { fmt.Println(n) })
Output: 3 6
func NewDescend ¶ added in v0.5.0
func NewDescend(t RbTree) Enumerable
NewDescend creates Enumerable that walks tree in descending order
Example ¶
tree := New() tree.Insert(Int(6)) tree.Insert(Int(18)) tree.Insert(Int(3)) it := NewDescend(tree) it.Foreach(func(n Comparable) { fmt.Println(n) })
Output: 18 6 3
func NewDescendRange ¶ added in v0.5.0
func NewDescendRange(t RbTree, from, to Comparable) Enumerable
NewDescendRange that walks tree in descending order within the range [from, to]
Example ¶
tree := New() tree.Insert(Int(6)) tree.Insert(Int(18)) tree.Insert(Int(3)) it := NewDescendRange(tree, Int(6), Int(3)) it.Foreach(func(n Comparable) { fmt.Println(n) })
Output: 6 3
func NewOpenAscendRange ¶ added in v1.1.0
func NewOpenAscendRange(t RbTree, from, to Comparable) Enumerable
NewOpenAscendRange creates Enumerable that walks tree in ascending order within the range (from, to]) open means that both ends not necessary present in the tree. If not the nearest tree nodes will be found and iteration starts and stops using them
Example ¶
tree := New() tree.Insert(Int(6)) tree.Insert(Int(18)) tree.Insert(Int(3)) it := NewOpenAscendRange(tree, Int(2), Int(10)) it.Foreach(func(n Comparable) { fmt.Println(n) })
Output: 3 6
func NewOpenDescendRange ¶ added in v1.1.0
func NewOpenDescendRange(t RbTree, from, to Comparable) Enumerable
NewOpenDescendRange that walks tree in descending order within the range (from, to) open means that both ends not necessary present in the tree. If not the nearest tree nodes will be found and iteration starts and stops using them
Example ¶
tree := New() tree.Insert(Int(6)) tree.Insert(Int(18)) tree.Insert(Int(3)) it := NewOpenDescendRange(tree, Int(20), Int(5)) it.Foreach(func(n Comparable) { fmt.Println(n) })
Output: 18 6
func NewWalkInorder ¶ added in v0.5.0
func NewWalkInorder(t RbTree) Enumerable
NewWalkInorder creates Enumerable that walks tree inorder (left, node, right)
Example ¶
tree := New() tree.Insert(Int(6)) tree.Insert(Int(18)) tree.Insert(Int(3)) it := NewWalkInorder(tree) it.Foreach(func(n Comparable) { fmt.Println(n) })
Output: 3 6 18
func NewWalkPostorder ¶ added in v0.5.0
func NewWalkPostorder(t RbTree) Enumerable
NewWalkPostorder creates Enumerable that walks tree postorder (left, right, node)
Example ¶
tree := New() tree.Insert(Int(6)) tree.Insert(Int(18)) tree.Insert(Int(3)) it := NewWalkPostorder(tree) it.Foreach(func(n Comparable) { fmt.Println(n) })
Output: 3 18 6
func NewWalkPreorder ¶ added in v0.5.0
func NewWalkPreorder(t RbTree) Enumerable
NewWalkPreorder creates Enumerable that walks tree preorder (node, left, right)
Example ¶
tree := New() tree.Insert(Int(6)) tree.Insert(Int(18)) tree.Insert(Int(3)) it := NewWalkPreorder(tree) it.Foreach(func(n Comparable) { fmt.Println(n) })
Output: 6 3 18
type Int ¶
type Int int
Int is the int type key that can be stored as Node's key
func (Int) Equal ¶ added in v0.11.0
func (x Int) Equal(y Comparable) bool
Equal define Comparable interface member for Int
func (Int) Less ¶ added in v0.11.0
func (x Int) Less(y Comparable) bool
Less define Comparable interface member for Int
type Int64 ¶ added in v0.7.0
type Int64 int64
Int64 is the int64 type key that can be stored as Node's key
func (Int64) Equal ¶ added in v0.11.0
func (x Int64) Equal(y Comparable) bool
Equal define Comparable interface member for Int64
func (Int64) Less ¶ added in v0.11.0
func (x Int64) Less(y Comparable) bool
Less define Comparable interface member for Int64
type Iterator ¶ added in v0.5.0
type Iterator interface { // Current gets current Node Current() Comparable // Next advances the iterator and returns whether // the next call to the item method will return a // non-nil item. // // Next should be called prior to any call to the // iterator's item retrieval method after the // iterator has been obtained // // The order of iteration is implementation // dependent. Next() bool }
Iterator is an node iterator.
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node represent red-black tree node
func (*Node) Predecessor ¶
Predecessor gets Node's predecessor
Example ¶
tree := New() tree.Insert(Int(6)) tree.Insert(Int(18)) tree.Insert(Int(3)) root := tree.Root() n := root.Predecessor() fmt.Println(n.Key())
Output: 3
type NodeAction ¶ added in v0.9.0
type NodeAction func(Comparable)
NodeAction defines function prototype that used by an iteration method to iterate over portions of the tree.
type RbTree ¶
type RbTree interface { // Len returns the number of nodes in the tree. Len() int64 // Insert inserts new Node into Red-Black tree. Creates Root if tree is empty Insert(n Comparable) // ReplaceOrInsert inserts new Node into Red-Black tree. Creates Root if tree is empty // If an item in the tree // already equals the given one, it is removed from the tree and returned. // Otherwise, nil is returned. ReplaceOrInsert(n Comparable) Comparable // Delete searches and deletes Node with key value specified from Red-black tree // It returns true if Node was successfully deleted otherwise false Delete(c Comparable) bool // DeleteAll searches and deletes all found nodes with key value specified from Red-black tree // It returns true if nodes was successfully deleted otherwise false DeleteAll(c Comparable) bool // Search searches value specified within search tree Search(value Comparable) (Comparable, bool) // Floor searches value with the greatest data lesser than or equal to key value. Floor(value Comparable) (Comparable, bool) // Ceiling searches value with the smallest data larger than or equal to key value. Ceiling(value Comparable) (Comparable, bool) // SearchAll searches all values with the same key as specified within search tree SearchAll(value Comparable) []Comparable // SearchNode searches *Node which key is equals value specified SearchNode(value Comparable) (*Node, bool) // Minimum gets tree's min element Minimum() *Node // Maximum gets tree's max element Maximum() *Node // OrderStatisticSelect gets i element from subtree // IMPORTANT: numeration starts from 1 not from 0 OrderStatisticSelect(i int64) (*Node, bool) // Root gets tree root Node Root() *Node }
RbTree represents red-black tree interface
func New ¶ added in v0.11.0
func New() RbTree
New creates new empty Red-Black tree
Example ¶
tree := New() node := NewString("a") tree.Insert(node) size := tree.Len() fmt.Println(size) n, ok := tree.Search(node) fmt.Println(n) fmt.Println(ok) n, ok = tree.Search(NewString("b")) fmt.Println(n) fmt.Println(ok)
Output: 1 a true <nil> false
type String ¶
type String string
String is the string type key that can be stored as Node's key
func (*String) Equal ¶ added in v0.11.0
func (x *String) Equal(y Comparable) bool
Equal define Comparable interface member for String
func (*String) Less ¶ added in v0.11.0
func (x *String) Less(y Comparable) bool
Less define Comparable interface member for String