Treap

Treap
TypeRandomized binary search tree
Time complexity in big O notation
Operation Average Worst case
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
Space complexity
Space O(n) O(n)
Preview warning: Page using Template:Infobox data structure with unknown parameter "build_worst"
Preview warning: Page using Template:Infobox data structure with unknown parameter "build_avg"

In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches 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.