木構造

導入

ちょっと情報処理試験を受けようという話になりまして、木構造ってなんだっけ？ということで少しまとめてみました。

木構造

木構造とは

下記のようなデータ構造を言います。

      [1]
　 　／　＼
　 [2]　　[3]
　／　＼　　　＼
[4]　　[5]　　[6]

[1]～[6]は分岐箇所を示し、[ノード(節)]と呼びます。
[1]は木構造の始端で[ルート(根)]と呼びます。
[4]～[6]は木構造の終端で[リーフ(葉)]と呼びます。
／のようにノード間をつなぐ線はブランチ(枝)と呼びます。
図示すると下記になります。

       　　　　[ルート(根)]
　　　　　　　　／　　　　＼　←ブランチ(枝)
　　　　[ノード(節)]　　[ノード(節)]
　　　　／　　　　＼　　　　　　　＼
[リーフ(葉)]　　[リーフ(葉)]　　[リーフ(葉)]

※ルートもリーフも特別に名前がついているだけでノードの一種です。

なぜか、上から下へ広がる図で書くことが多いのに「木」なんですよね。
「根」なんじゃないかと思ったりもします。

分岐数や段数に特に縛りはありません。
一方向に分裂していけば木構造です。たぶん。

2分木とは

よく使われる木構造です。
分岐数が2以下の木構造です。
最初に示した下記の図も2分木になっています。

      [1]
　 　／　＼
　 [2]　　[3]
　／　＼　　　＼
[4]　　[5]　　[6]

完全2分木(Complete Binary Tree)

最も深いリーフとそれ以外のリーフの深さの差が1以下の2分木のことです。
ちなみにリーフ以外のすべてのノードが2つの子を持ち
すべてのリーフの深さが等しい2分木を完全2分木(Full Binary Tree)と言います。

最初に示した下記の図はComplete Binary Treeですが、Full Binary Treeではありません。

      [1]
　 　／　＼
　 [2]　　[3]
　／　＼　　　＼
[4]　　[5]　　[6]

下記はComplete Binary TreeかつFull Binary Treeです。

      [1]
     ／ ＼
  [2]    [3]
 ／ ＼   ／ ＼
[4] [5] [6] [7]

通常、完全2分木といえばComplete Binary Treeを指しますので
Full Binary Treeはあまり気にする必要はありません。

ヒープ(半順序木)

ヒープ(heap)とは[親ノード] ≧ [子ノード]もしくは[親ノード] ≦ [子ノード]という法則にしたがう木構造です。
通常は、上記の法則にしたがう完全2分木のことをヒープと言います。

直系の親子関係にないノード間は特に制限はありません。
[親ノード] ≦ [子ノード]という関係にある場合、下記の図では
[1] ≦ [3] ≦ [6]なので、[1] ≦ [6]という関係は成り立ちますが、
[2] ≦ [6]という関係は成り立ちません。

      [1]
　 　／　＼
　 [2]　　[3]
　／　＼　　　＼
[4]　　[5]　　[6]

ヒープは優先度付きキュー(priority queue)やヒープソートの実装などに使われます。

2分探索木

[右の子ノード] < [親ノード] < [左の子ノード]という一定の法則に従っているものです。

2分探索木の場合下記の木構造では[4] < [2] < [5] < [1] < [3] < [6]となります。

      [1]
　 　／　＼
　 [2]　　[3]
　／　＼　　　＼
[4]　　[5]　　[6]

2分探索木はその名の通り2分探索に使われます。

AVL木

完全2分木の2分探索木をAVL木と呼びます。
通常の2分探索木は深さ制限がないため、下記のような構造となることもあります。

         [1]
        ／
      [2]
     ／ ＼
   [3]   [4]
  ／ ＼
[5]   [6]

この場合[6]のノードを探索するには[1]->[2]->[3]->[6]と4つのノードをたどることになります。
一方下記のAVL木の場合は[1]->[3]->[6]と3つのノードをたどることで探索が完了します。

      [1]
　 　／　＼
　 [2]　　[3]
　／　＼　　　＼
[4]　　[5]　　[6]

この差はノード数が多くなるにつれ開いていきます。
100ノードの場合、2分探索木では最大100ノードたどる必要がありますが、
AVL木では最大7ノードたどれば見つかります。

B木

B木はAVL木の多分岐の木へ一般化した木構造です。
最大分岐数をオーダーと呼びます。

メモリ読み出しはページ(4KBなど)単位に行われます。
メモリ読み出しの回数を減らすために各ノードをページサイズに対して最適化します。

仮に子ノードへのポインタ以外に各ノードが96バイトの領域を持ち、子ノードへのポインタが8バイトとします。
ノードのサイズを4KBにする場合は子ノードを500個とします。
（つまりオーダー500）

ノードの総数が1億とすると、
・オーダー2(=AVK木)の場合、深さ27。
・オーダー500の場合、深さ3。

最悪ケースでは、AVL木では27回メモリ読み出しが発生するのに対して
B木(オーダー500)では3回のメモリ読み出しで済む。
メモリ読み出しがボトルネックになる場合には、有利に働きます。

DBのインデックス検索などに使用されます。

B+木

B木の改良版(亜種)の木構造です。
B木との違いは以下の通りです。

• レコードはすべてリーフに格納される。
• 各リーフは前後のノードへのポインタを持つことが多い。
  つまり、リーフは連結リストになっている。
• 各ノードには子ノード数の上限/下限が設定される。

B木に対して優位なのは、範囲取得が強いことです。
B木というか2分木は、リーフ以外もレコードを持つため途中で
該当レコードを見つけることがありレスポンスが早いという利点があります。

B+木の場合は、必ずリーフまで検索が必要ということはありますが、
リーフがリスト構造になっているため、リーフのみを辿っていくことで範囲取得が実現できます。
（B木の場合は、ノードを子ノード->親ノード->子ノード->・・・と辿っていくため、
　次のノードを判定する処理が追加で必要です。）

他にB*木やB#木というB木の改良版(亜種)もあるようです。

関係DBのインデックス検索などに使用されます。

走査

深さ優先順

子があれば子を優先して、縦に走査を行います。
下記の図の場合は、[1]->[2]->[4]->[5]->[3]->[6]のように走査を行います。

      [1]
　 　／　＼
　 [2]　　[3]
　／　＼　　　＼
[4]　　[5]　　[6]

幅優先順

同じ深さのノードを優先して、横に走査を行います。
下記の図の場合は、[1]->[2]->[3]->[4]->[5]->[6]のように走査を行います。

先行順(行きがけ順)

中間ノード->左側の木->右側の木の順に走査を行います。
下記の図の場合は、[1]->[2]->[4]->[5]->[3]->[6]のように走査を行います。

      [1]
　 　／　＼
　 [2]　　[3]
　／　＼　　　＼
[4]　　[5]　　[6]

中間順(通りがけ順)

左側の木->中間ノード->右側の木の順に走査を行います。
下記の図の場合は、[4]->[2]->[5]->[1]->[3]->[6]のように走査を行います。

      [1]
　 　／　＼
　 [2]　　[3]
　／　＼　　　＼
[4]　　[5]　　[6]

後行順(帰りがけ順)

左側の木->右側の木->中間ノードの順に走査を行います。
下記の図の場合は、[4]->[5]->[2]->[6]->[3]->[1]のように走査を行います。

      [1]
　 　／　＼
　 [2]　　[3]
　／　＼　　　＼
[4]　　[5]　　[6]