go-treap

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.

Installation

To install go-treap, use go get.

go get github.com/austingebauer/go-treap

Then import the library into your Go program.

import "github.com/austingebauer/go-treap"

Usage

API

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")

Behavior

I recommend reading Julia Evan's Blog Post on Treaps for a simple explanation of the treap data structure.

Contributing

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.

License

MIT