A Go library that provides a balanced binary search tree by using binary heap properties and randomization.
The height of the treap is proportional to the logarithm of the number
of values inserted with high probability. This characteristic means that,
on average, each Search(), Insert(), or Delete() operation takes logarithmic
time to perform.
To install go-treap, use go get.
go get github.com/austingebauer/go-treapThen import the library into your Go program.
import "github.com/austingebauer/go-treap"The go-treap API provides Search(), Insert(), and Delete() functions with
O(log n) time complexity on average.
Please refer to the GoDoc for additional API documentation of the library.
Example 1: Basic usage
trp := NewTreap()
trp.Insert("c")
trp.Insert("b")
trp.Insert("a")
trp.Search("a") // true
trp.Search("d") // false
trp.Delete("b")
trp.Delete("c")
trp.Delete("a")I recommend reading Julia Evan's Blog Post on Treaps for a simple explanation of the treap data structure.
Pull requests are welcome.
For major changes, please open an issue first to discuss what you would like to change.
Please make sure to update tests along with changes.