Spaghetti Source logo

Treap

説明

Treap は乱数を用いて期待的に平衡する二分探索木である.

各ノードには普通の二分探索木と同じく Key と Value が付加されており,二分探索木と同様に Key によって順序がついている.それに加えて各ノードは Priority を持ち,自分は自分の子供よりも大きな Priority を持つ.これを保つように木の回転を行っていく.これは極めてシンプルに実装できる.

Priority をランダムに割り当てると期待的に平衡することが示される.厳密に平衡しないため,頂点を手繰る速度は AVL 木や赤黒木に劣るが,回転操作が高速なので,頂点の追加・削除はそれらよりも高速になることがある.

計算量

ただし expexted

使い方

単なる二分探索木用途なら eval, cache などは不要で,50行程度になる.

typedef xxx Key;
Key の型.全順序を仮定.
typedef xxx Value;
Value の型.
typedef xxx Result;
eval の結果型.
Treap *find(Treap *, Key);
key を持つ要素のポインタを返す.
Treap *insert(Treap *, Key, Value);
(key, value) を挿入.
Treap *erase(Treap *, Key);
key を持つ要素を削除.
Result eval(Treap *);
値を評価する.キャッシュされていればそれを返す.

ソースコード

typedef int Key;
typedef int Value;
typedef int Result;
struct Treap {
  Key key;
  Value value;
  int p;
  bool cached;
  Result cache;
  Treap *ch[2]; // LEFT = ch[0], RIGHT = ch[1]
  Treap(const Key &key, const Value &value) : key(key), value(value),
    p(rand()), cached(0) { ch[0] = ch[1] = 0; }
};
Treap *rotate(Treap *t, int b) {
  Treap *s = t->ch[1-b]; t->ch[1-b] = s->ch[b]; s->ch[b] = t;
  s->cached = t->cached = false;
  return s;
}
Treap *find(Treap *t, const Key &key) {
  return !t || key == t->key ? t : find(t->ch[key<t->key], key);
}
Treap *insert(Treap *t, const Key &key, const Value &value) {
  if (!t) return new Treap(key, value);
  else if (key == t->key) return t;
  int b = !(key < t->key);
  t->ch[b] = insert(t->ch[b], key, value);
  if (t->p > t->ch[b]->p) t = rotate(t, 1-b);
  t->cached = false;
  return t;
}
Treap *erase(Treap *t, const Key &key) {
  if (!t) return NULL;
  if (key == t->key) {
    if (!t->ch[0] && !t->ch[1]) return NULL;
    else if (!t->ch[0]) t = rotate(t, 0);
    else if (!t->ch[1]) t = rotate(t, 1);
    else t = rotate(t, t->ch[0]->p<t->ch[1]->p);
    t = erase(t, key);
  } else {
    int b = !(key < t->key);
    t->ch[b] = erase(t->ch[b], key);
  }
  t->cached = false;
  return t;
}
Result eval(Treap *t) {
  if (!t) return 0;
  if (!t->cached)
    t->cache = eval(t->ch[0]) + eval(t->ch[1]) + 1; // CHANGE IT FLEXIBLE
  t->cached = true;
  return t->cache;
}
Treap *nth(Treap *t, int n) { // NTH ELEMENT
  int l = eval(t->ch[0]);
  if (n < l) return nth(t->ch[0], n);
  if (n > l) return nth(t->ch[1], n-l-1);
  return t;
}

Verified

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.11.17 02:55:42.