# Euler tour tree implementation using a circular skip list

I implemented an euler tour tree using a skip list. Typically, a skip list is used as dictionary structures. However this skip list is merely used as a doubly linked list which can be joined and split fast, and can determine whether given two elements are in the same list.

My implementation is based on tmaehara's one. However, his implementation seems to be incorrect because certain node isn't cut properly (and mistake the usage of delete).

struct ETTSkipList {
mt19937 mt;
struct node { node *r, *l, *u; };
struct edge { node *uv, *vu; };

ETTSkipList() : mt(123) {}

int random_level() {
unsigned r = mt();
for (int i = 0; i < 15; i++) if (r >> i*2 & 3) return i + 1;
return 15;
}

node *up(node *u) {
if (!u) return u;
node *s = u;
do {
if (u->u) return u->u;
u = u->l;
} while (u != s);
return 0;
}

node *create() {
int h = random_level();
node *res = (node *)malloc(sizeof(node) * h);
node *t = res;
for (int i = 0; i < h; i++) {
t->l = t;
t->r = t;
t->u = i + 1 < h ? t + 1 : 0;
t++;
}
return res;
}

node *join(node *a, node *b) {
if (!a) return b;
if (!b) return a;
node *ar = a->r, *br = b->r;
a->r = br; br->l = a;
b->r = ar; ar->l = b;
return a;
}

edge link(node *u, node *v) {
node *uv = create();
node *vu = create();
edge res = {uv, vu};
while (true) {
node *u0 = up(u), *v0 = up(v);
if (!join(join(u, vu), join(v, uv))) break;
u = u0; v = v0;
if (uv) uv = uv->u;
if (vu) vu = vu->u;
}
return res;
}

void cut(edge e) {
node *u = e.uv, *v = e.vu;
while (u) {
node *ur = u->r, *vr = v->r;
node *uu = up(u), *vv = up(v);
u->r = vr; vr->l = u;
v->r = ur; ur->l = v;
u = uu; v = vv;
}
for (node *u = e.uv; u; u = u->u) {
u->r->l = u->l;
u->l->r = u->r;
}
for (node *u = e.vu; u; u = u->u) {
u->r->l = u->l;
u->l->r = u->r;
}
free(e.uv);
free(e.vu);
}

bool same(node *u, node *v) {
node *uu = 0, *vv = 0;
while (u) uu = u, u = up(u);
while (v) vv = v, v = up(v);
node *s = vv;
do {
if (uu == vv) return true;
vv = vv->l;
} while (vv != s);
return 0;
}
};

struct ETTSplayTree {
struct node {
node *l = nullptr;
node *r = nullptr;
node *p = nullptr;
node() {}
};

node *singleton() {
return new node();
}

pair<node *, node *> link(node *u, node *v) {
node *uv = new node();
node *vu = new node();
rotate(u);
rotate(v);
join(u, uv);
join(uv, v);
join(v, vu);
return { uv, vu };
}

void cut(pair<node *, node *> e) {
rotate(e.first);
split_right(e.first);
split_left(e.second);
split_right(e.second);
delete e.first;
delete e.second;
}

void rot(node *x) {
node *y = x->p, *z = y->p;
if (z) {
if (y == z->l) z->l = x;
if (y == z->r) z->r = x;
}
x->p = z; y->p = x;
if (x == y->l) {
y->l = x->r; x->r = y;
if (y->l) y->l->p = y;
} else {
y->r = x->l; x->l = y;
if (y->r) y->r->p = y;
}
}

node *splay(node *x) {
while (x->p) {
node *y = x->p, *z = y->p;
if (z) rot((x == y->l) == (y == z->l) ? y : x);
rot(x);
}
return x;
}

void join(node *x, node *y) {
if (!x || !y) return;
splay(x);
while (x->r) x = x->r;
splay(x);
splay(y);
x->r = y;
y->p = x;
}

node *split_left(node *x) {
splay(x);
node *y = x->l;
if (y) y->p = x->l = nullptr;
return y;
}

node *split_right(node *x) {
splay(x);
node *y = x->r;
if (y) y->p = x->r = nullptr;
return y;
}

void rotate(node *x) {
join(x, split_left(x));
}

bool same(node *x, node *y) {
node *xx = x, *yy = y;
while (x->p) x = x->p;
while (y->p) y = y->p;
splay(xx);
splay(yy);
return x == y;
}
};


#### References

[1] R. E. Tarjan: Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Journal Mathematical Programming, Series A and B 78(2): 169–177, 1997.
[2] R. E. Tarjan, R. F. Werneck: Dynamic trees in practice. Journal of Experimental Algorithms Volume 14, 2009.
[3] W. Pugh: Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM 33(6):668–676, 1990.