木メモ

プログラミング

はじめに

立派な庭師になるために、木についてちょっと調べてみたので、まとめておく。

木(構造)とは

  • 閉路を含まない無向グラフを「森」という
  • 連結な森を「木」という
    • 与えられた頂点が全てつながっていて、閉路を含んでいない
  • 閉路を含まない有向グラフは「DAG(Directed acyclic graph)」という
  • ある頂点を根(Root)としてもつ木を「根付き木」という
    • 2点v,wが辺を持ち、vの方が根に近い場合、vを「親」、wを「子」という
    • 2点v,wについて、根とvとの経路にwが存在する場合、wはvの「先祖」、vはwの「子孫」という
    • 子を持たない頂点を「葉」という
    • 根から各点への経路の長さ(1辺を1とする)を「高さ」という
    • 各点の子の数が常にn子の木を「n分木」という
  • 連結グラフGについて、閉路ができなくなるまで辺を除去し続けると、残ったものは「全域木」となる
  • 根付き木を探索などに用いることで、O(log n)などで高速に処理が行える

木の性質

木Tに頂点がn個あるとすると、

  • 閉路がない
    • 辺を1本でも加えると閉路ができる
  • 連結である
  • 辺の数は(n-1)本
    • (n-1)(n-2)/2+1本以上の辺があればグラフは連結
  • 任意の2点を結ぶ経路は1本のみ
数え上げ
  • (Cayleyの定理)「n点の異なるラベル付き木は、n^(n-2)個」
  • 「完全グラフKnの全域木の総数は、n^(n-2)個」
  • (行列木定理)「連結な単純グラフ(V,E)の全域木の総数は、グラフラプラシアンLの任意の要素に対する余因子に等しい」
    • L(G) = 次数行列D(G) - 隣接行列A(G)

木の探索方法

根付き木の探索を考える。

深さ優先探索(Depth First Search)
  • 全ての頂点を効率的にダブりなくまわる方法
  • 根から扇形に探索を広げる前に、できるだけ深く木に入り込む
    • 再帰的にたどる、stackを使う

以下、巡回方法(簡単のため2分木)

-行きがけ順(pre-order)

再帰的に以下の順番で処理をする

  • 現在のノードの処理
  • 左の子ノードへ移動
  • 右の子ノードへ移動
-通りがけ順(in-order)

再帰的に以下の順番で処理をする

  • 左の子ノードへ移動
  • 現在のノードの処理
  • 右の子ノードへ移動
-帰りがけ順(post-order)

再帰的に以下の順番で処理をする

  • 左の子ノードへ移動
  • 右の子ノードへ移動
  • 現在のノードの処理
幅優先探索(Breadth First Search)
  • 全ての頂点を効率的にだぶりなくまわる方法
  • 根から深く木に入り込む前に、できるだけ扇形に探索を広げる
  • 巡回は「レベル順(level-order)」になる
    • queueを使う
枝狩り
  • あるノードにいて、そのノード以下の探索が必要ないと判断できる場合がある
  • その場合、現在のノード以下の探索をしないことを「枝狩り」という
  • 計算量の見積もりは難しい
Euler tour technique
void dfs(int now_v, int prev_v){
  int a = eulertour.size();
  eulertour.push_back(now_v);
  for(int i=0; i<G[now_v].size(); i++){
    if(i != prev_v){
      dfs(G[now_v][i], now_v);
      eulertour.push_back(now_v);
    }
  }
  int b = eulertour.size();
  //now_vノード以下の部分木はeulertourの[a,b)に含まれる
}

最小全域木(Minumum Spanning Tree)

  • ある無向グラフGについて、全ての頂点が連結な部分グラフで木のものを「全域木」という
  • 辺に重みがあるとき、辺の重みの合計が最小な全域木を「最小全域木」という
Prim法
Kruskal法
  • 最小全域木を求めるアルゴリズム
  • グラフGで重みが一番小さい辺で閉路ができないものを選択し続け、全ての頂点が連結になったら終了する
  • 木だけでなく森でもよい

最小共通祖先(Lowest Common Ancestor)

  • 根付き木で、2つの頂点v,wの共通の祖先で最も近い頂点を「最小共通祖先」という
    • 子孫としてv,w両方を含むノードで一番根から遠いもの
Doubling＋2分探索
  • 各頂点について、その頂点から2^k回親をたどったときのノードを保持しておく(前処理,Doubling)
  • v,wで親が同じ深さになるまで上ってから、上記の情報を使って2分探索で共通ノードを探す
RMQを使う方法
  • euler-tour-techniqueで列にして同時に深さdepthも保持しておき、かつ、最初にノードが現れるindexを保持しておく
  • LCA(v,w) = eulertour[index[v]<=i<=index[w]でdepth[i]が最小となるi]
    • 最小となるiはRMQで求める

空間分割

  • 空間を再帰的に凸集合で分割して表現する手法
  • 2つに分割していく：Binary Space Partitioning(BSP木)
  • 4つに分割していく：四分木
  • 8つに分解していく：八分木
  • その他：KD木、Implicit KD木、VantagePoint木
KD木
  • k次元ユークリッド空間の点を分類する空間分割データ構造
  • BSP木の特殊なケースで、座標軸に垂直な平面のみで(同軸にならないように)分割を行う
    • BSP木と異なり、各ノードに1つの点が対応している
  • 各ノードは、点の情報と、分割平面についての情報を保持する
  • 正しく構築できれば、「ある点集合で点xに一番近いのはどの点か？」という最近傍質問にO(log n)で答えられる
RangeTree(領域木)
  • 各ノードに配列や木構造を持つような木を「領域木」という
    • 例えば、x座標についての２分木で、その各ノードに対応するx座標に対応したy座標を配列や木構造で持つようなもの
  • 長方形空間内に含まれる点群に処理、などが効率的に行える
  • 入れ子を増やせば高次元に拡張できる

探索木

ひも付き２分木
  • 通常の２分木ではn個の頂点に対して、子を指す辺は2本あるので、全体で2*n本ある
  • しかし、葉ノードでは子ノードがないため、辺が余っている
  • この余っている辺を「次に大きい/小さいノード」を指すために使うような２分木を「ひも付き２分木」という
  • 構築時に、子を指すのか、ひもなのかを表すフラグを用意する方法がある
    • フラグを使わないで構築する方法もある
Union-Find木
  • グループ(集合への所属)を管理するデータ構造
    • aとbは同じ集合に含まれるか、など
  • 初期化は、n個のノードを用意する
  • v,wを併合する場合は、vのグループからwへ辺を張る
    • ただし、偏らないように木の高さを保持しておき、併合時に異なる場合は高さが小さいものから大きいものに辺を張る
    • また、辺を根に近くなるように縮約を行うとより高速になる
  • v,wが同じグループに含まれるかを判定する場合は、両ノードの根が等しいかどうかを確認する
  • v,wを分離することはできない
  • http://www.prefield.com/algorithm/container/union_find.html
Segment Tree(区分木)
  • 各頂点が範囲を管理し、各子ノードは親の範囲を半分にした範囲を管理するような完全2分木のデータ構造
  • 各頂点で保持するデータを変えることで様々な機能を実現できる
    • 範囲の最小値を保持→Range Minimum Query
    • 範囲の和を保持→Fenwick Tree(Binary Indexed Tree)
    • など
class SegmentTree {
  int N;
  vector<int> dat;
public:
  SegmentTree(int n_){
    N = 1;
    while(N<n_) N *= 2;
    dat.reserve(2*N);
    for(int i=0; i<2*N; i++) 初期化処理;
  }

  //k番目をaに更新
  void update(int k, int a){
    //葉の更新
    k += N-1;
    dat[k] = a;
    //親を更新していく
    while(k>0){
      k = (k-1)/2;
      //親ノードの更新
      //(子ノードはそれぞれdat[2*k+1],dat[2*k+2])
      //...
    }
  }

  //範囲[s,t)に対する要求処理
  // kは頂点番号、l,rは頂点に対応する範囲
  int query(int s, int t){ return query(s, t, 0, 0, N); }
  int query(int s, int t, int k, int l, int r){
    if(r<=s || t<=1) return 範囲外の時の値; //範囲外のとき
    if(s<=l || r<=t) return 完全範囲内の時の値; //完全に範囲内のとき
    //部分的に範囲内のとき
    int vl = query(s, t, 2*k+1, l, (l+r)/2); //左ノード
    int vr = query(s, t, 2*k+2, (l+r)/2, r); //右ノード
    return 子ノードの値vl,vrについての値;
  }
};
Interval Tree(区間木)
  • 区間を保持するためのデータ構造
  • 区間や点のオーバーラップ(重なり)について探索したい場合に効率的に探索できる
  • Argumented Treeという手法では、普通の２分探索木などを用いる
    • 各ノードは「区間の始点」によってソートされ、各ノードには「区間終点」と「そのノード以下の終点の最大値」を保持する
    • 区間AとBのオーバーラップは「A.start<=B.end && B.start<=A.end」の時なので、それを(効率的に)探せばよい
  • http://ja.wikipedia.org/wiki/%E5%8C%BA%E9%96%93%E6%9C%A8
平衡探索木(Balanced Tree)
  • 普通の探索木では構築時にデータによっては偏りが発生してしまう場合がある
    • 片側だけに子ノードが入り続けている、など
  • 木の高さを自動で調整し、木の高さを低く保つような探索木を「平衡探索木」という
  • 以下のようなものが提案されている
    • AVL木
    • 赤黒木
      • C++STLのset,mapはどちらも赤黒木実装らしいので、使うときはこれらを使えばよさそう
    • Spaly木
    • スケープゴート木
    • Treap
    • AA木
    • B木、B+木、B*木、B^x木
    • 2-3木、2-3-4木
    • など
Link-Cut木(動的木)
Heap
  • 「子の要素は親の要素より常に大きい(小さい)」を満たすようなデータ構造
    • 優先度付きキューとして、集合の最大値(最小値)を順番に取り出せる
  • push操作は、追加する値を葉ノードとして追加し、親ノードと交換を繰り返す
  • pop操作は、根が最大値(最小値)なので、それを取り出し、葉ノードを一つ根に持ってきて、子ノードとの交換を繰り返す
  • C++では、priority_queueがあるので、これを使えばよさそう
  • 二分ヒープの操作が改善されたものとして以下がある
    • 二項ヒープ
    • フィボナッチヒープ
    • Skew Heap
  • http://hos.ac/blog/#blog0001
Trie
SuffixTree
  • 接尾辞(文字列の接尾部分)を木構造で表す
    • ABCという文字列の接尾部分は{ABC,BC,C}
  • 文字列操作が高速に扱える
  • 木を作成せず、接尾辞の開始位置をソートして扱う「SuffixArray」もある
  • http://d.hatena.ne.jp/jetbead/20120104/1325687465
Huffman木
  • ハフマン符号化を行う際に利用される木構造
  • 構築の仕方
    • データの記号とその出現個数を調べる
    • 記号は葉ノードとして表現し、出現個数をその親ノードとする
    • 親ノードをもたないノードについて、一番個数が少ない2つのノードを子にもつ新たなノードを作成し、そこに出現ノードの合計を割り当てる
    • 上記を繰り返し、一つの木を構築する
    • 根から左右に0、1を割当てる
    • 根から記号までに通った0,1の組み合わせがその記号に対応する符号になる
  • http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7
Stern-Brocot木
シュタイナー木
  • 連結グラフGと部分頂点集合Tについて、Tを含む木を「シュタイナー木」という
  • 辺に重みを持つ場合、木の辺の重みの合計が最小となるものを「最小シュタイナー木」という
  • NP困難。動的計画法に基づく方法などが提案されている
  • http://www.prefield.com/algorithm/dp/steiner_tree.html

その他

Gomory-Hu木
  • 重み付き連結グラフGにおいて、重み付き木Tが以下の条件を満たすとき「Gomory-Hu木」という
    • すべてのGの頂点を含む
    • Gの最小カットとTの最小カットが等しい
  • 任意のグラフでGomory-Hu木が存在する
Decomposition

(とりあえず、目についたものだけ列挙)

  • tree Decomposition(木分解)
  • Sqrt Decomposition(平方分割)
  • Centroid Decomposition(重心分解)
  • Heavy-Light Decomposition
  • Ear Decomposition(耳分解)
  • など

参考文献など