README
¶
rbtree
Golang red-black tree.
Types
It uses a comparable type as a key and any type as a value.
Methods
| Method name | Time |
|---|---|
| Set | O(log2n) |
| SetNx | O(log2n) |
| Del | O(log2n) |
| Get | O(log2n) |
| GetEx | O(log2n) |
| IsExist | O(log2n) |
| Len | O(1) |
| Move | O(2log2n) |
| Max | O(log2n) |
| Min | O(log2n) |
| Empty | O(1) |
| Walk | O(log2n + m) |
| Slice | O(log2n + m) |
Memory usage
O(n×node),
where
node = 3*sizeof(uintptr) +
sizeof(Key) +
sizeof(bool) +
sizeof(Value) // data
Install
Get or update
go get -u github.com/logrusorgru/rbtree
Test
go test -cover -race github.com/logrusorgru/rbtree
Run benchmark
expensive
go test -timeout=30m -test.bench . github.com/logrusorgru/rbtree
limited
go test -test.benchtime=0.1s -test.bench . github.com/logrusorgru/rbtree
Usage
package main
import (
"fmt"
"github.com/logrusorgru/rbtree"
)
func main() {
// create new red-black tree
var tr = rbtree.New[int, string]()
// append value to tree
tr.Set(0, "zero")
tr.Set(12, "some value")
var t int = 98
tr.Set(t, "don't forget about int indexing")
tr.Set(199, "rbtree distributed under Unlicense, feel free to fork it")
tr.Set(2, "trash")
// delete value from tree
tr.Del(2)
// get it
fmt.Println(tr.Get(2))
fmt.Println(tr.Get(t))
// check existence only
fmt.Println(tr.IsExist(12))
fmt.Println(tr.IsExist(590))
// get count
fmt.Println(tr.Len())
// change index of value
tr.Move(12, 13)
fmt.Println(tr.Get(13))
fmt.Println(tr.IsExist(12))
// take min index and value
fmt.Println(tr.Min())
// max
fmt.Println(tr.Max())
// empty
tr.Empty()
fmt.Println(tr.Len())
fmt.Println(tr.Min())
fmt.Println(tr.Max())
fmt.Println(tr.Get(0))
}
See also
If you want to lookup the tree much more than change it, take a look at LLRB (if memory usage are critical) (read | source)
Licensing
Copyright © 2016-2022 Konstantin Ivanov. This work is free. It comes without any warranty, to the extent permitted by applicable law. You can redistribute it and/or modify it under the terms of the the Unlicense. See the LICENSE file for more details.
Documentation
¶
Overview ¶
Package rbtree is the red-black tree.
Index ¶
- Variables
- type Tree
- func (t *Tree[Key, Value]) Del(key Key) (deleted bool)
- func (t *Tree[Key, Value]) Empty()
- func (t *Tree[Key, Value]) Get(key Key) Value
- func (t *Tree[Key, Value]) GetEx(key Key) (val Value, ok bool)
- func (t *Tree[Key, Value]) IsExist(key Key) bool
- func (t *Tree[Key, Value]) Len() int
- func (t *Tree[Key, Value]) Max() (Key, Value)
- func (t *Tree[Key, Value]) Min() (Key, Value)
- func (t *Tree[Key, Value]) Move(oldKey, newKey Key) (moved bool)
- func (t *Tree[Key, Value]) Set(key Key, value Value) (added bool)
- func (t *Tree[Key, Value]) SetNx(key Key, value Value) (added bool)
- func (t *Tree[Key, Value]) Slice(from, to Key) (vals []Value)
- func (t *Tree[Key, Value]) SliceKeys(from, to Key) (keys []Key)
- func (t *Tree[Key, Value]) Walk(from, to Key, walkFunc WalkFunc[Key, Value]) (err error)
- type TreeInterface
- type TreeThreadSafe
- func (t *TreeThreadSafe[Key, Value]) Del(key Key) (deleted bool)
- func (t *TreeThreadSafe[Key, Value]) Empty()
- func (t *TreeThreadSafe[Key, Value]) Get(key Key) Value
- func (t *TreeThreadSafe[Key, Value]) GetEx(key Key) (val Value, ok bool)
- func (t *TreeThreadSafe[Key, Value]) IsExist(key Key) bool
- func (t *TreeThreadSafe[Key, Value]) Len() int
- func (t *TreeThreadSafe[Key, Value]) Max() (Key, Value)
- func (t *TreeThreadSafe[Key, Value]) Min() (Key, Value)
- func (t *TreeThreadSafe[Key, Value]) Move(oldKey, newKey Key) (moved bool)
- func (t *TreeThreadSafe[Key, Value]) Set(key Key, value Value) (added bool)
- func (t *TreeThreadSafe[Key, Value]) SetNx(key Key, value Value) (added bool)
- func (t *TreeThreadSafe[Key, Value]) Slice(from, to Key) (vals []Value)
- func (t *TreeThreadSafe[Key, Value]) SliceKeys(from, to Key) (keys []Key)
- func (t *TreeThreadSafe[Key, Value]) Tree() (tree *Tree[Key, Value])
- func (t *TreeThreadSafe[Key, Value]) Walk(from, to Key, walkFunc WalkFunc[Key, Value]) (err error)
- type WalkFunc
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrStop = errors.New("stop a walking")
ErrStop is the error for stop walking
Functions ¶
This section is empty.
Types ¶
type Tree ¶
type Tree[Key constraints.Ordered, Value any] struct { // contains filtered or unexported fields }
Tree is the RB-tree
func New ¶
func New[Key constraints.Ordered, Value any]() *Tree[Key, Value]
New creates the new RB-Tree
Example ¶
var tr = New[int, string]()
fmt.Printf("%T", tr)
Output: *rbtree.Tree[int,string]
func (*Tree[Key, Value]) Del ¶
Del deletes value by key. O(logn). It returns false, if key doesn't exits.
Example ¶
var tr = New[int, string]() tr.Set(0, "hello") tr.Del(0) fmt.Println(tr.IsExist(0))
Output: false
func (*Tree[Key, Value]) Empty ¶
func (t *Tree[Key, Value]) Empty()
Empty makes the tree empty O(1).
Example ¶
var tr = New[int, string]() tr.Set(0, "hello") tr.Set(1, "hi") tr.Empty() fmt.Println(tr.Len())
Output: 0
func (*Tree[Key, Value]) Get ¶
func (t *Tree[Key, Value]) Get(key Key) Value
Get O(logn). It returns zero value, if key doesn't exist.
Example ¶
var tr = New[int, string]() tr.Set(0, "hello") fmt.Println(tr.Get(0))
Output: hello
func (*Tree[Key, Value]) IsExist ¶
IsExist O(logn)
Example ¶
var tr = New[int, string]() tr.Set(0, "hello") fmt.Println(tr.IsExist(0))
Output: true
func (*Tree[Key, Value]) Len ¶
Len O(1)
Example ¶
var tr = New[int, string]() tr.Set(0, "hello") fmt.Println(tr.Len()) tr.Set(0, "hello") fmt.Println(tr.Len()) tr.Set(1, "hi") fmt.Println(tr.Len())
Output: 1 1 2
func (*Tree[Key, Value]) Max ¶
func (t *Tree[Key, Value]) Max() (Key, Value)
Max returns maximum index and its value O(logn)
Example ¶
var tr = New[int, string]() tr.Set(0, "hello") tr.Set(1, "hi") fmt.Println(tr.Max())
Output: 1 hi
func (*Tree[Key, Value]) Min ¶
func (t *Tree[Key, Value]) Min() (Key, Value)
Min returns minimum indexed and its value O(logn)
Example ¶
var tr = New[int, string]() tr.Set(0, "hello") tr.Set(1, "hi") fmt.Println(tr.Min())
Output: 0 hello
func (*Tree[Key, Value]) Move ¶
Move moves the value from one index to another. Silent. It just changes index of value O(2logn).
Example ¶
var tr = New[int, string]() tr.Set(0, "hello") tr.Move(0, 1) fmt.Println(tr.Get(1))
Output: hello
func (*Tree[Key, Value]) Set ¶
Set the value. O(logn). This will overwrite the existing value.
Example ¶
var tr = New[int, string]() tr.Set(0, "hello") fmt.Println(tr.Get(0))
Output: hello
func (*Tree[Key, Value]) Slice ¶
func (t *Tree[Key, Value]) Slice(from, to Key) (vals []Value)
Slice returns all values at given range if any.
Example ¶
var tr = New[int, string]() tr.Set(0, "zero") tr.Set(1, "one") tr.Set(2, "two") tr.Set(3, "three") fmt.Println(tr.Slice(1, 2)) fmt.Println(tr.Slice(2, 1))
Output: [one two] [two one]
func (*Tree[Key, Value]) SliceKeys ¶
func (t *Tree[Key, Value]) SliceKeys(from, to Key) (keys []Key)
SliceKeys returns all keys at given range if any.
func (*Tree[Key, Value]) Walk ¶
Walk on the Tree.
Any error returned by the WalkFunc stops a walking. Also, there is special ErrStop, for example:
if err := tr.Walk(0, 500, walkFunc); err != nil && err != rbtree.ErrStop {
log.Println(err) // real error
}
To pass through the entire tree, use the minimum possible and maximum possible values of the index. For example:
tr.Walk(math.MinUint, math.MaxUint, walkFunc)
The Tree shouldn't be modified inside the WalkFunc.
Example ¶
var tr = New[int, string]()
tr.Set(1, "one")
tr.Set(2, "two")
tr.Set(3, "three")
var walkFunc = func(key int, value string) error {
fmt.Println(key, "-", value)
return nil
}
tr.Walk(0, math.MaxInt, walkFunc)
Output: 1 - one 2 - two 3 - three
type TreeInterface ¶
type TreeInterface[Key constraints.Ordered, Value any] interface { Set(Key, Value) bool SetNx(Key, Value) bool Del(Key) bool Get(Key) Value GetEx(Key) (Value, bool) IsExist(Key) bool Len() int Empty() Move(Key, Key) bool Max() (Key, Value) Min() (Key, Value) Walk(Key, Key, WalkFunc[Key, Value]) error Slice(Key, Key) []Value SliceKeys(Key, Key) []Key }
type TreeThreadSafe ¶
type TreeThreadSafe[Key constraints.Ordered, Value any] struct { // contains filtered or unexported fields }
func NewThreadSafe ¶
func NewThreadSafe[Key constraints.Ordered, Value any]() ( tts *TreeThreadSafe[Key, Value])
NewThreadSafe creates the new thread-safe RB-Tree.
func ToThreadSafe ¶
func ToThreadSafe[Key constraints.Ordered, Value any](tree *Tree[Key, Value]) ( tts *TreeThreadSafe[Key, Value])
ToThreadSafe wraps a Tree.
func (*TreeThreadSafe[Key, Value]) Del ¶
func (t *TreeThreadSafe[Key, Value]) Del(key Key) (deleted bool)
Del deletes value by key. O(logn). It returns false, if key doesn't exits.
func (*TreeThreadSafe[Key, Value]) Empty ¶
func (t *TreeThreadSafe[Key, Value]) Empty()
Empty makes the tree empty O(1). It returns the Tree itself.
func (*TreeThreadSafe[Key, Value]) Get ¶
func (t *TreeThreadSafe[Key, Value]) Get(key Key) Value
Get O(logn). It returns zero value, if key doesn't exist.
func (*TreeThreadSafe[Key, Value]) GetEx ¶
func (t *TreeThreadSafe[Key, Value]) GetEx(key Key) (val Value, ok bool)
GetEx O(logn). It returns false, if key doesn't exist.
func (*TreeThreadSafe[Key, Value]) IsExist ¶
func (t *TreeThreadSafe[Key, Value]) IsExist(key Key) bool
IsExist O(logn)
func (*TreeThreadSafe[Key, Value]) Max ¶
func (t *TreeThreadSafe[Key, Value]) Max() (Key, Value)
Max returns maximum index and its value O(logn)
func (*TreeThreadSafe[Key, Value]) Min ¶
func (t *TreeThreadSafe[Key, Value]) Min() (Key, Value)
Min returns minimum indexed and its value O(logn)
func (*TreeThreadSafe[Key, Value]) Move ¶
func (t *TreeThreadSafe[Key, Value]) Move(oldKey, newKey Key) (moved bool)
Move moves the value from one index to another. Silent. It just changes index of value O(2logn).
func (*TreeThreadSafe[Key, Value]) Set ¶
func (t *TreeThreadSafe[Key, Value]) Set(key Key, value Value) (added bool)
Set the value. O(logn). This will overwrite the existing value.
func (*TreeThreadSafe[Key, Value]) SetNx ¶
func (t *TreeThreadSafe[Key, Value]) SetNx(key Key, value Value) (added bool)
SetNx doesn't overwrites an existing value.
func (*TreeThreadSafe[Key, Value]) Slice ¶
func (t *TreeThreadSafe[Key, Value]) Slice(from, to Key) (vals []Value)
Slice returns all values at given range if any.
func (*TreeThreadSafe[Key, Value]) SliceKeys ¶
func (t *TreeThreadSafe[Key, Value]) SliceKeys(from, to Key) (keys []Key)
SliceKeys returns all keys at given range if any.
func (*TreeThreadSafe[Key, Value]) Tree ¶
func (t *TreeThreadSafe[Key, Value]) Tree() (tree *Tree[Key, Value])
Tree returns underlying Tree.
func (*TreeThreadSafe[Key, Value]) Walk ¶
func (t *TreeThreadSafe[Key, Value]) Walk(from, to Key, walkFunc WalkFunc[Key, Value]) (err error)
Walk on the Tree.
Any error returned by the WalkFunc stops a walking. Also, there is special ErrStop, for example:
if err := tr.Walk(0, 500, walkFunc); err != nil && err != rbtree.ErrStop {
log.Println(err) // real error
}
To pass through the entire tree, use the minimum possible and maximum possible values of the index. For example:
tr.Walk(math.MinUint, math.MaxUint, walkFunc)
The Tree shouldn't be modified inside the WalkFunc.
Source Files