Treap Algorithm

A treap is a randomized binary search tree data structure whose name combines tree and heap, reflecting the two ordering properties it maintains at once. Raimund Seidel and Cecilia R. Aragon introduced it in 1989: each key inserted into a treap is given an independent, randomly chosen numeric priority, and the structure is kept ordered as a binary search tree by key while also kept ordered as a heap by priority, so that in effect the tree ends up shaped as if its keys had been inserted into an ordinary unbalanced binary search tree in a uniformly random order, without ever having to know or control that order directly. Because randomization does the work that explicit rebalancing does in structures such as red-black trees, a treap is comparatively simple to implement while still achieving, with high probability, a tree height proportional to the logarithm of the number of keys, giving search, insertion and deletion operations expected logarithmic time.