CentralNotice Treap From Wikipedia, the free encyclopedia Jump to: navigation , search Treap Type Randomized Binary Search Tree Time complexity in big O notation Average Worst case Space O(n) O(n) Search O(log n) amortized O(log n) Insert O(log n) amortized O(log n) Delete O(log n) amortized O(log n) Part of a series on Probabilistic data structures Bloom filter Quotient filter Skip list Random trees Random binary tree Treap Rapidly exploring random tree Related Randomized algorithm Computer science portal v t e 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 sh...