親子 おやこ 構造 こうぞう
木 き 構造 こうぞう (きこうぞう)とは、グラフ理論 りろん における木 き に対応 たいおう づけられるデータ構造 こうぞう である。
木 き 構造 こうぞう は、一般 いっぱん のグラフ構造 こうぞう と同様 どうよう の、ノード(節点 せってん 、頂点 ちょうてん )とノード間 あいだ を結 むす ぶエッジ(枝 えだ 、辺 あたり )あるいはリンクで表 あらわ すこともできるが、木 き 構造 こうぞう 専用 せんよう の、特 とく に有向 ゆうこう の根付 ねつ き木 き となるような表現 ひょうげん が使 つか われることも多 おお い。
データ構造 こうぞう として使 つか われる木 き は、ほとんどの場合 ばあい 、根 ね となるノードが決 き められた根付 ねつ き木 き である。さらに、有向 ゆうこう 木 き であることも多 おお い。[ 注 ちゅう 1]
ノード間 あいだ の関係 かんけい は家系 かけい 図 ず に見立 みた てた用語 ようご で表現 ひょうげん される。木 き 構造 こうぞう 内 ない の各 かく ノードは、0個 こ 以上 いじょう の子 こ ノード (英 えい : child node ) を持 も ち、子 こ ノードは木 き 構造 こうぞう 内 ない では下方 かほう に存在 そんざい する(木 き 構造 こうぞう の成長 せいちょう 方向 ほうこう は下 した とするのが一般 いっぱん 的 てき である)。子 こ ノードを持 も つノードは、子 こ ノードから見 み れば親 しん ノード (英 えい : parent node ) である。あるノードから見 み て、同 おな じ親 おや を持 も つノードを兄弟 きょうだい ノード (英 えい : sibling node ) という。あるノードから見 み て、その子 こ ノードやそこから先 さき の子 こ ノード全 すべ てのいずれかを子孫 しそん ノード (英 えい : descendant node ) と呼 よ び、その親 おや ノードやそこから先 さき の親 しん ノードの全 すべ てのいずれかを先祖 せんぞ ノード (英 えい : ancestor node ) と呼 よ ぶ。ノードは高々 たかだか 1個 いっこ の親 しん ノードを持 も つ。
根 ね ノード (英 えい : root node ) とは、親 おや ノードを持 も たないノードのこと。根 ね ノードは木 き 構造 こうぞう の最 さい 上位 じょうい にあるノードであり、1つの木 き 構造 こうぞう に高々 たかだか 1つしか存在 そんざい しない。根 ね ノードからスタートして、親 おや から子 こ へ、またその子 こ へ、とエッジを辿 たど っていくと、あらゆるノードへ必 かなら ず到達 とうたつ でき、そのような(根 ね から特定 とくてい ノードまでの)経路 けいろ は常 つね に一意 いちい である。図 ず で示 しめ す場合 ばあい 、根 ね ノードが一番 いちばん 上 じょう に描 えが かれるのが普通 ふつう である。二分 にぶん ヒープ などの木 き 構造 こうぞう では、根 ね ノードは特別 とくべつ な属性 ぞくせい を持 も つ。木 き 構造 こうぞう 内 ない の全 すべ てのノードは、そのノードを頂点 ちょうてん とする部分 ぶぶん 木 き の根 ね ノードと見 み なすことができる。
葉 は ノード (英 えい : leaf node ) とは、子 こ ノードを持 も たないノードのこと。葉 は ノードは木 き 構造 こうぞう の下位 かい の末端 まったん にあるノードであり、ひとつの木 き に複数 ふくすう 存在 そんざい しうる。
内部 ないぶ ノード (英 えい : internal node 、inner node ) とは、子 こ ノードを持 も つノード、すなわち葉 は ノード以外 いがい のノードのこと。
高 たか さ (英 えい : height ) とは、あるノードについて、そのノードからその子孫 しそん である葉 は ノードへのエッジ数 すう の最大 さいだい 値 ち のこと。
根 ね ノードの高 たか さはその木 き 構造 こうぞう の高 たか さである。
深 ふか さ (英 えい : depth ) とは、逆 ぎゃく に、あるノードについて、そのノードから根 ね ノードまでのエッジ数 すう のこと。根 ね ノードの深 ふか さは 0 である。
部分 ぶぶん 木 き (英 えい : subtree ) は、木 き 構造 こうぞう の一部 いちぶ であり、それ自身 じしん も完全 かんぜん な木 き 構造 こうぞう となっている部分 ぶぶん を指 さ す。木 き 構造 こうぞう T の任意 にんい のノードは、その配下 はいか の全 ぜん ノードと共 とも に T の部分 ぶぶん 木 き を構成 こうせい する。根 ね ノードを頂点 ちょうてん とする部分 ぶぶん 木 き は、その木 き 構造 こうぞう 全体 ぜんたい と等 ひと しい。根 ね ノード以外 いがい を頂点 ちょうてん とする部分 ぶぶん 木 き は真部 まなべ 分木 ぶんき (英 えい : proper subtree ) と呼 よ ばれる(部分 ぶぶん 集合 しゅうごう と真 ま 部分 ぶぶん 集合 しゅうごう とのアナロジー)。
森 もり (英 えい : forest ) とは、木 き の集合 しゅうごう のこと。グラフ理論 りろん では、森 もり は閉路 へいろ をもたない(連結 れんけつ とは限 かぎ らない)グラフである。
森 もり が順序 じゅんじょ 木 き の順序 じゅんじょ 集合 しゅうごう である場合 ばあい 、これを木 き の木 き と考 かんが えることで前 ぜん 順 じゅん 、間 あいだ 順 じゅん 、後 こう 順 じゅん の走査 そうさ 法 ほう を再帰 さいき 的 てき に定義 ていぎ できる。
あるノードの子 こ ノード群 ぐん の間 あいだ に順序 じゅんじょ が存在 そんざい しない木 き と、順序 じゅんじょ が存在 そんざい する木 き がある。順序 じゅんじょ 性 せい のある木 き を実装 じっそう するには、子 こ ノードをリスト に入 い れたり、各 かく エッジ(枝 えだ )に異 こと なる自然 しぜん 数 すう を付与 ふよ するなどして子 こ ノード間 あいだ に順序 じゅんじょ を入 い れる。これが順序 じゅんじょ 付 つ き木 き (英 えい : ordered tree ) である。順序 じゅんじょ 付 つ き木 き の応用 おうよう としては2分 ふん 探索 たんさく 木 き などがある。コンピュータ中 ちゅう のデータ構造 こうぞう としては、順序 じゅんじょ が存在 そんざい しないデータ構造 こうぞう といったものは(セット型 がた のように存在 そんざい はするが)あまり一般 いっぱん 的 てき ではないため、普通 ふつう の実装 じっそう では自然 しぜん に順序 じゅんじょ 付 つ き木 き となる。
コンピュータ で利用 りよう する場合 ばあい にはいくつかの実装 じっそう 方法 ほうほう がある。典型 てんけい 的 てき な実装 じっそう としては、動的 どうてき メモリ確保 かくほ でノードを表 あらわ す構造 こうぞう 体 たい の領域 りょういき を確保 かくほ し、ポインタ で親 しん ノードや子 こ ノードを参照 さんしょう できるようにする。
各 かく ノードが子 こ ノードへのポインタのリストを持 も つ
各 かく ノードが親 しん ノードへのポインタを持 も つ
各 かく ノードが親 しん ノードへのポインタと子 こ ノードへのポインタのリストを持 も つ
各 かく ノードが長男 ちょうなん ノードへのポインタと弟 おとうと ノードへのポインタを持 も つ
他 ほか にも、配列 はいれつ を使 つか った実装 じっそう (ポインタではなく、インデックスによって親子 おやこ 関係 かんけい が決定 けってい される)などがある(例 たと えば、二分 にぶん ヒープ )。
前 ぜん 順 じゅん : F, B, A, D, C, E, G, I, H
間 あいだ 順 じゅん : A, B, C, D, E, F, G, H, I
後 こう 順 じゅん : A, C, E, D, B, H, I, G, F
レベル順 じゅん : F, B, G, A, D, I, C, E, H
木 き 構造 こうぞう の走査 そうさ (英 えい : traverse ) とは、木 き 構造 こうぞう にある全 ぜん ノードを一 いち 回 かい ずつ体系 たいけい 的 てき に調査 ちょうさ する処理 しょり である。連結 れんけつ リスト や1次元 じげん の配列 はいれつ のような線形 せんけい 性 せい のあるデータ構造 こうぞう では、走査 そうさ は普通 ふつう は前 まえ から順番 じゅんばん に行 おこな われる(後 うし ろからたどる方法 ほうほう などもある)。木 き 構造 こうぞう の走査 そうさ には下記 かき の方法 ほうほう などがある。以下 いか のアルゴリズムは二 に 分木 ぶんぎ に関 かん するものだが、多分 たぶん 木 き にも応用 おうよう 可能 かのう である。
深 ふか さ優先 ゆうせん 探索 たんさく は、現在 げんざい のノードを調査 ちょうさ し、その子 こ ノードに対 たい して同 おな じことを繰 く り返 かえ す。従 したが って、再帰 さいき 呼 よ び出 だ し で容易 ようい に表現 ひょうげん できる(ループ でも実装 じっそう 可能 かのう )。走査 そうさ 法 ほう は、ノードを調査 ちょうさ する順序 じゅんじょ によって以下 いか の3つに分類 ぶんるい される(いずれの方法 ほうほう も、根 ね から探索 たんさく を開始 かいし する)。
前 ぜん 順 じゅん ・先行 せんこう 順 じゅん ・前 ぜん 置 おけ 順 じゅん ・行 い きがけ順 じゅん (英 えい : pre-order )
根 ね ノードを調査 ちょうさ する。
もしあれば、左 ひだり の部分 ぶぶん 木 き を前 まえ 順 じゅん 走査 そうさ する。
もしあれば、右 みぎ の部分 ぶぶん 木 き を前 まえ 順 じゅん 走査 そうさ する。
2分 ふん 探索 たんさく 木 き のコピーを作 つく る際 さい によく利用 りよう される。また、数式 すうしき の構文 こうぶん 木 き からポーランド記法 きほう の表現 ひょうげん を得 え るのにも利用 りよう される。
間 あいだ 順 じゅん ・中間 なかま 順 じゅん ・通 とお りがけ順 じゅん (英 えい : in-order )
もしあれば、左 ひだり の部分 ぶぶん 木 き を間 あいだ 順 じゅん 走査 そうさ する。
根 ね ノードを調査 ちょうさ する。
もしあれば、右 みぎ の部分 ぶぶん 木 き を間 あいだ 順 じゅん 走査 そうさ する。
多分 たぶん 木 き では定義 ていぎ されない。2分 ふん 探索 たんさく 木 き では、間 あいだ 順 じゅん 走査 そうさ によって走査 そうさ する順 じゅん がソートされた順序 じゅんじょ になるため、よく使 つか われる。
後 こう 順 じゅん ・後 こう 行 くだり 順 じゅん ・後 ご 置 おけ 順 じゅん ・帰 かえ りがけ順 じゅん (英 えい : post-order )
もしあれば、左 ひだり の部分 ぶぶん 木 き を後 こう 順 じゅん 走査 そうさ する。
もしあれば、右 みぎ の部分 ぶぶん 木 き を後 こう 順 じゅん 走査 そうさ する。
根 ね ノードを調査 ちょうさ する。
レベル順 じゅん (英 えい : level-order )
幅優先 はばゆうせん 探索 たんさく は、深 ふか さが同 おな じノードを浅 あさ い方 ほう から順 じゅん に走査 そうさ していく。
この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
前 ぜん 順 じゅん (n )
n を処理 しょり
for each (n の子 こ ノード i)
前 ぜん 順 じゅん (i)
間 あいだ 順 じゅん (n )
if (n に左 ひだり の子 こ ノードがあれば)
間 あいだ 順 じゅん (n の左 ひだり の子 こ ノード)
n を処理 しょり
if (n に右 みぎ の子 こ ノードがあれば)
間 あいだ 順 じゅん (n の右 みぎ の子 こ ノード)
後 こう 順 じゅん (n )
for each (n の子 こ ノード i)
後 ご 順 じゅん (i)
n を処理 しょり
これらの実装 じっそう では、木 き 構造 こうぞう の高 たか さのぶんだけコールスタック 領域 りょういき を必要 ひつよう とする。平衡 へいこう が保 たも たれていない木 き では、これが深刻 しんこく な問題 もんだい となる場合 ばあい もある。各 かく ノードの親 しん ノードの位置 いち を覚 おぼ えておくことでスタックを使 つか わないようにもできる。
下記 かき はレベル順 じゅん の擬似 ぎじ コード。
レベル順 じゅん (n )
n をキューに追加 ついか
while (キューに要素 ようそ を含 ふく むなら)
n ← キューから取 と り出 だ す
n を処理 しょり
for each (n の子 こ ノード i)
i をキューに追加 ついか
糸 いと 付 つ き2分木 ぶんぎ
また、糸 いと 付 つ き2分木 ぶんぎ (英語 えいご 版 ばん ) (英 えい : threaded binary tree ) を使 つか う方法 ほうほう もある。Joseph M. Morris が1979年 ねん に発表 はっぴょう した[ 1] 。糸 いと 付 つ き2分木 ぶんぎ は、子 こ ノードがない場合 ばあい に間 あいだ 順 じゅん の前 まえ と後 うし ろをそれぞれ左 ひだり の子 こ ポインタと右 みぎ の子 こ ポインタに設定 せってい しておいた木 き 構造 こうぞう である。この場合 ばあい 、子 こ ノードの有無 うむ はポインタ以外 いがい のフィールドで示 しめ す必要 ひつよう がある。これを使 つか うと、間 あいだ 順 じゅん 走査 そうさ の効率 こうりつ が非常 ひじょう によくなるが、前 ぜん 順 じゅん や後 こう 順 じゅん は通常 つうじょう のスタックを使 つか った実装 じっそう の方 ほう がよい。
糸 いと 付 つ き2分木 ぶんぎ を間 あいだ 順 じゅん 走査 そうさ するコードは次 つぎ のようになる。
Sub inorder(n∈node)
Do While hasLeftChild(n)
Let node ← node.left
Loop
Do
visit(n)
If hasRightChild(n) Then
Let n ← n.right
Do While hasLeftChild(n)
Let n ← n.left
Loop
Else
Let n ← n.right
End If
Loop While n ≠ Null
End Sub
アイテム(データを持 も つノード)数 すう を数 かぞ え上 あ げる。
あるアイテムを探索 たんさく する。
新 あら たなアイテムを木 き 構造 こうぞう の特定 とくてい の位置 いち に追加 ついか する。
アイテムを削除 さくじょ する。
部分 ぶぶん 木 き を削除 さくじょ する(枝 えだ 刈 が り)
部分 ぶぶん 木 き を追加 ついか する(接 つ ぎ木 き )
任意 にんい のノードから根 ね ノードを探 さが す。
子 こ ノード数 すう での分類 ぶんるい
二 に 分木 ぶんぎ - 各 かく ノードが子 こ ノードを最大 さいだい 2つしかもたない木 き
多分 たぶん 木 き - 子 こ ノードを3つ以上 いじょう 持 も つノードを含 ふく む木 き 。二 に 分木 ぶんぎ でない木 き
平衡 へいこう 木 き (バランス木 き ) - すべての葉 は について、深 ふか さがほぼ等 ひと しい木 き
ヒープ
デジタル木 き - 主 おも に文字 もじ 列 れつ の格納 かくのう のためにつかわれる木 き
その他 た
木 き 構造 こうぞう は主 おも に以下 いか のような用途 ようと で使 つか われる
^ 一般 いっぱん に無 む 向 こう 木 き は、それに含 ふく まれる任意 にんい のノードを根 ね として解釈 かいしゃく 可能 かのう な非 ひ 根付 ねつ き木 き である。有向 ゆうこう 木 き は、エッジが、葉 は から根 ね に向 む かう向 む きの場合 ばあい と、根 ね から葉 は に向 むか う向 む きの場合 ばあい があるが、いずれにしても根 ね となるノードが決 き められた根付 ねつ き木 き となる。
^ Morris, Joseph M. (December 1979). “Traversing binary trees simply and cheaply”. Information Processing Letters 9 (5): 197-200. doi :10.1016/0020-0190(79)90068-1 .
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.