treap balanced binary search tree, for Go

Overview

This Go package provides a balanced binary search tree data structure, expected to have logarithmic height.

This implementation borrows a lot of ideas from GoLLRB.

Installation

Use go install:

go install github.com/stathat/treap

That's it.

If you are building your Go code with go install, you can skip the previous step and just import treap as follows:

import (
        "github.com/stathat/treap"
)

Usage

To create a tree, you need a function that will compare your keys. Here's one for int keys.

func IntLess(p, q interface{}) bool {
        return p.(int) < q.(int)
}

Then create the tree:

tree := NewTree(IntLess)

Put some stuff in it:

tree.Insert(5, "a")
tree.Insert(7, "b")
tree.Insert(2, "c")
tree.Insert(1, "d")

Get values:

x := tree.Get(2)

Check if a key exists:

if tree.Exists(17) { ... }

Delete a node:

tree.Delete(7)

Iterate over your data in order:

for v := range tree.IterAscend() {
        fmt.Printf("%s\n", v)
}

There are more functions. Look in treap.go for all of them.

Status

This package was extracted from production code powering StatHat, so clearly we feel that it is production-ready, but it should still be considered experimental as other uses of it could reveal issues we aren't experiencing.

Contact us

We'd love to hear from you if you are using this in your projects! Please drop us a line.

Author

Patrick Crosby