C[omp]ute

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