Editing Treap (section)

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