Treaps

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

• Treaps in Java, in Dr. Dobbs' Journal, by Stefan Nilsson, including Java source code. "If you could use only one data structure, which one would you choose?"
• Fast parallel set operations using treaps by G. Blellock and M. Reid-Miller. "Treaps have the advantage of being both simple and general... Our interest is in developing fast parallel algorithms for aggregate set operations."
• Implementing ordered sets using treaps, Cornell University lecture from CS312, Data Structures and Functional Programming. "Two well-known data structures for implementing ordered sets use randomness to achieve good average-case performance: skip lists and treaps. Treaps are simpler and probably faster."
• Treaps in Perl "I have this weakness for self organizing data structures, especially tree based ones."
• Treaps in Scheme "Compared to red-black trees, treaps are simpler and more elegant, and can get by without sentinels."
• Treaps in C# (includes source code) by Roy Clem. "I discovered the Treap while looking for a more efficient data structure than the hash table provided by Java, several years ago."
• Java animation of several types of trees, including treaps by Kubo Kovac. "By watching the visualization the user should more easily grasp the ideas behind the data structures."
• Treaps in Python by Dan Stromberg. "Treaps in pure python, or alternatively python augmented by some cython for a performance boost."

Original Papers on Treaps

• "Randomized Search Trees," (PDF) C. Aragon and R. Seidel, Proc. 30th IEEE Symposium on Foundations of Computer Science (1989), 540-546.
• "Randomized Search Trees," (PDF) R. Seidel and C. Aragon, Algorithmica 16 (1996) 464-497.