Treaps are binary search trees in which each node has both a key and a priority. Randomized search trees use random priorities in treaps to achieve good average-case performance. Sometimes the two terms are used interchangeably. The treap has been commended for its elegance and efficiency, and is now used in production applications ranging from wireless networking to memory allocation to fast parallel aggregate set operations.

This page links to a collection of references on treaps, including our original papers and source code in various languages. If you know of any other helpful references, please email me (Cecilia Aragon) and I'll add it to the list.

References and Source Code

Original Papers on Treaps