東京工業大学で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;
}