Treaps

A Treap is a data structure that combines a binary search tree with the heap invariant, which means that any root node of any subtree has a higher priority than its children (with a max-heap invariant, that is).

The idea is that BSTs perform really well when the insertions are done randomly, as it tends to be balanced, so the Treap tries to simulate this randomness by assigning random priorities to the inserted nodes.

I quickly implemented insertion/removal only for the purpose of learning and haven't refactored it, so the code could probably be further optimized/simplified.

Quick notes:

- Insertion: insert key X with a random priority. Insert works as in BSTs. Once the node is inserted, 'heapify' the node with the corresponding rotations.

- Removal: the opposite of the insertion. Find key X to remove, rotate the node down (preserving the heap invariant) until it becomes a leaf or has a null child and then remove it appropriately.

Further reference:
- http://en.wikipedia.org/wiki/Treap
- C implementation by Farooq Mela: https://github.com/fmela/libdict/blob/master/src/tr_tree.c

The Treap might perform better than BSTs, Skip Lists or other balanced trees such as Red-Black Trees, AVLs, AA trees or Splay Trees. Reference:

A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67-75)

Source code (netbeans project):

Download