# Treaps

One of the simplest balanced tree data structures is the treap, a randomized tree that combines the invariants of a binary search tree and a heap. The idea is to give each node two keys: a tree key used for searching, and a heap key, which is chosen at random and used to decide which nodes rise to the top. If we ignore the heap keys, a treap is a binary search tree: the tree keys store the contents of the tree, and the tree key in each node is greater than all keys in its left subtree and less than all keys in its right subtree. If we ignore the tree keys: a treap is a heap: each node has a heap key that is larger than all heap keys in is descendants.

It is not immediately obvious that we can preserve both invariants at once, but if we are presented with an unorganized pile of nodes already assigned tree and heap keys, we can build a treap by making the node with the largest heap key the root, putting all the nodes with smaller tree heap keys in the left subtree and all the nodes with larger tree keys in the right subtree, then organizing both subtrees recursively in the same way. This tells use that for any assignment of tree and heap keys, a treap exists (and is in fact unique!), so the only trick is to make sure that it doesn’t cost too much to preserve the treap property when we insert a new element.

To insert a new node, we assign it a random heap key and insert it at a leaf using the usual method for a binary search tree. Because the new node’s random key may be large, this may violate the heap property. But we can rotate it up until the heap property is restored.

For deletions, we first have to search for a node with the key we want to delete, then remove it from the tree. If the node has has most one child, we can just patch it out, by changing its parent’s pointer to point to the child (or to null, if there is no child). If the node has two children, we pick the bigger one and rotate it up. Repeating this process will eventually rotate the node we are deleting down until it either has one child or is a leaf.

It’s not hard to see that the cost of any of these operations is proportional to length of some path in the treap. If all nodes have random heap keys, then the root node will be equally likely to be any of the nodes. This doesn’t guarantee that we get a good split, but a very bad split requires picking a root node close to one side or the other, which is unlikely. People smarter than I am have analyzed the expected height of a tree constructed in this way and show that the length of the longest path converges to (4.311…)log n in the limit (Devroye, A note on the height of binary search trees, JACM 1986; the upper bound is due to Robson, The height of binary search trees, Australian Computer Journal, 1979). This gives an O(log n) bound for the expected height in practice. However, we do have to be careful to make sure that whoever is supplying our inputs can’t see what heap keys we pick, or they will be able to generate an unbalanced tree by repeatedly inserting and deleting nodes until they draw bad heap keys.

Below is an example of a binary search tree implemented as a treap. You can also find much more about treaps on the web page of Cecilia Aragon, one of the inventors of treaps.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <limits.h>

#define NUM_CHILDREN (2)

#define LEFT (0)
#define RIGHT (1)

// Invariants:
// - Every key below child[LEFT] < key < every key below child[RIGHT]
// - Every heapKey in both subtreaps < heapKey.
// heapKeys are chosen randomly to ensure balance with high probability.
struct treap {
int key;
int heapKey;
struct treap *child[NUM_CHILDREN];
};

void
treapDestroy(struct treap *t)
{
if(t) {
for(int dir = LEFT; dir <= RIGHT; dir++) {
treapDestroy(t->child[dir]);
}
free(t);
}
}

void
treapPrintHelper(const struct treap *t, int depth)
{
if(t == 0) {
return;
}

treapPrintHelper(t->child[LEFT], depth+1);

// print indented root
for(int i = 0; i < depth; i++) {
putchar(' ');
}

printf("%d [%d]\n", t->key, t->heapKey);

treapPrintHelper(t->child[RIGHT], depth+1);
}

void
treapPrint(const struct treap *t)
{
treapPrintHelper(t, 0);
}

// return 1 if it finds key, 0 otherwise
int
treapSearch(const struct treap *t, int key)
{
if(t == 0) {
// no key!
return 0;
} else if(key == t->key) {
// found it
return 1;
} else if(key < t->key) {
// look in left
return treapSearch(t->child[LEFT], key);
} else {
// look in right
return treapSearch(t->child[RIGHT], key);
}
}

// return largest element <= key
// or INT_MIN if there is no such element.
int
treapSearchMaxLE(const struct treap *t, int key)
{
if(t == 0) {
// no key!
return INT_MIN;
} else if(key == t->key) {
// found it
return key;
} else if(key < t->key) {
// look in left
return treapSearchMaxLE(t->child[LEFT], key);
} else {
// look in right
int result = treapSearchMaxLE(t->child[RIGHT], key);

if(result == INT_MIN) {
// didn't find it
return t->key;
} else {
return result;
}
}
}

// rotate the treap pointed to by parent
// so that child in direction moves up
void
treapRotateUp(struct treap **parent, int dir)
{
// get pointers to anything that might move
assert(parent);
struct treap *child = *parent;
assert(child);
struct treap *grandchild = child->child[dir];
assert(grandchild);
struct treap *middleSubtreap = grandchild->child[!dir];

// do the move
*parent = grandchild;
grandchild->child[!dir] = child;
child->child[dir] = middleSubtreap;
}

// insert key into treap pointed to by parent
void
treapInsert(struct treap **parent, int key)
{
if(*parent == 0) {
// no key!
*parent = malloc(sizeof(struct treap));
(*parent)->key = key;
(*parent)->heapKey = rand();
(*parent)->child[LEFT] = (*parent)->child[RIGHT] = 0;
} else if(key == (*parent)->key) {
// found it
return;
} else if(key < (*parent)->key) {
// look in left
treapInsert(&(*parent)->child[LEFT], key);
} else {
// look in right
treapInsert(&(*parent)->child[RIGHT], key);
}

// check heap property
for(int dir = LEFT; dir <= RIGHT; dir++) {
if((*parent)->child[dir] != 0 && (*parent)->child[dir]->heapKey > (*parent)->heapKey) {
treapRotateUp(parent, dir);
}
}
}

// delete a node from a treap (if present)
void
treapDelete(struct treap **parent, int key)
{
// first we look for it
if(*parent == 0) {
// not there
return;
} else if(key == (*parent)->key) {
// got it; rotate down until we have a missing kid
for(;;) {
// do we have a missing child?
for(int dir = LEFT; dir <= RIGHT; dir++) {
if((*parent)->child[dir] == 0) {
// yes; free this node and promote other kid
struct treap *toDelete = *parent;
*parent = toDelete->child[!dir];
free(toDelete);
return;
}
}

// no missing child, have to rotate down
int biggerKid;
if((*parent)->child[LEFT]->heapKey > (*parent)->child[RIGHT]->heapKey) {
biggerKid = LEFT;
} else {
biggerKid = RIGHT;
}

// rotate up the bigger kid
treapRotateUp(parent, biggerKid);

// node to delete is now on opposite side
parent = &(*parent)->child[!biggerKid];
}
} else {
treapDelete(&(*parent)->child[key < (*parent)->key ? LEFT : RIGHT], key);
}
}

#define TEST_THRESHOLD (10)

int
main(int argc, char **argv)
{
if(argc != 1) {
fprintf(stderr, "Usage: %s\n", argv[0]);
return 1;
}

struct treap *t = 0;
int key;

while(scanf("%d", &key) == 1) {
if(key >= 0) {
treapInsert(&t, key);
} else {
treapDelete(&t, -key);
}

treapPrint(t);
printf("--- largest <= %d is %d\n", TEST_THRESHOLD, treapSearchMaxLE(t, TEST_THRESHOLD));
}

treapDestroy(t);

return 0;
}


examples/trees/treap/treap.c