An implementation of treap insertion in ANSI C. Inserts 1 to 30 into a treap in order, then prints the treap in Graphviz's dot format.

treap_insertion.c

#include <stdlib.h>
#include <stdio.h>

struct node {
    struct node *parent;
    struct node *left;
    struct node *right;
    int value;
    int weight;
};

typedef struct node node_t;

node_t *new_node(int value);

node_t *add_node(node_t *root, int value);
node_t *attach_leaf(node_t *root, node_t *leaf);
node_t *rotate_leaf(node_t *root, node_t *leaf);

void free_tree(node_t *root);

void print_tree(node_t *root);
void print_connections(node_t *root);
void print_connection(node_t *a, node_t *b);

int gen_weight();

int main() {
    int i;
    node_t *root = NULL;

    /* populate the tree by inserting 1-30 in order */
    for (i = 1; i <= 30; ++i) {
        root = add_node(root, i);
    }

    /* print the tree in Graphviz dot format */
    print_tree(root);

    /* free the memory taken by the tree */
    free_tree(root);
        
    return 0;
}

/* initializes a node */
node_t *new_node(int value) {
    node_t *node = malloc(sizeof(node_t));
    node->parent = NULL;
    node->left = NULL;
    node->right = NULL;
    node->value = value;
    node->weight = gen_weight();

    return node;
}

/* adds a node to the tree, returns the new root */
node_t *add_node(node_t *root, int value) {
    node_t *leaf = new_node(value);
    root = attach_leaf(root, leaf);
    return rotate_leaf(root, leaf);
}

/* attaches a leaf to the tree, returns the new root */
node_t *attach_leaf(node_t *root, node_t *leaf) {
    /* if there is no root, the leaf becomes the root */
    if (root == NULL) {
        return leaf;
    }

    /* attach the leaf recursively */
    if (root->value > leaf->value) {
        root->left = attach_leaf(root->left, leaf);
        root->left->parent = root;
    } else {
        root->right = attach_leaf(root->right, leaf);
        root->right->parent = root;
    }

    /* the root hasn't changed */
    return root;
}

/* rotates a leaf into heap order, returns the new root */
node_t *rotate_leaf(node_t *root, node_t *leaf) {
    /* no need for rotations if leaf is the only node */
    if (leaf->parent == NULL) {
        return leaf;
    }

    /* no need for rotations if leaf's weight is not less than its parent's */
    if (leaf->weight >= leaf->parent->weight) {
        return root;
    }

    /* remember leaf's grandparent for later */
    node_t *grandparent = leaf->parent->parent;

    if (grandparent == NULL) {
        /* leaf becomes the root if it has no grandparent */
        root = leaf;
    } else if (grandparent->left == leaf->parent) {
        /* or it becomes its grandparent's left child */
        grandparent->left = leaf;
    } else {
        /* or it becomes its grandparent's right child */
        grandparent->right = leaf;
    }

    /* now reposition its parent and children */
    if (leaf->parent->left == leaf) {
        /* right rotation */
        leaf->parent->left = leaf->right;
        leaf->right = leaf->parent;
    } else {
        /* left rotation */
        leaf->parent->right = leaf->left;
        leaf->left = leaf->parent;
    }

    /* finally set its grandparent to its parent */
    leaf->parent = grandparent;

    /* keep rotating and return the new root */
    return rotate_leaf(root, leaf);
}

/* frees all the nodes in a tree recursively */
void free_tree(node_t *root) {
    /* don't try to free NULL */
    if (root == NULL) {
        return;
    }

    /* free root's children, then root */
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

/* prints a tree to a Graphviz dot file */
void print_tree(node_t *root) {
    /* print open graph */
    printf("graph treap {\n");

    /* print the connnections */
    print_connections(root);

    /* print close graph */
    printf("}\n");
}

/* recursively prints the connections in a tree in Graphviz dot format */
void print_connections(node_t *root) {
    if (root == NULL) {
        return;
    }

    /* print left connections first */
    print_connection(root, root->left);
    print_connections(root->left);

    /* then print right connections */
    print_connection(root, root->right);
    print_connections(root->right);
}

/* prints a connection between two nodes in Graphviz dot format */
void print_connection(node_t *a, node_t *b) {
    static int counter = 0;

    /* can't print a connection if a is NULL */
    if (a == NULL) {
        return;
    }

    /* print an invisible connection if b is NULL */
    if (b == NULL) {
        printf("\"%d (%d)\" -- I%d [weight=2 style=invis];\n", a->value,
                a->weight, counter);
        printf("I%d [style=invis];\n", counter++);
        return;
    }

    printf("  \"%d (%d)\" -- \"%d (%d)\";\n", a->value, a->weight, b->value,
            b->weight);
}

/* generates a random weight for a node */
int gen_weight() {
    /* this is slightly off from a uniform distribution */
    return rand() % 100;
}