木構造 (データ構造)

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索
ファイル:Tree structure(data) 01.png
親子構造

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

ノード

木構造は、ノード（節点、頂点）とノード間を結ぶエッジ（枝、辺）あるいはリンクで表される。

データ構造として使われる木は、ほとんどの場合、根となるノードが決められた根付き木で、ノード間の関係は家系図に見立てた用語で表現される。木構造内の各ノードは、0個以上の子ノード (child node) を持ち、子ノードは木構造内では下方に存在する（木構造の成長方向は下とするのが一般的である）。子ノードを持つノードは、子ノードから見れば親ノード (parent node) である。あるノードから見て、同じ親を持つノードを兄弟ノード (sibling node) という。あるノードから見て、その子ノードやそこから先の子ノード全てのいずれかを子孫ノード (descendant node) と呼び、その親ノードやそこから先の親ノードの全てのいずれかを先祖ノード (ancestor node) と呼ぶ。ノードは高々1つの親ノードを持つ。

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

子ノードを持たないノードを葉ノード (leaf node) と呼ぶ。葉ノードは木構造の下位の末端にあるノードであり、1つの木に複数存在しうる。

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

あるノードについて、そのノードからその子孫である葉ノードへのエッジ数の最大値を、そのノードの「高さ」という。 根ノードの「高さ」はその木構造の「高さ」である。逆に、あるノードについて、そのノードから根ノードまでのエッジ数を、そのノードの「深さ」という。根ノードの深さは 0 である。

部分木

部分木 (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分探索木 この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) と呼ぶ。グラフ理論では、森とは閉路をもたない（連結とは限らない）グラフである。

森が順序木の順序集合である場合、これを木の木と考えることで前順、間順、後順の走査法を再帰的に定義できる。

木構造の種類

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

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

関連項目

参考文献

  • 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.

外部リンク

テンプレート:データ構造 テンプレート:木構造 (データ構造)de:Datenstruktur#Baum

「http://wikippe.e-do-match.com/index.php?title=木構造_(データ構造)&oldid=9690」から取得