Editing Treap (section)

== Operations ==

=== Basic operations ===
Treaps support the following basic operations:

*To search for a given key value, apply a standard [[binary search algorithm]] in a binary search tree, ignoring the priorities.
*To insert a new key ''x'' into the treap, generate a random priority ''y'' for ''x''. Binary search for ''x'' in the tree, and create a new node at the leaf position where the binary search determines a node for ''x'' should exist. Then, as long as ''x'' is not the root of the tree and has a larger priority number than its parent ''z'', perform a [[tree rotation]] that reverses the parent-child relation between ''x'' and ''z''.
*To delete a node ''x'' from the treap, if ''x'' is a leaf of the tree, simply remove it. If ''x'' has a single child ''z'', remove ''x'' from the tree and make ''z'' be the child of the parent of ''x'' (or make ''z'' the root of the tree if ''x'' had no parent). Finally, if ''x'' has two children, swap its position in the tree with the position of its immediate successor ''z'' in the sorted order, resulting in one of the previous cases. In this final case, the swap may violate the heap-ordering property for ''z'', so additional rotations may need to be performed to restore this property.

=== Building a treap ===

* To build a treap we can simply insert n values in the treap where each takes <math>O(\log n)</math> time. Therefore a treap can be built in <math>O(n \log n)</math> time from a list values.

===Bulk operations===
In addition to the single-element insert, delete and lookup operations, several fast "bulk" operations have been defined on treaps: [[Union (set theory)|union]], [[Intersection (set theory)|intersection]] and [[set difference]]. These rely on two helper operations, ''split'' and ''join''.

*To split a treap into two smaller treaps, those smaller than key ''x'', and those larger than key ''x'', insert ''x'' into the treap with maximum priority—larger than the priority of any node in the treap. After this insertion, ''x'' will be the root node of the treap, all values less than ''x'' will be found in the left subtreap, and all values greater than ''x'' will be found in the right subtreap. This costs as much as a single insertion into the treap.
*Joining two treaps that are the product of a former split, one can safely assume that the greatest value in the first treap is less than the smallest value in the second treap. Create a new node with value ''x'', such that ''x'' is larger than this max-value in the first treap and smaller than the min-value in the second treap, assign it the minimum priority, then set its left child to the first heap and its right child to the second heap. Rotate as necessary to fix the heap order. After that, it will be a leaf node, and can easily be deleted. The result is one treap merged from the two original treaps. This is effectively "undoing" a split, and costs the same. More generally, the join operation can work on two treaps and a key with arbitrary priority (i.e., not necessary to be the highest).
[[File:Treap merge.svg|thumb|Join performed on treaps <math>T_1</math> and <math>T_2</math>. Right child of <math>T_1</math> after the join is defined as a join of its former right child and <math>T_2</math>.]]
The join algorithm is as follows:

 '''function''' join(L, k, R)
     '''if''' prior(k, k(L)) and prior(k, k(R)) '''return''' Node(L, k, R)
     '''if''' prior(k(L), k(R)) '''return''' Node(left(L), k(L), join(right(L), k, R))
     '''return''' Node(join(L, k, left(R)), k(R), right(R))
[[File:Treap split.svg|thumb|To split <math>T</math> by <math>x</math>, recursive split call is done to either left or right child of <math>T</math>.]]
The split algorithm is as follows:

 '''function''' split(T, k)
     '''if''' (T = nil) '''return''' (nil, false, nil)
     (L, (m, c), R) = expose(T)
     '''if''' (k = m) '''return''' (L, true, R)
     '''if''' (k < m) 
         (L', b, R') = split(L, k)
         '''return''' (L', b, join(R', m, R))
     '''if''' (k > m) 
         (L', b, R') = split(R, k)
         '''return''' (join(L, m, L'), b, R'))

The union of two treaps {{math|''t''<sub>1</sub>}} and {{math|''t''<sub>2</sub>}}, representing sets {{mvar|A}} and {{mvar|B}} is a treap {{mvar|''t''}} that represents {{math|''A'' ∪ ''B''}}. The following recursive algorithm computes the union:

 '''function''' union(t<sub>1</sub>, t<sub>2</sub>):
     '''if''' t<sub>1</sub> = nil:
         '''return''' t<sub>2</sub>
     '''if''' t<sub>2</sub> = nil:
         '''return''' t<sub>1</sub>
     '''if''' priority(t<sub>1</sub>) < priority(t<sub>2</sub>):
         '''swap''' t<sub>1</sub> and t<sub>2</sub>
     t<sub><</sub>, t<sub>></sub> ← split t<sub>2</sub> on key(t<sub>1</sub>)
     '''return''' join(union(left(t<sub>1</sub>), t<sub><</sub>), key(t<sub>1</sub>),
                     union(right(t<sub>1</sub>), t<sub>></sub>))

Here, ''split'' is presumed to return two trees: one holding the keys less than its input key, one holding the greater keys. (The algorithm is [[persistent data structure|non-destructive]], but an in-place destructive version exists as well.)

The algorithm for intersection is similar, but requires the ''join'' helper routine. The complexity of each of union, intersection and difference is {{math|''O''(''m'' log {{sfrac|''n''|''m''}})}} for treaps of sizes {{mvar|m}} and {{mvar|n}}, with {{math|''m'' ≤ ''n''}}. Moreover, since the recursive calls to union are independent of each other, they can be executed [[parallel programming|in parallel]].<ref>{{citation
 | last1 = Blelloch | first1 = Guy E. 
 | last2 = Reid-Miller | first2 = Margaret 
 | title = Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures - SPAA '98 
 | contribution = Fast set operations using treaps
 | doi = 10.1145/277651.277660
 | isbn = 0-89791-989-0
 | location = New York, NY, USA
 | pages = 16–26
 | publisher = ACM
 | year = 1998| title-link = Symposium on Parallel Algorithms and Architectures 
 | s2cid = 7342709 
 }}.</ref> 

Split and Union call Join but do not deal with the balancing criteria of treaps directly, such an implementation is usually called the [[Join-based tree algorithms|"join-based" implementation]].

Note that if hash values of keys are used as priorities and structurally equal nodes are merged already at construction, then each merged node will be a unique representation of a set of keys. Provided that there can only be one simultaneous root node representing a given set of keys, two sets can be tested for equality by pointer comparison, which is constant in time.

This technique can be used to enhance the merge algorithms to perform fast also when the difference between two sets is small. If input sets are equal, the union and intersection functions could break immediately returning one of the input sets as result, while the difference function should return the empty set.

Let {{mvar|d}} be the size of the symmetric difference. The modified merge algorithms will then also be bounded by {{math|''O''(''d'' log {{sfrac|''n''|''d''}})}}.<ref>{{cite journal|last1=Liljenzin|first1=Olle|title=Confluently Persistent Sets and Maps|arxiv=1301.3388|bibcode=2013arXiv1301.3388L|year=2013}}</ref><ref name="Confluent Sets and Maps">[https://github.com/liljenzin/confluent Confluent Sets and Maps on GitHub]</ref>