README
¶
scapegoat
This repository provides an implementation of Scapegoat Trees, as described in https://people.csail.mit.edu/rivest/pubs/GR93.pdf
Visualization
One of the unit tests supports writing its output to a Graphviz .dot file so
that you can see what the output looks like for different weighting conditions.
To use this, include the -dot flag when running the tests, e.g.,
# The -balance parameter is as specified for scapegoat.New.
go test -dot w300.dot -balance 300
Example output:
go test -dot x.dot -balance 50 -text limerick.txt
dot -Tpng -o limerick.png x.dot
Documentation
¶
Overview ¶
Package scapegoat implements a Scapegoat Tree, as described in the paper
I. Galperin, R. Rivest: "Scapegoat Trees" https://people.csail.mit.edu/rivest/pubs/GR93.pdf
A scapegoat tree is an approximately-balanced binary search tree structure with worst-case O(lg n) lookup and amortized O(lg n) insert and delete. The worst-case cost of a single insert or delete is O(n).
It is also relatively memory-efficient, as interior nodes do not require any ancillary metadata for balancing purposes, and the tree itself costs only a few words of bookkeeping overhead beyond the nodes. A rebalancing operation requires only a single contiguous vector allocation.
Index ¶
- func Less[Key constraints.Ordered](x, y Key) bool
- type LessFunc
- type Tree
- func (t *Tree[T]) Inorder(f func(key T) bool)
- func (t *Tree[T]) InorderAfter(key T, f func(key T) bool)
- func (t *Tree[T]) Insert(key T) bool
- func (t *Tree[T]) Len() int
- func (t *Tree[T]) Lookup(key T) (_ T, ok bool)
- func (t *Tree[T]) Max() T
- func (t *Tree[T]) Min() T
- func (t *Tree[T]) Remove(key T) bool
- func (t *Tree[T]) Replace(key T) bool
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Less ¶ added in v0.4.0
func Less[Key constraints.Ordered](x, y Key) bool
Less is a Less function for ordered types.
Types ¶
type Tree ¶
type Tree[T any] struct { // contains filtered or unexported fields }
A Tree is the root of a scapegoat tree. A *Tree is not safe for concurrent use without external synchronization.
func New ¶
New returns *Tree with the given balancing factor 0 ≤ β ≤ 1000 and keys. The balancing factor represents how unbalanced the tree is permitted to be, with 0 being strictest (as near as possible to 50% weight balance) and 1000 being loosest (no rebalancing).
New panics if β < 0 or β > 1000.
func (*Tree[T]) Inorder ¶
Inorder traverses t inorder and invokes f for each key until either f returns false or no further keys are available.
Example ¶
package main
import (
"fmt"
"github.com/creachadair/scapegoat"
)
func main() {
tree := scapegoat.New(15, scapegoat.Less[string], "eat", "those", "bloody", "vegetables")
tree.Inorder(func(key string) bool {
fmt.Println(key)
return true
})
}
Output: bloody eat those vegetables
func (*Tree[T]) InorderAfter ¶
InorderAfter traverses t inorder, considering only keys equal to or after key, and invokes f for each key until either f returns false or no further keys are available.
func (*Tree[T]) Insert ¶
Insert adds key into the tree if it is not already present, and reports whether a new node was added.
Example ¶
package main
import (
"fmt"
"github.com/creachadair/scapegoat"
)
func main() {
tree := scapegoat.New[string](200, scapegoat.Less[string])
tree.Insert("never")
tree.Insert("say")
tree.Insert("never")
fmt.Println("tree.Len() =", tree.Len())
}
Output: tree.Len() = 2
func (*Tree[T]) Len ¶
Len reports the number of elements stored in the tree. This is a constant-time query.
func (*Tree[T]) Lookup ¶
Lookup reports whether key is present in the tree, and returns the matching key if so, or a zero value if the key is not present.
Example ¶
package main
import (
"fmt"
"github.com/creachadair/scapegoat"
)
type Pair struct {
X string
V int
}
func (p Pair) less(q Pair) bool { return p.X < q.X }
func main() {
tree := scapegoat.New(1, Pair.less, []Pair{{
X: "mom",
V: 1,
}}...)
hit, ok := tree.Lookup(Pair{X: "mom"})
fmt.Printf("%v, %v\n", hit.V, ok)
miss, ok := tree.Lookup(Pair{X: "dad"})
fmt.Printf("%v, %v\n", miss.V, ok)
}
Output: 1, true 0, false
func (*Tree[T]) Max ¶
func (t *Tree[T]) Max() T
Max returns the maximum key from t. If t is empty, Max returns a zero key.
func (*Tree[T]) Min ¶
func (t *Tree[T]) Min() T
Min returns the minimum key from t. If t is empty, Min returns a zero key.
Example ¶
package main
import (
"fmt"
"github.com/creachadair/scapegoat"
)
func main() {
tree := scapegoat.New(50, scapegoat.Less[int], 1814, 1956, 955, 1066, 2016)
fmt.Println("len:", tree.Len())
fmt.Println("min:", tree.Min())
fmt.Println("max:", tree.Max())
}
Output: len: 5 min: 955 max: 2016
func (*Tree[T]) Remove ¶
Remove key from the tree and report whether it was present.
Example ¶
package main
import (
"fmt"
"github.com/creachadair/scapegoat"
)
func main() {
const key = "Aloysius"
tree := scapegoat.New[string](1, scapegoat.Less[string])
fmt.Println("inserted:", tree.Insert(key))
fmt.Println("removed:", tree.Remove(key))
fmt.Println("re-removed:", tree.Remove(key))
}
Output: inserted: true removed: true re-removed: false
Source Files