## Treaps - Randomized Binary Search Trees

From: "andrew cooke" <andrew@...>

Date: Thu, 16 Feb 2006 14:56:24 -0300 (CLST)

A treap is a regular binary search tree, with one extension. The extension
is that every node in a tree, beside a key, a value, and references to
its left and right children, has an additional constant field, a priority.
The value of this field is set (to a random integer number) when the node
is constructed, and is not changed afterwards. At any given moment,
the priority of every non-leaf node never exceeds the priorities of its
children. When a new node is inserted, we check that this invariant holds;
otherwise, we perform a right or left rotation that swaps a parent and
its kid, keeping the ordering of keys intact; the changes may need to be
propagated recursively up. The priority property, and the fact they are
chosen at random, makes a treap look like a binary search tree built by
a random sequence of insertions.

http://okmij.org/ftp/Scheme/lib/treap.scm

Andrew