Editing Treap (section)

== Description ==
[[Image:TreapAlphaKey.svg|thumb|left|A treap with alphabetic key and numeric max heap order]]
The treap was first described by [[Raimund Seidel]] and [[Cecilia R. Aragon]] in 1989;<ref name="paper89">{{Citation | contribution=Randomized Search Trees |
first1=Cecilia R. | last1=Aragon | first2=Raimund | last2=Seidel |
title=30th Annual Symposium on Foundations of Computer Science |
contribution-url=http://faculty.washington.edu/aragon/pubs/rst89.pdf | pages=540–545 | year=1989 |
doi=10.1109/SFCS.1989.63531 | isbn=0-8186-1982-1 | publisher=IEEE Computer Society Press | location=Washington, D.C.|
title-link=Symposium on Foundations of Computer Science }}
</ref><ref name="paper96">
{{Citation | title=Randomized Search Trees |
first1=Raimund | last1=Seidel | first2=Cecilia R. | last2=Aragon |
journal=Algorithmica | volume=16 | issue=4/5 | pages=464–497 | year=1996 |
url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8602 |
doi=10.1007/s004539900061|
doi-broken-date=1 November 2024 }}</ref> its name is a [[portmanteau word|portmanteau]] of [[Tree data structure|tree]] and [[heap (data structure)|heap]].
It is a [[Cartesian tree]] in which each key is given a (randomly chosen) numeric priority. As with any binary search tree, the [[inorder traversal]] order of the nodes is the same as the sorted order of the keys. The structure of the tree is determined by the requirement that it be heap-ordered: that is, the priority number for any non-leaf node must be greater than or equal to the priority of its children. Thus, as with Cartesian trees more generally, the root node is the maximum-priority node, and its left and right subtrees are formed in the same manner from the subsequences of the sorted order to the left and right of that node.

An equivalent way of describing the treap is that it could be formed by inserting the nodes highest priority-first into a binary search tree without doing any rebalancing. Therefore, if the priorities are independent random numbers (from a distribution over a large enough space of possible priorities to ensure that two nodes are very unlikely to have the same priority) then the shape of a treap has the same probability distribution as the shape of a [[random binary search tree]], a search tree formed by inserting the nodes without rebalancing in a randomly chosen insertion order.  Because random binary search trees are known to have logarithmic height with high probability, the same is true for treaps.  This mirrors the [[Quicksort#Using_a_binary_search_tree|binary search tree argument]] that [[quicksort]] runs in expected <math>O(n \log n)</math> time.  If binary search trees are solutions to the [[Dynamic problem (algorithms)|dynamic problem]] version of sorting, then Treaps correspond specifically to dynamic quicksort where priorities guide pivot choices.

Aragon and Seidel also suggest assigning higher priorities to frequently accessed nodes, for instance by a process that, on each access, chooses a random number and replaces the priority of the node with that number if it is higher than the previous priority. This modification would cause the tree to lose its random shape; instead, frequently accessed nodes would be more likely to be near the root of the tree, causing searches for them to be faster.

Naor and Nissim<ref>{{citation
 |last1        = Naor
 |first1       = M.
 |author1-link = Moni Naor
 |last2        = Nissim
 |first2       = K.
 |date         = April 2000
 |doi          = 10.1109/49.839932
 |issue        = 4
 |journal      = IEEE Journal on Selected Areas in Communications
 |pages        = 561–570
 |title        = Certificate revocation and certificate update
 |url          = http://eprints.kfupm.edu.sa/29443/1/29443.pdf
 |volume       = 18
|s2cid = 13833836
 }}{{dead link|date=March 2018 |bot=InternetArchiveBot |fix-attempted=yes }}.</ref> describe an application in maintaining [[Public key certificate|authorization certificates]] in [[public-key cryptography|public-key cryptosystems]].