木構造 (データ構造)

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

目次 1 ノード 1.1 根ノード 1.2 葉ノード 1.3 内部ノード 2 部分木 3 木構造における順序性 4 実装方法 4.1 グラフとしての木構造 5 走査法 5.1 例 5.2 実装例 6 主な操作 7 森 8 木構造の種類 9 コンピュータにみる木構造 10 関連項目 11 参考文献 12 外部リンク

[編集] ノード

木構造は、ノード（節点、頂点）とノード間を結ぶエッジ（枝、辺）あるいはリンクで表される。ノードには何らかのデータ（値、条件、別のデータ構造、別の木構造）が付属している。木構造内の各ノードは、0個以上の子ノード（child nodes）を持ち、子ノードは木構造内では下方に存在する（木構造の成長方向は下とするのが一般的である）。子ノードを持つノードは、子ノードから見れば親ノード（parent node）である。同じ親を持つノード同士を兄弟という。ノードは高々1つの親ノードを持つ。最底辺の子ノードから、あるノードまでのエッジ数を、そのノードの「高さ」という。（後述する）根ノードの「高さ」は、木構造の「高さ」である。逆に根ノードから最底辺に向かってのエッジ数を「深さ」という。

[編集] 根ノード

木構造の頂点にあるノードを根ノード（root node）と呼ぶ。頂点にあるため、根ノードは親ノードを持たない。木構造に対する各種操作は、一般に根ノードを出発点とする（アルゴリズムによっては、葉ノードから開始して根ノードに到達して完了するものもある）。他のノードにはエッジあるいはリンクを辿ることで必ず到達できる。形式的定義では、そのような（根から特定ノードまでの）経路は常に一意である。図で示す場合、根ノードが一番上に描かれるのが普通である。ヒープなどの木構造では、根ノードは特別な属性を持つ。木構造内の全てのノードは、そのノードを頂点とする部分木の根ノードと見なすことができる。

[編集] 葉ノード

木構造の最底辺にあるノードを葉ノード（leaf node）と呼ぶ。最底辺にあるため、葉ノードは子ノードを持たない。

[編集] 内部ノード

内部ノード（internal node、inner node）は、子ノードを持つノード、すなわち葉ノード以外のノードを意味する。

[編集] 部分木

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

[編集] 木構造における順序性

木構造は2種類に分類される。順序性のない木と、順序性のある木である。順序性のない木は、構造的には木だが、あるノードの子ノード群には順序が存在しない。順序性のある木では、各エッジ（枝）に異なる自然数を付与するなどして子ノード間に順序性が存在する。これを順序木（ordered tree）と呼ぶ。一般に実際に使われるデータ構造としては順序木の方が典型的である。2分探索木は順序木の一種である。

[編集] 実装方法

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

• 各ノードが子ノードへのポインタのリストを持つ
• 各ノードが親ノードへのポインタを持つ
• 各ノードが親ノードへのポインタと子ノードへのポインタのリストを持つ
• 各ノードが長男ノードへのポインタと弟ノードへのポインタを持つ

他にも、配列を使った実装（ポインタではなく、インデックスによって親子関係が決定される）などがある（例えば、二分ヒープ）。

[編集] グラフとしての木構造

グラフ理論では、木とは非環状（ループを持たない）グラフを意味する。根付き木は、根として選ばれたノードを持つグラフである。この場合、エッジでつながれた2つのノードには親子関係が成り立つ。

[編集] 走査法

木構造の走査（traversal）とは、木構造にある全ノードを一回ずつ体系的に調査する処理である。以下のアルゴリズムは二分木に関するものだが、他の木構造にも応用可能である。連結リストや1次元の配列のような線形性のあるデータ構造では、走査は順番に行われるだけで、論理的には一種類しかない。しかし、木構造の走査にはいくつかの方法がある。一般に、現在のノードを調査し、その子ノードに対して同じことを繰り返す。従って、再帰呼び出しで容易に表現できる（ループでも実装可能）。走査法は、ノードを調査する順序によって以下の3つに分類される（いずれの方法も、根から探索を開始する）。

