Treap 参考: http://www.prefield.com/algorithm/container/treap.html

Treap.cpp

#include <bits/stdc++.h>
using namespace std;

using Key = int;
using Value = int;

struct Treap {
    Key key;
    Value val;
    int pri;        // priority（小さい方が上）
    Treap *ch[2];   // left, right
    Treap(Key key, Value val) : key(key), val(val), pri(rand()) {
        ch[0] = ch[1] = NULL;
    }
};

// b: 回転方向
Treap *rotate(Treap *t, int b) {
    Treap *s = t->ch[1 - b];
    t->ch[1 - b] = s->ch[b];
    s->ch[b] = t;
    return s;   // 回転の結果上になったノードを返す
}

Treap *find(Treap *t, Key key) {
    return (!t || key == t->key) ? t : find(t->ch[key > t->key], key);
}

Treap *insert(Treap *t, Key key, Value val) {
    if (!t) return new Treap(key, val);
    else if (key == t->key) {
        // key が同じノードが既にあった場合、val を更新する
        t->val = val;
        return t;
    }
    int b = key > t->key;
    t->ch[b] = insert(t->ch[b], key, val);
    if (t->pri > t->ch[b]->pri) t = rotate(t, 1-b);
    return t;
}

Treap *erase(Treap *t, Key key) {
    if (!t) return NULL;
    if (key == t->key) {
        if (!t->ch[0] && !t->ch[1]) return NULL;
        else if (!t->ch[0]) t = rotate(t, 0);
        else if (!t->ch[1]) t = rotate(t, 1);
        else t = rotate(t, t->ch[0]->pri < t->ch[1]->pri);
        t = erase(t, key);
    }
    else {
        int b = key > t->key;
        t->ch[b] = erase(t->ch[b], key);
    }
    return t;
}

int height(Treap *t) {
    if (!t) return -1;
    return max(height(t->ch[0]), height(t->ch[1])) + 1;
}

int main() {
    for (int t = 0; t < 10; ++t) {
        Treap* root = NULL;
        for (int i = 0; i < 1 << 20; ++i) {
            root = insert(root, i, 0);
        }
        cout << height(root) << endl;
    }
}