| Treap |
|---|
|
| Type | Randomized binary search tree |
|---|
|
| Operation |
Average |
Worst case |
|---|
| Search |
O(log n) |
O(n) |
|---|
| Insert |
O(log n) |
O(n) |
|---|
| Delete |
O(log n) |
O(n) |
|---|
|
| 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.