Main Page | See live article | Alphabetical index

Treap

In computer science, a Treap is a binary search tree (BST) that orders the nodes by adding a random number priority attribute to a node, as well as a key. The nodes are ordered so that the keys obey BST and the priorities obey the min heap order property.

(priority[v] > priority[u] means u was inserted before v)

Treaps exhibit the properties of a BST and a heap.