木構造 (データ構造)

木構造とは、グラフ理論における木に対応づけられるデータ構造である。

1. 用語
-----

木構造は、一般のグラフ構造と同様の、ノードとノード間を結ぶエッジあるいはリンクで表すこともできるが、木構造専用の、特に有向の根付き木となるような表現が使われることも多い。

データ構造として使われる木は、ほとんどの場合、根となるノードが決められた根付き木である。さらに、有向木であることも多い。

ノード間の関係は家系図に見立てた用語で表現される。木構造内の各ノードは、0個以上の子ノード  を持ち、子ノードは木構造内では下方に存在する。子ノードを持つノードは、子ノードから見れば親ノード  である。あるノードから見て、同じ親を持つノードを兄弟ノード  という。あるノードから見て、その子ノードやそこから先の子ノード全てのいずれかを子孫ノード  と呼び、その親ノードやそこから先の親ノードの全てのいずれかを先祖ノード  と呼ぶ。ノードは高々1個の親ノードを持つ。

根ノード  とは、親ノードを持たないノードのこと。根ノードは木構造の最上位にあるノードであり、1つの木構造に高々1つしか存在しない。根ノードからスタートして、親から子へ、またその子へ、とエッジを辿っていくと、あらゆるノードへ必ず到達でき、そのような経路は常に一意である。図で示す場合、根ノードが一番上に描かれるのが普通である。二分ヒープなどの木構造では、根ノードは特別な属性を持つ。木構造内の全てのノードは、そのノードを頂点とする部分木の根ノードと見なすことができる。

葉ノード  とは、子ノードを持たないノードのこと。葉ノードは木構造の下位の末端にあるノードであり、ひとつの木に複数存在しうる。

内部ノード  とは、子ノードを持つノード、すなわち葉ノード以外のノードのこと。

高さ  とは、あるノードについて、そのノードからその子孫である葉ノードへのエッジ数の最大値のこと。 根ノードの高さはその木構造の高さである。

深さ  とは、逆に、あるノードについて、そのノードから根ノードまでのエッジ数のこと。根ノードの深さは 0 である。

部分木  は、木構造の一部であり、それ自身も完全な木構造となっている部分を指す。木構造 //T// の任意のノードは、その配下の全ノードと共に //T// の部分木を構成する。根ノードを頂点とする部分木は、その木構造全体と等しい。根ノード以外を頂点とする部分木は真部分木  と呼ばれる。

森  とは、木の集合のこと。グラフ理論では、森は閉路をもたないグラフである。 森が順序木の順序集合である場合、これを木の木と考えることで前順、間順、後順の走査法を再帰的に定義できる。

2. 子ノードの順序性
-----------

あるノードの子ノード群の間に順序が存在しない木と、順序が存在する木がある。順序性のある木を実装するには、子ノードをリストに入れたり、各エッジに異なる自然数を付与するなどして子ノード間に順序を入れる。これが順序付き木  である。順序付き木の応用としては2分探索木などがある。コンピュータ中のデータ構造としては、順序が存在しないデータ構造といったものはあまり一般的ではないため、普通の実装では自然に順序付き木となる。

3. 実装方法
-------

コンピュータで利用する場合にはいくつかの実装方法がある。典型的な実装としては、動的メモリ確保でノードを表す構造体の領域を確保し、ポインタで親ノードや子ノードを参照できるようにする。

各ノードが子ノードへのポインタのリストを持つ
各ノードが親ノードへのポインタを持つ
各ノードが親ノードへのポインタと子ノードへのポインタのリストを持つ
各ノードが長男ノードへのポインタと弟ノードへのポインタを持つ他にも、配列を使った実装などがある。

4. 走査法
------

木構造の走査  とは、木構造にある全ノードを一回ずつ体系的に調査する処理である。連結リストや1次元の配列のような線形性のあるデータ構造では、走査は普通は前から順番に行われる。木構造の走査には下記の方法などがある。以下のアルゴリズムは二分木に関するものだが、多分木にも応用可能である。

4.1. 深さ優先探索
-----------

深さ優先探索は、現在のノードを調査し、その子ノードに対して同じことを繰り返す。従って、再帰呼び出しで容易に表現できる。走査法は、ノードを調査する順序によって以下の3つに分類される。