前順・先行順・前置順 (preorder)

1. 根ノードを調査する。
2. もしあれば、左の部分木を前順走査する。
3. もしあれば、右の部分木を前順走査する。

これは、深さ優先探索とも呼ばれる。2分探索木のコピーを作る際によく利用される。また、数式の構文木からポーランド記法の表現を得るのにも利用される。

間順・中間順 (inorder)

1. もしあれば、左の部分木を間順走査する。
2. 根ノードを調査する。
3. もしあれば、右の部分木を間順走査する。

2分探索木では、間順走査によって走査する順がソートされた順序になるため、よく使われる。

後順・後行順・後置順 (postorder)

1. もしあれば、左の部分木を後順走査する。
2. もしあれば、右の部分木を後順走査する。
3. 根ノードを走査する。

これらとは別にレベル順の走査もある。この場合、「深さ」のレベルが同じノードを浅い方から順に走査していく。これは、幅優先探索とも呼ばれる。

[編集] 例

この2分探索木において、 前順走査での調査順: F, B, A, D, C, E, G, I, H 間順走査での調査順: A, B, C, D, E, F, G, H, I 2分探索木での間順走査は、ソートされた順となる。 後順走査での調査順: A, C, E, D, B, H, I, G, F レベル順走査での調査順: F, B, G, A, D, I, C, E, H

[編集] 実装例

preorder(node)
  print node.value
  if node.left  ≠ null then preorder(node.left)
  if node.right ≠ null then preorder(node.right)
inorder(node)
  if node.left  ≠ null then inorder(node.left)
  print node.value
  if node.right ≠ null then inorder(node.right)
postorder(node)
  if node.left  ≠ null then postorder(node.left)
  if node.right ≠ null then postorder(node.right)
  print node.value

これらの実装では、木構造の高さのぶんだけコールスタック領域を必要とする。平衡が保たれていない木では、これが深刻な問題となる場合もある。各ノードの親ノードの位置を覚えておくことでスタックを使わないようにもできる。また、糸付き2分木を使う方法もある。糸付き2分木は、子ノードがない場合に間順の前と後ろをそれぞれ左の子ポインタと右の子ポインタに設定しておいた木構造である。この場合、子ノードの有無はポインタ以外のフィールドで示す必要がある。これを使うと、間順走査の効率が非常によくなるが、前順や後順は通常のスタックを使った実装の方がよい。

糸付き2分木を間順走査するコードは次のようになる。

inorder(node)
  while hasleftchild(node) do
    node = node.left
  do
    visit(node)
    if (hasrightchild(node)) then
      node = node.right
      while hasleftchild(node) do
        node = node.left
    else
      node = node.right
  while node ≠ null

[編集] 主な操作

• アイテム（データを持つノード）数を数え上げる。
• あるアイテムを探索する。
• 新たなアイテムを木構造の特定の位置に追加する。
• アイテムを削除する。
• 部分木を削除する（枝狩り）
• 部分木を追加する（接ぎ木）
• 任意のノードから根ノードを探す。

[編集] 森

森（forest）とは、順序木の順序集合である。森における前順、間順、後順の走査法は、これを木構造の木構造と考えることで再帰的に定義できる。

[編集] 木構造の種類

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

[編集] コンピュータにみる木構造

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

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

[編集] 関連項目

• バイナリ空間分割 (BSP)
• 木 (数学)
• DSWアルゴリズム

[編集] 参考文献

• 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 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), 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.

[編集] 外部リンク

• Description from the Dictionary of Algorithms and Data Structures
• STL-like C++ tree class
• List of data structures from LEDA
• NGenerics : implementation in C#
• The Adjacency List Model for Processing Trees with SQL
• Storing Hierarchical Data in a Database PHP による走査コード例がある
• Managing Hierarchical Data in MySQL
• Working with Graphs in MySQL
• N-ary Tree Traversal
• Animation Applet of Binary Tree Traversal
• http://www.math.northwestern.edu/~mlerma/courses/cs310-05s/notes/dm-treetran