01 August, 2010

Treaps in Erlang

After a few months break I'm back to working on a project written mainly in Erlang and I'll be posting the most interesting pieces online to a small open-source project at Google Code, ErlAZ - Erlang A to Z.
The first module I'm uploading is an implementation of the Treap data structure.

What is a Treap?
It's a binary search tree where each node, in addition to its key and value, contains a number, called priority, assigned to it at insertion time.
All nodes are sorted horizontally by their key (so that a greater key is always to the right of a smaller one) and vertically by their priority (so that all parents of any given node up to the root have a higher priority than the node).
By choosing the priorities uniformly distributed across all keys (for example randomly), in the long run the treap will have the characteristic of a well-balanced tree, without having to re-balance it periodically.

I implemented my version as a drop-in replacement for the dict module, with all the dict functions having exactly the same signiture and behaviour, but working on treaps and performing according to the underlying tree structure vs. the hashtable used in dict.
There are also a few additional functions that use the ordered nature of the tree to allow querying and iterating over the keys in a sorted manner (which is pretty much the point of using a treap anyway), as well as functions for splitting the treap in two by a key (the first sub-treap contains all nodes with keys less or equal to the given key and the second - all nodes with greater keys) and for merging back a splitted treap.

The treap module comes with well documented functions and an extensive EUnit test suit (in a separate module treap_test), which contains tests and examples for the usage of each function.
As always all the code I release is covered by the New BSD License unless stated otherwise.
This means you are free to use it in any way you like, so help yourself:

  • ErlAZ trunk - The ErlAZ project's root with the Makefile for building the code and its documentation.

  • treap.erl - The treap module.

  • treap_test.erl - The treap_test module with all the EUnit tests.