すのふら

すのふら

日々の備忘録

木構造について調べる

相変わらずwikipediaをメインに調べていく。

木構造(きこうぞう)とは、グラフ理論の木の構造をしたデータ構造のこと。

木構造 (データ構造) - Wikipedia

親に子供がぶら下がっている構造のこと。
f:id:snofra:20180905161535p:plain
こんな感じで親に当たる根ノードとその子供である葉ノードに分別できる。
深さをカウントするときは根ノードよりも下をカウントする。


木構造なぜやるのか、木構造によって何が幸せかというと、データを取得するときに効率よく取得できるということ。
HDDのデータを取得するのも木構造(B+Tree)で、データ探索の効率がよいから。
*1

この動画みたいに何通りあるのかの処理の実行に260億年とかかけられると非常に困るわけで。
www.youtube.com

それを効率よくデータを取得しようという考えがあって、アルゴリズムのひとつとして木構造が存在するということ。


木構造の走査法

木構造を処理するとしたときに実行方法(走査法)はいくつか存在している。主に2つ。


深さ優先探索

簡単に言うと、

  1. 根ノードから葉ノードまでの1ルート、分岐気にせず全部見る。※左側から順番に見る
  2. 末端までたどり着いたら、末端の直前の分岐まで戻ってまだ行っていないルートを末端まで行ってみる。
  3. それを繰り返す。

そんな感じ。

俺が一番しっくり来たのはノベルゲームのルートをいったん全部やってED見た後、行っていない選択肢選びつづけてルート制覇する感じ。

この探索方法も3つある。

  • 前順・先行順・前置順・行きがけ順
  • 間順・中間順・通りがけ順
  • 後順・後行順・後置順・帰りがけ順


前順・先行順・前置順・行きがけ順

上で書いた内容の通り順番に実行する。
f:id:snofra:20180905163651p:plain


間順・中間順・通りがけ順

木の左側の末端の葉ノードから走査する。
ABCFのような節になっているところは、上から下とのきにカウントするのではなく、下から上になったときにカウントする。
※B→Fのときに1ではなく、I→Fのときに1カウントする
f:id:snofra:20180905163706p:plain


後順・後行順・後置順・帰りがけ順

前順・先行順・前置順・行きがけ順の逆版みたいなイメージ。
この場合も木の左側の末端の葉ノードから走査する。
f:id:snofra:20180905163734p:plain


幅優先探索

深さが同じノードを浅い方から順に走査していく。
f:id:snofra:20180905163915p:plain

木構造の種類

二分探索木とかAVL木は以下動画がわかりやすくておすすめ。
www.nicovideo.jp

B-Treeは上の動画のAVL木を少し変えたもの。
何が変わっているのかっていうと、多分木であるのでその要素が違う。
多分木って何かっていうと、ひとつの親にぶら下がれる子供が複数件OKってだけ。

二分探索木やAVL木はそもそもそものルール上、ひとつの親にぶら下がれる子供が2つのみ。

じゃあなぜAVL木ではなくB-Treeをつかうのか。

B-treeとは、1つのノードがm個 (m>=2) の子ノードを持つことができる平衡木構造のことです。

なぜAVL木だと問題があるかというと、大規模なデータを補助記憶装置(ハードディスクなど)へ格納し検索する場合、コンピュータの処理に時間がかかってしまうためです。
ハードディスクは主記憶装置に比べ、アクセス時間が非常に長く、そのためハードディスクを効率的に扱うには、なるべくブロックの読み取り回数を少なくする必要があります。

ブロックの読み取り回数は木の深さになります。
AVL木の場合、log n 回なのに対して、B-treeの場合、log n / log m 回 (※計算は省略) になります。そのためmが大きくなるほど、処理時間に差が出てきます。
このことから、MySQLではインデックスのデータ構造にB-treeが採用されているようです。

B-treeインデックス入門


そのほか参考サイト

http://www-ikn.ist.hokudai.ac.jp/~arim/pub/algo/algo6.pdf

木構造<ハードウェアとソフトウェア<Web教材<木暮仁

https://wa3.i-3-i.info/word14397.html

よく分からない深さ優先探索