# 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.

- If v is a left child of u, then key[v] < key[u];
- If v is a right child of u, then key[v] > key[u];
- If v is a child of u, then priority[v] > priority[u];

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

Treaps exhibit the properties of a BST and a heap.