README
¶
wbtree
wbtree is a weight balanced binary search tree for go 1.18+
For more on weight balanced trees, see: https://yoichihirai.com/bst.pdf
Concurrent access
No. This library does not support concurrent access (it is not "thread-safe"). This may be addressed in a future release. It may not. It is probably at least feasible to make it lock-free...
Balance parameters
The choice of <3,2> as balance parameters here is mostly for the convienience of using simple integer values.
There's a somewhat faster setting, <1+sqrt(2), sqrt(2)>, which is not even rational.
The performance is quite close even with the integer params, so they are used, but it should be noted
that I've not benchmarked or even attempted any others yet.
Basic usage
package main
import (
"fmt"
"github.com/shawnsmithdev/wbtree"
"math/big"
)
func main() {
var example *wbtree.Tree[*big.Int, string]
var inserted, removed bool
// insert and update
example, inserted = example.Insert(big.NewInt(5), "fie")
fmt.Println(inserted) // true
example, inserted = example.Insert(big.NewInt(5), "five")
fmt.Println(inserted) // false
example, _ = example.Insert(big.NewInt(4), "four")
example, _ = example.Insert(big.NewInt(3), "three")
// remove
fmt.Println(example.Keys()) // 3, 4, 5
fmt.Println(example.Values()) // []string{"three", "four", "five"}
example, removed = example.Remove(big.NewInt(4))
fmt.Println(removed) // true
example, removed = example.Remove(big.NewInt(42))
fmt.Println(false) // true
fmt.Println(example.Values()) // []string{"three", "five"}
}
Documentation
¶
Index ¶
- type Cmpable
- type Tree
- func (t *Tree[K, V]) ForEach(f func(K, V) bool)
- func (t *Tree[K, V]) Get(key K) V
- func (t *Tree[K, V]) GetNode(key K) *Tree[K, V]
- func (t *Tree[K, V]) Greatest(n int) []*Tree[K, V]
- func (t *Tree[K, V]) GreatestKeys(n int) []K
- func (t *Tree[K, V]) GreatestNode() *Tree[K, V]
- func (t *Tree[K, V]) GreatestValues(n int) []V
- func (t *Tree[K, V]) Insert(key K, val V) (*Tree[K, V], bool)
- func (t *Tree[K, V]) Keys() []K
- func (t *Tree[K, V]) Least(n int) []*Tree[K, V]
- func (t *Tree[K, V]) LeastKeys(n int) []K
- func (t *Tree[K, V]) LeastNode() *Tree[K, V]
- func (t *Tree[K, V]) LeastValues(n int) []V
- func (t *Tree[K, V]) Remove(key K) (*Tree[K, V], bool)
- func (t *Tree[K, V]) ReverseForEach(f func(K, V) bool)
- func (t *Tree[K, V]) RootKey() (key K)
- func (t *Tree[K, V]) RootValue() (value V)
- func (t *Tree[K, V]) Size() uint64
- func (t *Tree[K, V]) Values() []V
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cmpable ¶
type Cmpable[T any] interface { // Cmp compares this value with other and returns: // -1 if this value < other // 0 if this value == other // +1 if this value > other Cmp(other T) int }
Cmpable are types that can do C style comparisons with a value of the parameter type. This is almost always the same type. For example, *big.Rat and *big.Int implement this interface.
type Tree ¶
Tree is a map implemented with a weight-balanced tree.
func (*Tree[K, V]) ForEach ¶
ForEach will call f for each node in this tree, in dfs order. If f returns false, interation stops.
func (*Tree[K, V]) Get ¶
func (t *Tree[K, V]) Get(key K) V
Get returns the value in this tree associated with key, or the zero value of V if key is not present
func (*Tree[K, V]) Greatest ¶ added in v0.0.3
Greatest returns a slice with length <= n holding the nodes this tree, in reverse dfs order (descending keys)
func (*Tree[K, V]) GreatestKeys ¶ added in v0.0.3
GreatestKeys returns a slice with length <= n holding the keys this tree, in reverse dfs order (descending keys)
func (*Tree[K, V]) GreatestNode ¶
GreatestNode returns the rightmost Tree node
func (*Tree[K, V]) GreatestValues ¶ added in v0.0.3
GreatestValues returns a slice with length <= n holding the values this tree, in reverse dfs order (descending keys)
func (*Tree[K, V]) Insert ¶
Insert adds a new value to this Tree, or updates an existing value. Returns the new root (the same node if not rebalanced). The returned bool is true if the Insert resulted in a new entry in the tree, false if an existing value was replaced.
func (*Tree[K, V]) Keys ¶
func (t *Tree[K, V]) Keys() []K
Keys returns a slice of all keys in dfs order (ascending keys)
func (*Tree[K, V]) Least ¶ added in v0.0.3
Least returns a slice with length <= n holding the nodes this tree, in dfs order (ascending keys)
func (*Tree[K, V]) LeastKeys ¶ added in v0.0.3
LeastKeys returns a slice with length <= n holding the keys this tree, in dfs order (ascending keys)
func (*Tree[K, V]) LeastValues ¶ added in v0.0.3
LeastValues returns a slice with length <= n holding the values this tree, in dfs order (ascending keys)
func (*Tree[K, V]) Remove ¶
Remove removes a node from a tree with the given key, if any exists. Returns the new root node, and a bool that is true if a node was removed.
func (*Tree[K, V]) ReverseForEach ¶ added in v0.0.3
ReverseForEach will call f for each node in this tree, in reverse dfs order. If f returns false, interation stops.
func (*Tree[K, V]) RootKey ¶
func (t *Tree[K, V]) RootKey() (key K)
RootKey returns the key of the root node of this tree.
func (*Tree[K, V]) RootValue ¶
func (t *Tree[K, V]) RootValue() (value V)
RootValue returns the stored value in the root node of this tree.
Source Files