treap

my_treap.cpp

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

const int MAXN = 1000010; //1e6
struct node {
    int key, prio;
    node *ch[2];
} base[MAXN], *top, *root, *null, nil;

typedef node* tree;

inline tree newNode(int key) {
    static int seed = 3312;
    top -> key = key; top -> prio = seed = int((seed * 48271LL) & 2147483647);
    top -> ch[0] = top -> ch[1] = null;
    return top++;
}

inline void Rotate(tree &x, int d) {
    tree y = x -> ch[!d];
    x -> ch[!d] = y -> ch[d];
    y -> ch[d] = x;
    x = y;
}

void Insert(tree &t, int key) {
    if(t == null) t = newNode(key);
    else
    {
        int d = t -> key < key;
        Insert(t -> ch[d], key);
        if(t -> ch[d] -> prio < t -> prio) Rotate(t, !d);
    }
}

//assuming the key exists in the set
void Delete(tree &t, int key) {
    if (t -> key != key) {
        Delete(t -> ch[t -> key < key], key);
    }
    else if(t -> ch[0] == null) t = t -> ch[1];
    else if(t -> ch[1] == null) t = t -> ch[0];
    else {
        int d = t -> ch[0] -> prio < t -> ch[1] -> prio;
        Rotate(t, d);
        Delete(t -> ch[d], key);
    }
}

int main()
{
    srand(time(0));
    const int n = 1000000; //1e6
    null = &nil;
    top = base;
    root = newNode(0); //dummy new root
    clock_t t0 = clock();
    for(int i = 0; i < n; ++i)
    {
        Insert(root, rand()); //rand key insert
    }
    printf("Time: %f\n", ((float)clock() - t0) / CLOCKS_PER_SEC);
    return 0;
}