Algoogle

Algorithm for Programming Contest

Treap

基本情報


計算量  
insert
erase
merge
split
空間

N := 要素数

解説


insert: 位置kに値valを挿入
erase: 位置kのノードを削除
merge: 木sと木tをマージ
split: 位置kで木を2つに分ける

Treapは二分探索木とヒープの両方の特徴を持っている.
ノードに優先度をつけ優先度が高い方が親にくる.
優先度をランダムに決めることでおおむね平衡になる.
実装が赤黒木などと比較して楽.
詳しくはプログラミングコンテストでのデータ構造 2 ~平衡二分探索木編~を参照のこと

コード


(treap.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
template<class T> class treap {
public:
    struct node {
        T val, sum;
        node *left, *right;
        int pri;
        unsigned sz;
        node(T val, int pri):val(val),sum(val),pri(pri),sz(1) {
            left = right = NULL;
        }
    };

    node *root;
    treap() : root(NULL) {
        srand(time(NULL));
    }

    unsigned size() { return size(root); }
    unsigned size(node *v) { return !v? 0: v->sz; }
    T sum(node *v) { return !v? 0: v->sum; }

    node *update(node *v) {
        v->sz = size(v->left)+size(v->right)+1;
        v->sum = sum(v->left)+sum(v->right)+v->val;
        return v;
    }

    node *merge(node *s, node *t) {
        if(!s or !t) return s? s: t;
        if(s->pri > t->pri) {
            s->right = merge(s->right, t);
            return update(s);
        }
        t->left = merge(s, t->left);
        return update(t);
    }

    pair<node*, node*> split(node *v, unsigned k) {
        if(!v) return pair<node*,node*>(NULL,NULL);
        if(k <= size(v->left)) {
            pair<node*,node*> s = split(v->left, k);
            v->left = s.second;
            return make_pair(s.first,update(v));
        }
        pair<node*, node*> s = split(v->right, k-size(v->left)-1);
        v->right = s.first;
        return make_pair(update(v),s.second);
    }

    node *find(unsigned k) {
        node *v = root;
        while(v) {
            unsigned s = size(v->left);
            if(s > k) v = v->left;
            else if(s == k) return v;
            else {
                v = v->right;
                k -= s+1;
            }
        }
        return v;
    }

    void insert(unsigned k, T val) { root = insert(root,k,val,rand()); }
    node *insert(node *t, unsigned k, T val, int pri) {
        pair<node*, node*> s = split(t,k);
        t = merge(s.first, new node(val,pri));
        t = merge(t, s.second);
        return update(t);
    }

    void erase(int k) { root = erase(root,k); }
    node *erase(node *t, unsigned k) {
        pair<node*, node*> u, v;
        u = split(t,k+1);
        v = split(u.first, k);
        t = merge(v.first, u.second);
        return update(t);
    }
};

Comments