Editing Treap (section)

{{Short description|Random search tree data structure}}
{{Infobox data structure
| name = Treap
| type = Randomized [[binary search tree]]
| space_avg = ''O''(''n'')
| space_worst = ''O''(''n'')
| search_avg = ''O''(log ''n'')
| search_worst = ''O''(''n'')
| insert_avg = ''O''(log ''n'')
| insert_worst = ''O''(''n'')
| delete_avg = ''O''(log ''n'')
| delete_worst = ''O''(''n'')
| build_avg = ''O''(''nlogn'')
| build_worst = ''O''(''nlogn'')
| image = treap.svg
}}
{{Probabilistic}}
In [[computer science]], the '''treap''' and the '''randomized binary search tree''' are two closely related forms of binary search tree [[data structure]]s that maintain a dynamic set of ordered keys and allow [[binary search]]es among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, [[with high probability]] its height is proportional to the [[logarithm]] of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform.