週刊 spaghetti_source

Scapegoat Tree

09:51

// Scapegoat Tree
// - insert  : O(log n) amortized !!don't insert same key!!
// - remove  : O(log n) amortized
// - find_key: O(log n) 
//
const int MAXSIZE = 1000;
int N = 1;
int ch[2][MAXSIZE];
int key[MAXSIZE];
int ndel, del[MAXSIZE];
int size[MAXSIZE], ht[MAXSIZE]; // including 'deleted' node
int update(int i) {
  if (!i) return i;
  size[i] = 1 + size[ch[0][i]] + size[ch[1][i]];
  ht[i]   = 1 + max(ht[ch[0][i]], ht[ch[1][i]]);
  return i;
}
int newnode(int k) {
  key[N] = k;
  ch[0][N] = ch[1][N] = 0;
  del[N] = 0;
  return update(N++);
}
int *flatten(int i, int *buf) {
  if (!i) return buf;
  buf = flatten(ch[0][i], buf);
  if (!del[i]) *buf++ = i;
  return flatten(ch[1][i], buf);
}
int makeBST(int *l, int *r) {
  if (r - l == 0) return 0;
  int *m = l+(r-l)/2;
  ch[0][*m] = makeBST(l, m);
  ch[1][*m] = makeBST(m+1, r);
  return update(*m);
}
int rebuild(int i) {
  static int buf[MAXSIZE];
  return makeBST(buf, flatten(i, buf));
}
const double beta = 3;
int insert(int i, int k) {
  if (!i) return newnode(k);
  int b = (k >= key[i]);
  ch[b][i] = insert(ch[b][i], k);
  update(i);
  return ht[i]>beta*log(size[i]) ? rebuild(i) : i;
}
int find_key(int i, int k) {
  if (!i || (!del[i] && k == key[i])) return i;
  return find_key(ch[k>=key[i]][i], k);
}
int remove(int i, int k) {
  del[find_key(i, k)] = 1, ++ndel;
  if (size[i] < 2*ndel) i = rebuild(i), ndel = 0;
  return i;
}

注意：上の実装は，本来の（Andersson, Galperin-Rivestの）「スケープゴート木」とは思想レベルで違いがあると思う．末尾の歴史的背景を参照．

スケープゴート木（Scapegoat Tree）は平衡二分探索木の一種．普通の平衡二分探索木は回転操作やマージ基準で平衡を保つものだけど，スケープゴート木は「平衡状態（log(木のサイズ)≒木の高さ）でなくなったら，ぶっ壊して再構築する」というアグレッシブな平衡化手法（rebuild）をとる．再構築する際にO(n)かかるので１操作あたりの最悪計算量ではO(log n)は達成できないけれど，amortized（n回の操作平均）の意味ではO(log n)を達成する．

remove: Global Rebuilding

removeではノードを検索して「削除した」というマークを張るだけで，実際にはなにもせず，検索の際はそのノードを無いものとして扱う．そして，木全体のノードの半分に「削除した」マークがついたら木全体をrebuildする．このようにバランスが崩れたら全体をまるごと作りなおすテクニックをGlobal Rebuildingという．

removeの計算量は次のように評価できる：rebuildが行われた直後から次のrebuildまでに必要なremoveの回数を数えるとn/2回．すなわちn操作するのにO(n)時間．よって１回あたりにならすとbuildがamortized定数時間となり，結局１操作あたり検索の分でO(log n)となる．

insert: Partial Rebuilding

続いてinsert．まず，Global Rebuildingは適用できないことに注意しよう．rebuild直後から考えて最小値を連続で突っ込まれると数回で平衡状態が崩れてしまうので，そのたびにGlobal Rebuildingすると amortized O(n) になってしまう．

ところがこの状況をよく見ると，全体より先に部分木で平衡が壊れている部分が現れることがわかる．そこでinsertでは「挿入した点から再帰的に平衡が壊れている点を探してそこ以下をrebuild」とする．これをPartial Rebuildingという．

insertの計算量の厳密な見積りは大変なので，雰囲気のみ示す．木全体にrebuildが行われた直後から次の全体rebuildまでに必要なinsertの回数を数える（部分木のrebuildは無視）．左の子だけに要素を挿入されるのが最悪ケースで，そのとき全体のrebuildの前に左の子のrebuildが発生するはず，と考えると，結局「左の子が一様に深くなるまで」が必要なinsertの回数になる．これはO(n)回なので，結局根に対するrebuildはamortized定数時間になる．これが全ての点について言えるので結局O(log n)が操作時間になる．

厳密な証明には，木全体が再構築される条件が本当に上で良いのかということと，１回の挿入で部分再構築が何度も起きないことを示す必要がある（前者を示せば後者は自動的に従う）．

歴史的背景

ところでスケープゴート木はAndersson(1989)とGalperin-Rivest(1993)が初出だが，非平衡データ構造を破壊と再生で平衡化するテクニックはそれよりもかなり昔から知られていて，体系的な教科書すらそれ以前に出ている（M. H. Overmars: The Design of Dynamic Data Structures, LNCS 156, 1983）．

これを踏まえてスケープゴート木の何が新しかったかというのを考えると，おそらく平衡に関する情報をノードに持たせなくてよいという情報量の問題なのだと思う（Andersson「The obtained class of trees, general balanced trees, may be maintained at a logarithmic amortized cost with no balance information stored in the nodes」，Galperin-Rivest「Scapegoat trees, unlike most balanced-tree schemes, do not require keeping extra data (e.g. “colors” or “weights”) in the tree nodes」.）

この点で，冒頭の実装は高さを陽に管理しているので，思想的にスケープゴート木ではきっと無い．本来は再帰で降りるときに高さを計算し，rebuildが発生したらその点より上でのrebuildが発生しないようにするのだが，陽に管理したほうが実装量的に楽なのでそうしている．

教科書やWeb上の解説記事ではこのあたりを区別していないものが結構見受けられるのだが，実際はどうなっているのだろう．

続く予定．