+/* A treap is a combination of a binary search tree and a binary heap. The
+ * nodes are ordered according to the search keys, in the usual way, so that
+ * all the keys in a node's left subtree precede that node's key, and all of
+ * the keys in its right subtree follow the node's key. The trick is that
+ * the tree must /also/ satisfy the heap condition regarding randomly
+ * assigned `weights' attached to each node: so a node's weight must not be
+ * less than their weight of either of its children.
+ *
+ * This combination uniquely determines the structure of the tree, except for
+ * nodes whose weights exactly match one (or both) of their children. (The
+ * root must be the heaviest node in the tree. The root's key splits the
+ * remaining nodes into left and right subtrees, whose structure is then
+ * uniquely determined by induction.)
+ *
+ * This is an /intrusive/ data structure. A caller is expected to include a
+ * `struct treap_node' as (probably) the initial part of a larger structure.
+ */