実装・実行
Insert 200000
Treap
Height 42; Ave. depth 21.255840;
Zip Tree
Height 52; Ave. depth 22.656550;
実装量はほぼ同じ。実装安を目指したので値の重複を許してinsertされる。再帰関数にしてしまったためZipTreeがやや遅いかもしれない。ランクは結局どちらもintで持たせたので省メモリの恩恵を受けていない。
上記の実装上の2つの違いは独立で、Treapの実装で1つだけ変更を加えてやるとかもできる。
実装は上半分がTreap、下半分がZip Tree。より良い実装はそのうち考える。
#include<climits>
#include<cassert>
#include<set>
#include<random>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;
typedef long long LL;
mt19937 engine(19480430);
struct Node {
int val;
int rnk;
Node *l, *r;
Node(int val_, int rnk_) : val(val_), rnk(rnk_), l(0), r(0) {}
};
typedef Node* Tree;
Tree find(Tree t, int val) {
while (t) {
if (val < t->val) {
t = t->l;
} else if (t->val < val) {
t = t->r;
} else {
return t;
}
}
return 0;
}
Tree rotate_right(Tree x) {
Tree y = x->l;
x->l = y->r;
y->r = x;
return y;
}
Tree rotate_left(Tree x) {
Tree y = x->r;
x->r = y->l;
y->l = x;
return y;
}
Tree treap_erase_minimum(Tree t, Tree y) {
if (!t->l) {
y->val = t->val;
y->rnk = t->rnk;
Tree x = t->r;
delete t;
return x;
} else {
t->l = treap_erase_minimum(t->l, y);
return t;
}
}
Tree treap_balance(Tree t) {
if (t->l && t->rnk <= t->l->rnk && (!(t->r) || t->l->rnk >= t->r->rnk)) {
t = rotate_right(t);
t->r = treap_balance(t->r);
} else if (t->r && t->rnk < t->r->rnk) {
t = rotate_left(t);
t->l = treap_balance(t->l);
}
return t;
}
int treap_rnk() {
return engine();
}
Tree treap_insert(Tree t, int val, int rnk) {
if (!t) {
return new Node(val, rnk);
} else {
if (val < t->val) {
t->l = treap_insert(t->l, val, rnk);
return (t->l->rnk >= t->rnk? rotate_right(t): t);
} else {
t->r = treap_insert(t->r, val, rnk);
return (t->r->rnk > t->rnk? rotate_left(t): t);
}
}
}
Tree treap_erase(Tree t, int val) {
if (!t) {
return 0;
} else {
if (val < t->val) {
t->l = treap_erase(t->l, val);
return t;
} else if (t->val < val) {
t->r = treap_erase(t->r, val);
return t;
} else if (!t->l || !t->r) {
Tree x = (t->l?: t->r);
delete t;
return x;
} else {
t->r = treap_erase_minimum(t->r, t);
return treap_balance(t);
}
}
}
Tree unzip_insert_root(Tree t, int val, int rnk) {
Tree x = new Node(val, rnk);
Tree low = x, high = x;
while (t) {
if (val < t->val) {
high = high->l = t;
t = t->l;
} else {
low = low->r = t;
t = t->r;
}
}
low->r = high->l = 0;
swap(x->l, x->r);
return x;
}
Tree zip_erase_root(Tree t) {
bool b = false;
Tree x = t;
Tree low = t->l, high = t->r;
while (low && high) {
if (low->rnk < high->rnk) {
(b? x->r: x->l) = high;
x = high;
b = false;
high = high->l;
} else {
(b? x->r: x->l) = low;
x = low;
b = true;
low = low->r;
}
}
(b? x->r: x->l) = (low?: high);
x = t->l;
delete t;
return x;
}
int zip_tree_rnk() {
unsigned x = engine() | (1u<<31);
return __builtin_ctz(x);
}
Tree unzip_insert(Tree t, int val, int rnk) {
if (!t) {
return new Node(val, rnk);
} else if (val < t->val) {
if (t->rnk <= rnk) {
return unzip_insert_root(t, val, rnk);
} else {
t->l = unzip_insert(t->l, val, rnk);
return t;
}
} else {
if (t->rnk < rnk) {
return unzip_insert_root(t, val, rnk);
} else {
t->r = unzip_insert(t->r, val, rnk);
return t;
}
}
}
Tree zip_erase(Tree t, int val) {
if (!t) {
return 0;
} else if (val < t->val) {
t->l = zip_erase(t->l, val);
return t;
} else if (t->val < val) {
t->r = zip_erase(t->r, val);
return t;
} else {
return zip_erase_root(t);
}
}
double depth_sum;
int height(Tree t, int depth=0) {
if (t) {
depth_sum += depth;
return max(height(t->l, depth+1), height(t->r, depth+1)) + 1;
} else {
return -1;
}
}
void show(Tree t, int depth=0) {
if (t) {
show(t->l, depth+1);
for (int i=0; i<depth; i++) printf("..");
printf("%d\n", t->val);
show(t->r, depth+1);
}
}
int last;
void verify(Tree t) {
if (t && t->l) {
assert(t->l->val <= t->val);
assert(t->l->rnk < t->rnk);
verify(t->l);
}
assert(last <= t->val);
last = t->val;
if (t && t->r) {
assert(t->val <= t->r->val);
assert(t->rnk >= t->r->rnk);
verify(t->r);
}
}
const int SIZE = 200000;
int A[SIZE];
int cnt[32];
int main() {
int cc = 0;
printf("Insert %d\n", SIZE);
puts("");
for (int i=0; i<SIZE; i++) A[i] = engine();
Tree treap = 0;
for (int i=0; i<SIZE; i++) {
int k = treap_rnk();
treap = treap_insert(treap, A[i], k);
cc++;
}
last = INT_MIN;
verify(treap);
printf("Treap\n");
int h = height(treap);
printf("Height %d; Ave. depth %f;\n", h, depth_sum / cc);
puts("");
Tree zipTree = 0;
cc = 0;
for (int i=0; i<SIZE; i++) {
int k = zip_tree_rnk();
cnt[k]++;
zipTree = unzip_insert(zipTree, A[i], k);
cc++;
}
last = INT_MIN;
verify(zipTree);
printf("Zip Tree\n");
depth_sum = 0;
h = height(zipTree);
printf("Height %d; Ave. depth %f;\n", h, depth_sum / cc);
puts("");
puts("");
printf("rnk distribution\n");
for (int i=0; i<32; i++) printf("%d%c", cnt[i], i==31?'\n':' ');
return 0;
}