README
¶
RBTree
Generic implementation of red-black trees.
Installation
go get github.com/sirkon/rbtree
Usage example.
package main
import (
"fmt"
"github.com/sirkon/rbtree"
)
func main() {
t := rbtree.NewOrdered[int]()
t.Insert(10)
t.Insert(9)
t.Insert(5)
t.Insert(7)
t.Insert(1)
t.Delete(7)
it := t.Iter()
for it.Next() {
fmt.Println(it.Item())
}
// Output
// 1
// 5
// 9
// 10
}
Notice.
Remember, this is not map[K, V] analogue, no explicit values bounded to their keys support here.
Yet it is possible to emulate them:
package main
import (
"fmt"
"github.com/sirkon/rbtree"
)
type KeyValue struct {
Key string
Val string
}
// Cmp to implement rbtree.TreeKey
func (kv KeyValue) Cmp(elem KeyValue) int {
switch {
case kv.Key < elem.Key:
return -1
case kv.Key == elem.Key:
return 0
default:
return 1
}
}
func main() {
t := rbtree.New[KeyValue]()
t.Insert(KeyValue{Key: "1", Val: "a"})
t.Insert(KeyValue{Key: "2", Val: "b"})
it := t.Iter()
for it.Next() {
fmt.Println(it.Item().Key, "-", it.Item().Val)
}
// Output:
// 1 - a
// 2 - b
}
Documentation
¶
Overview ¶
Package rbtree generic implementation of red-black tree
Index ¶
- type Iterator
- type OrderedIterator
- type Tree
- func (t *Tree[T]) Add(v T) (fresh bool)
- func (t *Tree[T]) Delete(value T) (status bool)
- func (t *Tree[T]) Free()
- func (t *Tree[T]) Insert(v T) (existBefore bool)
- func (t *Tree[T]) InsertReturn(v T) T
- func (t *Tree[T]) Iter() *Iterator[T]
- func (t *Tree[T]) Len() int
- func (t *Tree[T]) Min() (val T, exists bool)
- type TreeIterator
- type TreeKey
- type TreeOrdered
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Iterator ¶
type Iterator[T TreeKey[T]] struct { // contains filtered or unexported fields }
Iterator an iterator over red-black tree nodes. Beware, the tree must not be changed during the iteration.
type OrderedIterator ¶
type OrderedIterator[T constraints.Ordered] struct { // contains filtered or unexported fields }
OrderedIterator iterator definition over red-black tree of ordereds.
func (OrderedIterator[T]) Item ¶
func (i OrderedIterator[T]) Item() T
Item to implement TreeIterator
func (OrderedIterator[T]) Next ¶
func (i OrderedIterator[T]) Next() bool
Next to implement TreeIterator
type Tree ¶
type Tree[T TreeKey[T]] struct { // contains filtered or unexported fields }
Tree definition of red-black tree.
TODO arena for element allocation is definitely a viable
idea.
func (*Tree[T]) Add ¶
Add adds new or replaces existing element. Returns true when and only when the element didn't exist before.
func (*Tree[T]) Delete ¶
Delete tries to delete existing value. Returns true when and only when the element exist.
func (*Tree[T]) Insert ¶
Insert tries to insert a new value. Returns true when and only when the tree actually had an element.
func (*Tree[T]) InsertReturn ¶
func (t *Tree[T]) InsertReturn(v T) T
InsertReturn tries to insert an element. Returns inserted element if it didn't exist. Returns existing element otherwise.
type TreeIterator ¶
TreeIterator an abstraction for iterators over red-black tree.
type TreeKey ¶
type TreeKey[T treeElementReferencer[T]] interface {
Cmp(elem T) int
}
TreeKey tree keys must satisfy this interface.
type TreeOrdered ¶
type TreeOrdered[T constraints.Ordered] struct { // contains filtered or unexported fields }
TreeOrdered a red-black tree with ordered values.
func NewOrdered ¶
func NewOrdered[T constraints.Ordered]() *TreeOrdered[T]
NewOrdered constructs a red-black tree with ordered elements.
func (TreeOrdered[T]) Delete ¶
func (t TreeOrdered[T]) Delete(n T) (status bool)
Delete tries to delete existing element. Returns true if the element existed.
func (TreeOrdered[T]) Insert ¶
func (t TreeOrdered[T]) Insert(n T) (status bool)
Insert tries to insert a non-existing element. Returns true if the element didn't exist indeed.
func (TreeOrdered[T]) Iter ¶
func (t TreeOrdered[T]) Iter() OrderedIterator[T]
Iter returns tree iterator.
Source Files