東京工業大学でTarjan教授を拝見した
講義に出席した。顔を拝むのが目的。
Tarjan先生
我々が毎日書いているUnion-Findや強連結成分分解(lowlinkのやつ)の証明やらアルゴリズムやら考えたすごい人。
1時間の講義でZip Treeをマスターしよう。
Zip Tree
二分探索木の一つ。詳細な解説は講義に出た人の特権なので避けるがTreapにとても似ている。正直、名前聞いたことなかった。
Treapと比較して2つの違いがある
ランク
Treapはランダムな値を優先度としてノードに割り当てるがzip treeではそれをランクと呼ぶ。Treapでは経験上ノード1つに対してO(log n)ビットの追加メモリが必要だが、Zip TreeはO(log log n)ビット、多分。。。
実装ではこんな感じでいいだろうか?Treapのランクが32ビットなのに対し、Zip Treeは31以下(5ビット)で済んでいる。Treapで乱数の下位5ビットにすると壊滅する。
mt19937 engine; int zip_tree_rnk() { unsigned x = engine() | (1u<<31); return __builtin_ctz(x); } int treap_rnk() { return engine(); }
insert / delete
名にZipを冠するがinsert / deleteの操作から来ているようだ。トップダウンでできるのでループ処理で実装するのが簡単なはず。実装は一番下。
実装・実行
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; ////////////////////////////////////////////////// // Common; ////////////////////////////////////////////////// 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; } ////////////////////////////////////////////////// // Treap; ////////////////////////////////////////////////// // Subfunctions; 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; } // Main functions; 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); } } } ////////////////////////////////////////////////// // Zip Tree; ////////////////////////////////////////////////// // Subfunctions; 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; } // Main functions; 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); } } ////////////////////////////////////////////////// // Debug; ////////////////////////////////////////////////// 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(); // Empty Tree; Tree treap = 0; for (int i=0; i<SIZE; i++) { int k = treap_rnk(); treap = treap_insert(treap, A[i], k); cc++; } // for (int i=0; i<SIZE/2; i++) { // treap = treap_erase(treap, A[i]); // 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(""); // Empty Tree; 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++; } // for (int i=0; i<SIZE/2; i++) { // zipTree = zip_erase(zipTree, A[i]); // cc--; // } // show(zipTree); 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; }