skiplist

upd 2018-06-26: splay tree の same の実装が誤っていたため修正した。本来は根まで登った後に splay しなければならないが、それをしていなかった。

ET-tree の skiplist による実装を行った。辞書の実装に用いられる skiplist とは異なり、循環的構造を持たせている。

インタフェースの設計は tmaehara 氏の実装を参考にしている。ただし参照先の実装は cut が恐らく正しくない。algorithm/euler_tour_tree.cc at master · spaghetti-source/algorithm · GitHub

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, 33(6):668-676, 1990.