scapegoat

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 New[T any](β int, lessThan LessFunc[T], keys ...T) *Tree[T]
  • 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

• Tree.Inorder
• Tree.Insert
• Tree.Lookup
• Tree.Min
• Tree.Remove

Functions

func Less

func Less[Key constraints.Ordered](x, y Key) bool

Less is a Less function for ordered types.

Types

type LessFunc

type LessFunc[T any] func(x, y T) bool

A LessFunc reports whether x should precede y in order.

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

func New[T any](β int, lessThan LessFunc[T], keys ...T) *Tree[T]

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

func (t *Tree[T]) Inorder(f func(key T) bool)

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

func (t *Tree[T]) InorderAfter(key T, f func(key T) bool)

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

func (t *Tree[T]) Insert(key T) bool

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

func (t *Tree[T]) Len() int

Len reports the number of elements stored in the tree. This is a constant-time query.

func (*Tree[T]) Lookup

func (t *Tree[T]) Lookup(key T) (_ T, ok bool)

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

func (t *Tree[T]) Remove(key T) bool

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

func (*Tree[T]) Replace

func (t *Tree[T]) Replace(key T) bool

Replace adds key to the tree, updating an existing key if it is already present. Reports whether a new node was added.