README
¶
stree
This package 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 stree implements the Scapegoat Tree, an approximately-balanced binary search tree.
A scapegoat tree supports worst-case O(lg n) lookup and amortized O(lg n) insertion and deletion (the worst-case cost of a single insert or delete operation is O(n)).
Scapegoat trees are 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. Rebalancing uses the Day-Stout-Warren (DSW) in-place algorithm, which does not require any additional heap allocations.
The scapegoat tree algorithm is described by the paper:
I. Galperin, R. Rivest: "Scapegoat Trees" https://people.csail.mit.edu/rivest/pubs/GR93.pdf
Index ¶
- type Cursor
- func (c *Cursor[T]) Clone() *Cursor[T]
- func (c *Cursor[t]) HasLeft() bool
- func (c *Cursor[T]) HasNext() bool
- func (c *Cursor[T]) HasParent() bool
- func (c *Cursor[T]) HasPrev() bool
- func (c *Cursor[t]) HasRight() bool
- func (c *Cursor[T]) Inorder(yield func(key T) bool)
- func (c *Cursor[T]) Key() T
- func (c *Cursor[T]) Left() *Cursor[T]
- func (c *Cursor[T]) Max() *Cursor[T]
- func (c *Cursor[T]) Min() *Cursor[T]
- func (c *Cursor[T]) Next() *Cursor[T]
- func (c *Cursor[T]) Prev() *Cursor[T]
- func (c *Cursor[T]) Right() *Cursor[T]
- func (c *Cursor[T]) Up() *Cursor[T]
- func (c *Cursor[T]) Valid() bool
- type KV
- type Tree
- func (t *Tree[T]) Add(key T) bool
- func (t *Tree[T]) Clear()
- func (t *Tree[T]) Clone() *Tree[T]
- func (t *Tree[T]) Cursor(key T) *Cursor[T]
- func (t *Tree[T]) Find(key T) *Cursor[T]
- func (t *Tree[T]) Get(key T) (_ T, ok bool)
- func (t *Tree[T]) Inorder(yield func(key T) bool)
- func (t *Tree[T]) InorderAfter(key T) iter.Seq[T]
- func (t *Tree[T]) IsEmpty() bool
- func (t *Tree[T]) Len() int
- 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
- func (t *Tree[T]) Root() *Cursor[T]
- func (t *Tree[T]) String() string
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cursor ¶ added in v0.4.0
type Cursor[T any] struct { // contains filtered or unexported fields }
A Cursor is an anchor to a location within a Tree that can be used to navigate the structure of the tree. A cursor is Valid if it points to a non-empty subtree of its tree.
func (*Cursor[T]) Clone ¶ added in v0.4.0
Clone returns a clone of c that points to the same location, but which is unaffected by subsequent movement of c (and vice versa).
func (*Cursor[t]) HasLeft ¶ added in v0.4.0
HasLeft reports whether c has a non-empty left subtree. An invalid cursor has no left subtree.
func (*Cursor[T]) HasNext ¶ added in v0.4.0
HasNext reports whether c has a successor. An invalid cursor has no successor.
func (*Cursor[T]) HasParent ¶ added in v0.4.0
HasParent reports whether c has a parent. An invalid cursor has no parent.
func (*Cursor[T]) HasPrev ¶ added in v0.4.0
HasPrev reports whether c has a predecessor. An invalid cursor has no predecessor.
func (*Cursor[t]) HasRight ¶ added in v0.4.0
HasRight reports whether c has a non-empty right subtree. An invalid cursor has no right subtree.
func (*Cursor[T]) Inorder ¶ added in v0.4.0
Inorder is a range function over each key of the subtree at c in order.
func (*Cursor[T]) Key ¶ added in v0.4.0
func (c *Cursor[T]) Key() T
Key returns the key at the current location of the cursor. An invalid Cursor returns a zero-valued key.
func (*Cursor[T]) Left ¶ added in v0.4.0
Left moves to the left subtree of c, and returns c. If c had no left subtree, it becomes invalid.
func (*Cursor[T]) Max ¶ added in v0.4.0
Max moves c to the maximum element of its subtree, and returns c.
func (*Cursor[T]) Min ¶ added in v0.4.0
Min moves c to the minimum element of its subtree, and returns c.
func (*Cursor[T]) Next ¶ added in v0.4.0
Next advances c to its successor in the tree, and returns c. If c had no successor, it becomes invalid.
func (*Cursor[T]) Prev ¶ added in v0.4.0
Prev advances c to its predecessor in the tree, and returns c. If c had no predecessor, it becomes invalid.
func (*Cursor[T]) Right ¶ added in v0.4.0
Right moves to the right subtree of c, and returns c. If c had no right subtree, it becomes invalid.
type KV ¶ added in v0.11.0
type KV[T, U any] struct { Key T Value U }
KV is a convenience type for storing key-value pairs in a Tree, where the key type T is used for comparison while the value type U is ignored. Use the Compare method to adapt a comparison for T to a KV on T.
For convenience of notation, you can create a type alias for an instantiation of this type:
type metrics = stree.KV[string, float64]
compare := metrics{}.Compare(cmp.Compare)
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/creachadair/mds/stree"
)
func main() {
// For brevity, it can be helpful to define a type alias for your items.
type item = stree.KV[int, string]
tree := stree.New(100, item{}.Compare(cmp.Compare))
tree.Add(item{1, "one"})
tree.Add(item{2, "two"})
tree.Add(item{3, "three"})
tree.Add(item{4, "four"})
for _, i := range []int{1, 3, 2} {
fmt.Println(tree.Cursor(item{Key: i}).Key().Value)
}
}
Output: one three two
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 a new tree with the given balancing factor 0 ≤ β ≤ 1000. The order of elements stored in the tree is provided by the comparison function, where compare(a, b) must be <0 if a < b, =0 if a == b, and >0 if a > b.
If any keys are given, the tree is initialized to contain them, otherwise an empty tree is created. When the initial set of keys is known in advance it is more efficient to add them during tree construction, versus versus adding them separately later.
The balancing factor controls 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). Stricter balance incurs more overhead for rebalancing, but provides faster lookups. A good default is 250.
New panics if β < 0 or β > 1000.
func (*Tree[T]) Add ¶
Add inserts key into the tree. If key is already present, Add returns false without modifying the tree. Otherwise it adds the key and returns true.
Example ¶
package main
import (
"fmt"
"strings"
"github.com/creachadair/mds/stree"
)
func main() {
tree := stree.New(200, strings.Compare)
fmt.Println("inserted:", tree.Add("never"))
fmt.Println("inserted:", tree.Add("say"))
fmt.Println("re-inserted:", tree.Add("never"))
fmt.Println("items:", tree.Len())
}
Output: inserted: true inserted: true re-inserted: false items: 2
func (*Tree[T]) Clear ¶
func (t *Tree[T]) Clear()
Clear discards all the values in t, leaving it empty.
func (*Tree[T]) Clone ¶ added in v0.12.0
Clone returns a deep copy of t with identical settings. Operations on the clone do not affect t and vice versa.
func (*Tree[T]) Cursor ¶ added in v0.4.0
Cursor constructs a cursor to the specified key, or nil if key is not present in the tree.
func (*Tree[T]) Find ¶ added in v0.22.2
Find returns a cursor to the smallest key in the tree greater than or equal to key. If no such key exists, Find returns nil.
func (*Tree[T]) Get ¶
Get 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 (
"cmp"
"fmt"
"github.com/creachadair/mds/stree"
)
type Pair struct {
X string
V int
}
func (p Pair) Compare(q Pair) int { return cmp.Compare(p.X, q.X) }
func main() {
tree := stree.New(1, Pair.Compare,
Pair{X: "angel", V: 5},
Pair{X: "devil", V: 7},
Pair{X: "human", V: 13},
)
for _, key := range []string{"angel", "apple", "human"} {
hit, ok := tree.Get(Pair{X: key})
fmt.Println(hit.V, ok)
}
}
Output: 5 true 0 false 13 true
func (*Tree[T]) Inorder ¶
Inorder is a range function that visits each key of t in order.
Example ¶
package main
import (
"fmt"
"strings"
"github.com/creachadair/mds/stree"
)
func main() {
tree := stree.New(15, strings.Compare, "eat", "those", "bloody", "vegetables")
for key := range tree.Inorder {
fmt.Println(key)
}
}
Output: bloody eat those vegetables
func (*Tree[T]) InorderAfter ¶
InorderAfter returns a range function for each key greater than or equal to key, in order.
func (*Tree[T]) Len ¶
Len reports the number of elements stored in the tree. This is a constant-time query.
func (*Tree[T]) Max ¶
func (t *Tree[T]) Max() T
Max returns the maximum key in t. If t is empty, a zero key is returned.
func (*Tree[T]) Min ¶
func (t *Tree[T]) Min() T
Min returns the minimum key in t. If t is empty, a zero key is returned.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/creachadair/mds/stree"
)
func main() {
tree := stree.New(50, cmp.Compare[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"
"strings"
"github.com/creachadair/mds/stree"
)
func main() {
const key = "Aloysius"
tree := stree.New(1, strings.Compare)
fmt.Println("inserted:", tree.Add(key))
fmt.Println("removed:", tree.Remove(key))
fmt.Println("re-removed:", tree.Remove(key))
}
Output: inserted: true removed: true re-removed: false
func (*Tree[T]) Replace ¶
Replace inserts key into the tree. If key is already present, Replace updates the existing value and returns false. Otherwise it adds key and returns true.
Source Files