README
¶
Scapegoat Tree
A Go library which implements the Scapegoat Tree data structure.
A Scapegoat Tree is a self-balancing binary search tree, which is based on the concept of a scapegoat. A scapegoat is typically a person who is blamed when there is a problem, and Scapegoat Trees use this term because they identify a node to “blame” when the tree becomes unbalanced. The tree could become unbalanced after an insertion or deletion of a node, and then an element would be identified as “the scapegoat” to accept the problem. This problem would be corrected by rebalancing the subtree at the scapegoat
A Scapegoat Tree provides worst-case O(log n) lookup time and O(log n) amortised insertion and deletion time.
Installation
go get github.com/umahmood/scapegoat
Usage
packgage main
import (
"fmt"
"github.com/umahmood/scapegoat"
)
func main() {
tree, err := scapegoat.New[int](scapegoat.DefaultAlpha)
// handle err
keys := []int{42, 99, 3}
for _, key := range keys {
err := sg.Insert(key)
// handle err
}
found := tree.Search(42)
fmt.Println("found 42?", found) // true
removed := tree.Remove(88)
fmt.Println("removed 88?", removed) // false
// stats
fmt.Println(tree.Stats.TotalInserts) // 3
fmt.Println(tree.Stats.TotalRemovals) // 0
fmt.Println(tree.Stats.TotalSearches) // 1
}
Documentation
References
License
See the LICENSE file for license rights and limitations (MIT).
Documentation
¶
Index ¶
Constants ¶
const DefaultAlpha float64 = 1.5
Variables ¶
var ( ConstraintErr = errors.New("constraint error.") AlphaValueErr = errors.New("alpha value must be greater than zero.") )
Functions ¶
This section is empty.
Types ¶
type Scapegoat ¶
type Scapegoat[T constraints.Ordered] struct { Stats Stats // contains filtered or unexported fields }
func New ¶
func New[T constraints.Ordered](alpha float64) (*Scapegoat[T], error)
New creates a new Scapegoat instance. The parameter alpha allows flexibility in deciding how balanced the tree should be. A high alpha value results in fewer balances, making insertion quicker but lookups and deletions slower, and vice versa for a low alpha.
func (*Scapegoat[T]) Insert ¶
Insert a key into the tree. The key will not inserted if it already exists.
Source Files