package treap

import ""

Install: go get

Package treap provides a balanced binary search tree data structure, expected to have logarithmic height.

This implementation borrows a lot of ideas from GoLLRB.


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:


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.