Treap

Treap
Type	Randomized 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)

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.