前順・先行順・前置順・行きがけ順 
根ノードを調査する。
もしあれば、左の部分木を前順走査する。
もしあれば、右の部分木を前順走査する。 2分探索木のコピーを作る際によく利用される。また、数式の構文木からポーランド記法の表現を得るのにも利用される。 間順・中間順・通りがけ順 
もしあれば、左の部分木を間順走査する。
根ノードを調査する。
もしあれば、右の部分木を間順走査する。 多分木では定義されない。2分探索木では、間順走査によって走査する順がソートされた順序になるため、よく使われる。 後順・後行順・後置順・帰りがけ順 
もしあれば、左の部分木を後順走査する。
もしあれば、右の部分木を後順走査する。
根ノードを調査する。

4.2. 幅優先探索
----------

レベル順  幅優先探索は、深さが同じノードを浅い方から順に走査していく。

4.3. 走査例
--------



4.4. 擬似コード
----------

前順 n を処理 for each  前順

間順 if  間順 n を処理 if  間順

後順 for each  後順 n を処理

これらの実装では、木構造の高さのぶんだけコールスタック領域を必要とする。平衡が保たれていない木では、これが深刻な問題となる場合もある。各ノードの親ノードの位置を覚えておくことでスタックを使わないようにもできる。

下記はレベル順の擬似コード。 レベル順 n をキューに追加 while  n ← キューから取り出す n を処理 for each  i をキューに追加

4.5. 糸付き2分木
-----------

また、糸付き2分木  を使う方法もある。Joseph M. Morris が1979年に発表した。糸付き2分木は、子ノードがない場合に間順の前と後ろをそれぞれ左の子ポインタと右の子ポインタに設定しておいた木構造である。この場合、子ノードの有無はポインタ以外のフィールドで示す必要がある。これを使うと、間順走査の効率が非常によくなるが、前順や後順は通常のスタックを使った実装の方がよい。糸付き2分木を間順走査するコードは次のようになる。 Sub inorder Do While hasLeftChild Let node ← node.left Loop Do visit If hasRightChild Then Let n ← n.right Do While hasLeftChild Let n ← n.left Loop Else Let n ← n.right End If Loop While n ≠ Null End Sub

5. 主な操作
-------

アイテム数を数え上げる。
あるアイテムを探索する。
新たなアイテムを木構造の特定の位置に追加する。
アイテムを削除する。
部分木を削除する
部分木を追加する
任意のノードから根ノードを探す。

6. 木構造の種類
---------

子ノード数での分類
二分木 - 各ノードが子ノードを最大2つしかもたない木
2分探索木
多分木 - 子ノードを3つ以上持つノードを含む木。二分木でない木
四分木
八分木
平衡木 - すべての葉について、深さがほぼ等しい木
平衡2分探索木 - 平衡木であり、同時に2分探索木でもある木
AA木
AVL木
スケープゴート木
赤黒木
T木 
スプレー木 
Treap
多分木
B木 
B+木、B*木
2-3木、2-3-4木
ヒープ
二分ヒープ
二項ヒープ
フィボナッチヒープ
デジタル木 - 主に文字列の格納のためにつかわれる木
トライ木
パトリシア木
接尾辞木 
その他
領域探索木 
区分木 
区間木 
R木 
kd木

7. コンピュータにみる木構造
---------------

木構造は主に以下のような用途で使われる

階層構造のあるデータを操作する。ディレクトリツリー、ドメイン名、構文木、制御構造、決定木、XML DOMツリーなど。
情報を探索しやすくする。データベースのインデックス など。この用途の木構造を探索木とも呼ぶ。
データのソートのために使用する。ヒープソートなど。

8. 脚注
-----

8.1. 注釈
-------

8.2. 出典
-------

9. 関連項目
-------

バイナリ空間分割 
木 
二分木
DSWアルゴリズム

10. 参考文献
--------

Donald Knuth. //The Art of Computer Programming: Fundamental Algorithms//, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Section 2.3: Trees, pp.308–423.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. //Introduction to Algorithms//, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Section 10.4: Representing rooted trees, pp.214–217. Chapters 12–14 , pp.253–320.
Dale, Nell. Lilly, Susan D. "Pascal Plus Data Structures". D. C. Heath and Company. Lexington, MA. 1995. Fourth Edition.
Drozdek, Adam. "Data Structures and Algorithms in C++". Brook/Cole. Pacific Grove, CA. 2001. Second edition.

11. 外部リンク
---------

[1] from the Dictionary of Algorithms and Data Structures
[2] from LEDA
[3] PHP による走査コード例がある
[4]
[5]
[6]：8.4. Tree Transversal

de:Datenstruktur#Baum