Cecilia Aragon Home Page

Short Bio

Extended Bio

CV

Treaps Links

 

Treaps

This page links to a collection of references on treaps, including source code in various languages.

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?"

Java animation by Arthur Chou, defining treaps and demonstrating how randomized search trees work.

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."

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.