Package scapegoat

import "bitbucket.org/creachadair/scapegoat"

Overview
Index
Examples

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

type Key
type Tree
func New(β int) *Tree
func NewKeys(β int, keys ...Key) *Tree
func (t *Tree) Inorder(f func(Key) bool)
func (t *Tree) InorderAfter(key Key, f func(Key) bool)
func (t *Tree) Insert(key Key) bool
func (t *Tree) Len() int
func (t *Tree) Lookup(key Key) (Key, bool)
func (t *Tree) Max() Key
func (t *Tree) Min() Key
func (t *Tree) Remove(key Key) bool
func (t *Tree) Replace(key Key) bool

Examples

(Expand All)

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

Package files

node.go scapegoat.go

type Key

A Key represents an entry in the tree, defined by having a ordering relationship with other keys. An implementation of this interface may carry additional data that does not affect comparison.

type Key interface {
    // Less reports whether the receiver is ordered prior to the argument.
    // If a.Less(b) == b.Less(a) == false, a and b will be assumed equal.
    //
    // If the receiver and argument are not comparable, the implementation
    // should panic.
    Less(Key) bool
}

type Tree

A Tree is the root of a scapegoat tree. A *Tree is not safe for concurrent use without external synchronization.

type Tree struct {
    // contains filtered or unexported fields
}

func New

func New(β int) *Tree

New returns an empty *Tree with the given balancing factor 0 ≤ β ≤ 1000. 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 NewKeys

func NewKeys(β int, keys ...Key) *Tree

NewKeys constructs a *Tree with the given balancing factor and keys. This is usually faster for a fixed set of keys than inserting the keys one by one into an empty tree. See New for a description of β.

func (*Tree) Inorder

func (t *Tree) Inorder(f func(Key) bool)

Inorder traverses t inorder and invokes f for each key until either f returns false or no further keys are available.

Example

Code:

tree := NewKeys(15, W("eat"), W("those"), W("bloody"), W("vegetables"))
tree.Inorder(func(key Key) bool {
    fmt.Println(key)
    return true
})

Output:

bloody
eat
those
vegetables

func (*Tree) InorderAfter

func (t *Tree) InorderAfter(key Key, f func(Key) 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) Insert

func (t *Tree) Insert(key Key) bool

Insert adds key into the tree if it is not already present, and reports whether a new node was added.

Example

Code:

// type W string
// func (w W) Less(key Key) bool { return w < key.(W) }

tree := New(200)
tree.Insert(W("never"))
tree.Insert(W("say"))
tree.Insert(W("never"))
fmt.Println("tree.Len() =", tree.Len())

Output:

tree.Len() = 2

func (*Tree) Len

func (t *Tree) Len() int

Len reports the number of elements stored in the tree.

func (*Tree) Lookup

func (t *Tree) Lookup(key Key) (Key, bool)

Lookup reports whether key is present in the tree, and returns it if so.

Example

Code:

tree := NewKeys(1, W("mom"))
hit, ok := tree.Lookup(W("mom"))
fmt.Printf("%v, %v\n", hit, ok)
miss, ok := tree.Lookup(W("dad"))
fmt.Printf("%v, %v\n", miss, ok)

Output:

mom, true
<nil>, false

func (*Tree) Max

func (t *Tree) Max() Key

Max returns the maximum key in the tree, or nil if the tree is empty.

func (*Tree) Min

func (t *Tree) Min() Key

Min returns the minimum key in the tree, or nil if the tree is empty.

Example

Code:

tree := NewKeys(50, Z(1814), Z(1956), Z(955), Z(1066), Z(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) Remove

func (t *Tree) Remove(key Key) bool

Remove key from the tree and report whether it was present.

Example

Code:

key := W("Aloysius")
tree := New(1)
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) Replace

func (t *Tree) Replace(key Key) bool

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

bitbucket.org/creachadair/scapegoat

scapegoat