treap

(data structure)

Definition: A binary search tree in which nodes have another key, called the priority. Operations also keep the nodes heap ordered with regard to the priority.

Generalization (I am a kind of ...)
binary search tree.

Specialization (... is a kind of me.)
randomized binary search tree.

Note: The name comes from "tree" and "heap".

Some call "randomized binary search trees" treaps, but strictly a treap does not define how priorities are assigned.

Author: PEB

Implementation

Oleg Kiselyov's (Scheme) and verification code and other links.

More information

Raimund G. Seidel and Cecilia R. Aragon, Randomized Search Trees, Algorithmica, 16:464-497 (1996). Also in 30th Annual Symposium on Foundations of Computer Science, pages 540-545, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 4 October 2021.
HTML page formatted Mon Oct 4 14:22:58 2021.

Cite this as:
Paul E. Black, "treap", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 4 October 2021. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/treap.html