Splay木

説明

Splay木は自己組織化二分探索木である．新しい要素の追加や削除が起きたとき，その要素を木の根に移動させる．このとき同時に適当に平衡操作を施すことにより，木の高さがあまり高くなりすぎないようにする．

平衡二分探索木と違い，木の高さに関する上界は存在しない（昇順のデータ挿入で高さが O(n) になる）．しかし，ランダムに操作が施されたとき，splay の計算量（したがって insert, erase, find の計算量）は amortized で O(log n) となる．

計算量

• splay: O(log n)
• insert: O(log n)
• erase: O(log n)
• find: O(log n)

ただし amortized．

使い方

• splay(x, n): ヘルパー関数．x を根 n の場所まで移動させてできる木を返す．
• insert(x): x を Splay木に追加する．
• erase(x): （存在すれば）x を Splay木から削除する．
• find(x): 存在すれば x のポインタ，存在しないときは NULL を返す．

ソースコード

struct splay_tree {
  struct node {
    int key;
    node *l, *r;
    node(int key = 0, node *l = 0, node *r = 0) :
      key(key), l(l), r(r) { }
  } *root;
  node *splay(int x, node *t) {
    if (!t) return t;
    node N, *l = &N, *r = &N, *s;
    for (;;) {
      if (x < t->key) {
        if (t->l && x < t->l->key) s = t->l, t->l = s->r, s->r = t, t = s;
        if (!t->l) break;
        r->l = t, r = t, t = t->l;
      } else if (x > t->key) {
        if (t->r && x > t->r->key) s = t->r, t->r = s->l, s->l = t, t = s;
        if (!t->r) break;
        l->r = t, l = t, t = t->r;
      } else break;
    }
    l->r = t->l; r->l = t->r; t->l = N.r; t->r = N.l;
    return t;
  }
  node *find(int x) {
    root = splay(x, root);
    if (x == root->key) return root;
    else                return 0;
  }
  void insert(int x) {
    if (!root) root = new node(x);
    else {
      root = splay(x, root);
      if (x < root->key) {
        node *t = new node(x, root->l, root); root->l = 0; root = t;
      } else if (x > root->key) {
        node *t = new node(x, root, root->r); root->r = 0; root = t;
      }
    }
  }
  void erase(int x) {
    if (!find(x)) return;
    if (!root->l) root = root->r;
    else {
      node *t = root->r; root = splay(x, root->l); root->r = t;
    }
  }
  splay_tree() : root(0) { };
};

Verified