アルゴリズムとデータ構造第14回（最終回）木構造 (tree) 文字列の復習 文字列処理  C言語の文字列 • 文字列とは • 文字列リテラル • 配列による文字列 • ポインタによる文字列  文字列の基本操作 • 文字列の長さ • 文字列からの文字の探索 • 文字列の比較  文字列探索 • 力まかせ法（単純法） • KMP法前回の演習問題第1問第1問の解説と答え A B A D A B D A B C D A A B C A C D A B A D A B D A B C D A A B C A C D A B A D A B D A B C D A A B C A C D - 0 1 0 1 2 0 1 2 0 0 1 1 2 0 1 0 0 第２問第2問木（Tree）情報科学における木根(root) 枝(branch) 葉 leaf 節点(node)  根（root）   根 root  最も上流のノード 1つの木には1つのみ存在葉（leaf）・終端節・外部節   葉(leaf) 最下流のノード非終端節・内部節  葉以外のノード木の再帰的定義 (1) 単一の節点は，それ自身で一つの木 (1)’ 空集合でも木（空の木（null tree）Λ） (2) Ti : 木 ni : 木Tiの根 n : すべてのniの親 n n1 n2 nk T1 T2 Tk 新しい木ができる Tiは新しい木の部分木 nは新しい木の根 (3) すべての木は，(1)をもとに(2)を有限回適用して得られる   右図のような構造をグラフ（graph）という c b 右図は木といえるか？ ⇒いえない．（木の定義をもとに，各自理由を考えてみること） a d e f h g 親子関係親子関係：  a は b, f の親(parent)  b, f は a の子(child) c a a, b, …は各々の nodeの名前 b d f e 部分木（subtree） g h i 兄弟 a 同じ親を持つ節点を兄弟（sibling）という    b と f は兄弟ｃと d と e は兄弟 g と i は兄弟 c b d f e g h i 経路と経路の長さ  ｎ1，ｎ2，・・・，ｎk が木の中の節点の列であって，１≦ｉ＜ｋに対してｎi がｎi+1の親になっているとき，この列のことを「節点ｎ1から節点ｎk への経路 (path)」という．  このとき，経路の長さは k -1  節点自身への経路の長さは０ n1 n2 n3 先祖と子孫  節点ａから節点ｂへの経路があるとき，ａはｂの先祖 (ancestor)，ｂはａの子孫(descendant)であるという a 例   b  f  c d e g h aからhへの経路： a, f, g, h その経路の長さ： 3 ｆの子孫： g, h, i ｃの先祖： a, b i 根（ｒoot） ⇒真の先祖を持たない唯一の節点葉（leaf） ⇒真の子孫を持たない節点深さと高さ  節点の高さ（height）:ある節点から葉への最長経路長  節点の深さ(depth): 根からある節点までの経路の長さ  木の高さ: 木の根の高さ a  節点b b 高さ=１，深さ=１  f 節点g 高さ=１，深さ=2  深さ（レベル）０ c d e g 木の高さ３ h i 順序木と無順序木   順序木（ordered tree）：兄弟間で順序づけを行った木無順序木(unordered tree)：子の順序を無視した木 a b 無順序木としてみれば，同じ木 c c 順序木としてみると，異なる木左： bが兄，cが弟右： cが兄，bが弟 a b 木の探索（走査）（tree traversals）   ある決まった順番で，木のすべての節点をもれなくたどること木のなぞりともいう a b c d f e g h i 節点に順序をつける方法  行きがけ順（先行順，前順） preorder traversal ⇒ M-L-R  inorder traversal ⇒ L-M-R  M 通りがけ順（中間順，間順） L R 帰りがけ順（後行順，後順） postorder traversal ⇒ L–R-M ※ 木が空なら，どの順序でも，結果は空 ※ 木がひとつの節点だけなら，どの順序でも結果は同じ（節点自身）木をなぞっていき，各節点に最初に立ち寄ったときにリストアップする行きがけ順根n ① n 部分木T１を行きがけ順に走査部分木T2を行きがけ順に走査 T1 T2 部分木Tkを行きがけ順に走査 ② ③ 例 Tk A B C D E H A B I D H F J E I K J G L C F K L G 木のデータ構造木を表現するのに必要な事項  節点（および，節点に格納されている情報）  節点のつながり方 0 A 1 B 3 4 D E 2 6 G 5 F 8 I 9 J C 7 H 親へのポインタによる木の表現 0 A 1 B 3 4 D E 2 6 G 5 F 8 I 9 struct node { char label; int parent; }; struct node P[10]; J C 7 H P[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] ラベル（情報） A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 5 J 5 根の親は無いので -1とする親の節点番号（つながり方）長所と短所(親へのポインタによる表現)  長所    表現がコンパクト(領域量の点で有利) 節点の親を一定時間で探せる短所   子を見つけるには手間がかかる節点 i の子を探すには、配列を最初から走査し、P[k] の親の節点番号欄に i が記載されている k を探索する ⇒ 節点数 V に比例した計算手間 O (V ) 拡張性が低い子のリストによる木の表現 0 A (方法1の例) P[0] [1] 2 C B 1 [2] 子が3個 [3] 6 G 7H 3 4 5 F [4] D E 子が2個 [5] 8 I 9 J [6] [7]  子の数が一定ではない． [8] ⇒どう表わすか？方法1) 子の最大個数分，配列を用意する [9] 方法2) 子の連結リストを作る etc… A 1 2 -1 B 3 4 5 C 6 7 -1 D -1 -1 -1 E -1 -1 -1 F 8 9 -1 G -1 -1 -1 H -1 -1 -1 I -1 -1 -1 J -1 -1 -1 無駄が多い子のリストによる木の表現(方法2) 根 S[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] label A B C 1 3 6 2 4 7 8 9 方法2 5 D E F G 各節点の子の（連結）リスト H I 各セルは「子の節点番号」と「次の子へのポインタ」から成る構造体 J 各節点を表わす構造体の配列 header 1つの節点は，「ラベル」と「子のリストへのポインタ」から成る長所と短所(子のリストによる表現) 長所  子節点の探索が容易短所  親を調べにくい(計算手間 O (N) )  拡張性が低い．   節点を固定長の配列に連続して格納しているので，配列の要素数を越えて節点を増やせない複数の木を連結して新しい木を生成することができない．代表的な木構造二分木  完全二分木  ヒープ  二分探索木  AVL木  B木  完全バランス木 etc…  ソーティングアルゴリズムなどでよく使用されるサーチアルゴリズムなどでよく使用される二分木(binary tree) n1 定義：各節点が，2個以下の子（節点または葉）をもつ木  n2 n4     n6 n5 0 以下の性質をもつ節点だけから成る木  子を持たない 1   n3 左の子を一つだけもつ右の子を一つだけもつ左の子，右の子を1つずつもつ 3 2 4 6 空の木も二分木左の子（left child）と右の子(right child)を区別する 5 二分探索木  すべてのノードで   その左部分木のノードのキー値が、そのキー値より小その右部分木のノードのキー値が、そのキー値より大となっている二分木  通りがけ順でなぞると、昇順で値が得られる 10 5 15 4 7 1 1 4 6 5 6 12 9 7 9 11 10 20 14 11 12 14 15 20 二分探索木からのノードの探索  ノードの探索手順  根から探索、探索するキー値と各ノードのキー値を比較探索するキー値の方が小さければ左子ノードと比較  探索するキー値の方が大きければ右子ノードと比較   順次子ノードを探索見つかれば探索成功  見つからずに葉に到達したら探索失敗  ノードの探索：3を探索 5 2 7 1 4 3 3の方が大きい：右へ 3と一致：探索成功 3の方が小さい：左へ二分探索木からのノードの探索  ノードの探索手順  根から探索、探索するキー値と各ノードのキー値を比較探索するキー値の方が小さければ左子ノードと比較  探索するキー値の方が大きければ右子ノードと比較   順次子ノードを探索見つかれば探索成功  見つからずに葉に到達したら探索失敗  ノードの探索：8を探索 5 2 7 1 4 3 8の方が大きい：右へ子ノードなし：探索失敗ノードの挿入  手順  まず、挿入すべきデータと同じキー値を持つノードがあるか探索   すでに同じキー値を持つノードがあったら挿入中止探索失敗箇所にノードを新たに作成し、データ挿入ノードの挿入：1を挿入ノードの挿入：5を挿入ノードの挿入：9を挿入ノードの挿入：3を挿入 6 2 7 1 4 3 9 5 1の方が小さい：左へノードなし：ここへ追加 5の方が小さい：左へ 3の方が小さい：左へ 9の方が大きい：右へ 5の方が大きい：右へ 3の方が大きい：右へまとめ 木の再帰的定義  親子関係兄弟経路と経路の長さ先祖と子孫  順序木と無順序木  木の探索（走査）  行きがけ順  通りがけ順  帰りがけ順  木のデータ構造  親へのポインタによる木の表現  子のリストによる木の表現  木の操作  ノードの探索  ノードの挿入演習問題名前と学籍番号をご記入のうえ、解答用紙（A4）を提出する提出先：工学部電子情報実験研究棟５階 NO.5506室のドアのポストに入れてください締め切り時間：来週月曜日（7月28日）午前９時まで