データ構造とアルゴリズム 第7回 木 ～ データ構造（3）～

解答（問1） Push(C,S) Push(A,S) Q 先頭 末尾 A Enq(Pop(S),Q) C S Enq(E,Q) A E A Push(Deq(Q),S) Enq(D,Q) Deq(Q) A A D C D E C S Q S Q x E

解答（問2） 以下の3つの式を，ポーランド記法および逆ポーランド記法で 表現せよ． 中置表現 ポーランド記法 逆ポーランド記法 A + B + C + + A B C A B + C + A * B – C - * A B C A B * C - A * B – C ÷ D + E + - * A B ÷ C D E A B * C D ÷- E +

解説 A + B + C + A B + C A B + + C + + A B C A B + C + 優先度が同じ演算子が複数ある場合は，左から順に処理 A + B + C ポーランド記法 逆ポーランド記法 + A B + C A B + + C + + A B C A B + C + ABC++ではない．ABC++は 中置表現に戻すとA+(B+C) になる

解説 A * B – C÷D + E *AB - ÷CD + E AB* - CD÷ + E - *AB÷CD + E AB* CD÷ - ポーランド記法 逆ポーランド記法 *AB - ÷CD + E AB* - CD÷ + E - *AB÷CD + E AB* CD÷ - + E + - *AB÷CD E AB* CD÷ - E +

ポーランド記法→中置表現 + - *AB ÷CD E A*B C÷D A*B - C÷D A*B - C÷D + E 「演算子　(変数または中置表現の式) (変数または中置表現の式)」 ごとに中置表現に戻していく + - *AB ÷CD E A*B C÷D A*B - C÷D A*B - C÷D + E

逆ポーランド記法→中置表現 A B * C D ÷ - E + A*B C÷D A * B - C ÷ D 「 (変数または中置表現の式) (変数または中置表現の式) 演算子」 ごとに中置表現に戻していく A B * C D ÷ - E + A*B C÷D A * B - C ÷ D A * B - C ÷ D + E

木の走査（tree traversals） ある決まった順番で，木の をもれなくたどること 木の　　　　　ともいう a b f c d e g i h

節点に順序をつける方法 （先行順，前順） ⇒ M - L - R （中間順，間順） ⇒ L - M - R M （後行順，後順） 　　　　　　　　（先行順，前順） preorder traversal ⇒　M - L - R 　　　　　　　　（中間順，間順） inorder traversal ⇒　L - M - R 　　　　　　　　（後行順，後順） postorder traversal ⇒　L – R - M ※　木が空なら，どの順序でも，結果は空 ※　木がひとつの節点だけなら，どの順序でも結果は同じ（節点自身） M L R

木をなぞっていき，各節点に にリストアップする 行きがけ順 部分木T１を行きがけ順走査 部分木T2を行きがけ順に走査 部分木Tkを行きがけ順に走査 木をなぞっていき，各節点に　　　　　　　　　　　　　　にリストアップする n T1 T2 Tk

通りがけ順 部分木T１を通りがけ順に走査 部分木T2を通りがけ順に走査 部分木Tkを通りがけ順に走査 n T1 T2 Tk 木をなぞっていき， に立ち寄ったときに リストアップする 部分木T１を通りがけ順に走査 部分木T2を通りがけ順に走査 部分木Tkを通りがけ順に走査 n T1 T2 Tk

帰りがけ順 部分木T１を帰りがけ順に走査 部分木T2を帰りがけ順に走査 部分木Tkを帰りがけ順に走査 n T1 T2 Tk 木をなぞっていき，各節点に リストアップする 部分木T１を帰りがけ順に走査 部分木T2を帰りがけ順に走査 部分木Tkを帰りがけ順に走査 n T1 T2 Tk

ラベルつきの木 ラベル n1 n2 n3 n4 n5 n6 n7 ＊ + + a b a c ni：節点の名前

ラベルつきの木で数式を表現 ＊ + + a b a c 図は，（a+b）*(a+c)を表現している 葉 ：演算数 内部の節点：演算子 n1 葉　　　　　　：演算数 内部の節点：演算子 n1 n2 n3 n4 n5 n6 n7 ＊ + + a b a c

行きがけ順に走査 n1 n2 n3 n4 n5 n6 n7 ＊ + + a b a c 前置表現 （ポーランド記法） になっている

帰りがけ順に走査 n1 n2 n3 n4 n5 n6 n7 ＊ + + a b a c 後置表現 （逆ポーランド記法） になっている

通りがけ順に走査 n1 n2 n3 n4 n5 n6 n7 ＊ + + a b a c 中置表現

代表的な木構造 二分木 完全二分木 ヒープ 二分探索木 AVL木 B木 完全バランス木 etc… ソーティングアルゴリズム ヒープ　　　　　　　　 二分探索木 AVL木 B木 完全バランス木 etc… ソーティングアルゴリズム などでよく使用される サーチアルゴリズム などでよく使用される

二分木(binary tree) 　(p.46) 各節点が，2個以下の子（節点または葉）をもつ木 n1 n2 n3 n6 n4 n5

完全二分木 葉を除くすべての節点が必ず2個の子をもつ すべての葉の深さが等しい n1 n2 n3 n4 n5 n6 n7 本によって異なる定義をしている場合有 葉を除くすべての節点が必ず2個の子をもつ すべての葉の深さが等しい 高さを k とすると葉の数 L = 2k 節点の総数 P は 　P = 1+21+22+…+2k = 2k+1-1= 2L-1 高さ k は 　k = log2(P + 1)-1 葉以外の節点数Qは 　Q = P – L = 2k -1 枝の総数Hは 　H = P - 1 n1 n2 n3 n4 n5 n6 n7

ヒープ(heap) 10←最大値 7 9 n1> n2, n3 n2> n4, n5 1 5 n1 n2 n3 n4 n5 すべての節点において， 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　が格納される． n1 10←最大値 n2 7 n3 9 n1> n2, n3 n2> n4, n5 n4 1 n5 5

n4<n2<n5<n1< n3 二分探索木　　　　 「　　　　　　　　　　　　　　　　　　　　　　」の関係がある二分木 n1 10 最大値 n2 7 n3 13 最小値 n4 1 n5 8 n4<n2<n5<n1< n3

バランス木(balanced tree, 平衡木) 木の形が変わるとき，すなわち挿入，削除が行われるたびに，木の形を変形させて左右の部分木のバランスがとれるようにした木 バランス木の種類 B木 AVL木 完全バランス木 etc...

B木（B氏木，B-tree） BayerとMcCreightの考案（1972） 根からすべての葉に至る経路長が一定の m分木 m階のB木 条件3：すべての葉までの深さが一定 2階のB木 3階のB木

AVL木 Adel'son-Verl'skii と Landis の考案(1962) すべての節点で，左部分木と右部分木の　　　　　　が高々１しか違わない二分木

完全バランス木 すべての節点で，左部分木と右部分木の　　　　　　　が高々１個しか違わない二分木

木の実現

ラベル付きの木 ラベル 節点番号 (ノード番号) A 1 B 2 C 3 4 5 6 7 F G H 8 9 I J D E

木のデータ構造 I J B C G H D E F A 木を表現するのに必要な事項 節点（および，節点に格納されている情報） 木のデータ構造　　 木を表現するのに必要な事項 節点（および，節点に格納されている情報） 節点のつながり方 8 9 I J 1 2 3 5 6 7 4 B C G H D E F A

親へのポインタによる木の表現 A B C F G D E H I J 1 2 3 4 5 6 7 8 9 P[0] [1] [2] [3] 親へのポインタによる木の表現　 P[0] A B C D E F G H I J -1 1 2 5 根の親は 無いので -1とする [1] A [2] [3] [4] 1 B 2 C [5] [6] 3 4 5 F 6 7 G [7] D E H [8] [9] 8 I 9 J ラベル 親の節点番号 （　情報　） （　つながり方　）

親へのポインタによる木の実現例 struct node { char label; int parent; }; … struct node P[10]; P[0] A B C D E F G H I J -1 1 2 5 [1] [2] [3] [4] [5] [6] [7] [8] [9]

実現例2(typedefを使用した例) typedef struct { char label; int parent; } NODE; … 型に対する別名を宣言する P[0] A B C D E F G H I J -1 1 2 5 [1] [2] 構造体タグはつけてもつけなくても良い typedef struct { char label; int parent; } NODE; … NODE P[10]; [3] [4] [5] [6] [7] [8] 型に対する別名 [9]

長所と短所(親へのポインタによる表現) 長所 短所 表現がコンパクト(領域量の点で有利) 子を見つけるには手間がかかる 節点 i の子を探すには、配列を最初から走査し、P[k] の親の節点番号欄に i が記載されている k を探索する　 ⇒　節点数 V に比例した計算手間　O (V ) 拡張性が低い

子のリストによる木の表現 A B C H F G D E I J 1 2 子が3個 3 4 5 6 7 子が2個 8 9 無駄が多い 子のリストによる木の表現　 A (方法1の例)　　 P[0] A 1 2 -1 [1] B B 3 4 5 1 2 C 子が3個 [2] C 6 7 -1 [3] D -1 -1 -1 3 4 5 H F 6 7 G [4] D E E -1 -1 -1 子が2個 [5] F 8 9 -1 8 I 9 J [6] G -1 -1 -1 [7] H -1 -1 -1 子の数が一定ではない． ⇒どう表わすか？ 方法1) 子の最大個数分，配列を用意する 方法2) 子の連結リストを作る　　 etc… [8] I -1 -1 -1 [9] J -1 -1 -1 無駄が多い

子のリストによる木の表現(方法2) 1 2 3 4 5 6 7 8 9 S[0] [1] [2] [3] [4] [5] [6] 子のリストによる木の表現(方法2) 　 方法2 根 S[0] 1 2 A [1] B 3 4 5 [2] C 6 7 [3] D [4] E [5] F 8 9 [6] G 各節点の子の（連結）リスト 各セルは「子の節点番号」と 「次の子へのポインタ」から成る構造体 [7] H [8] I [9] J 各節点を表わす構造体の配列 1つの節点は，「ラベル」と「子のリストへのポインタ」から成る label header

実現例 struct cell { int child_index; struct cell *next_child; }; 実現例　　 S[0] A 1 2 struct cell { int child_index; struct cell　*next_child; }; struct node { char label; struct cell　*header; … struct node S[10]; [1] B 3 4 5 [2] C 6 7 [3] D next_child　 [4] E [5] F 8 9 [6] G [7] H child_index [8] I [9] J label header

長所と短所(子のリストによる表現) 長所 子節点の探索が容易 短所 (計算手間 O (V) ) 拡張性が低い． 長所と短所(子のリストによる表現)　　　 長所 子節点の探索が容易 短所 　　　　　　　　　　　　　　　　(計算手間　O (V)　) 拡張性が低い． 節点を固定長の配列に連続して格納しているので，配列の要素数を越えて節点を増やせない 複数の木を連結して新しい木を生成することができない．

抽象的な意味でのポインタ＝ 何かを指すもの 長男次弟表現　　　　　 節点のつながり方を「長男へのポインタ」と「弟へのポインタ」の2つの情報で表現 抽象的な意味でのポインタ＝　何かを指すもの 木 T A B C D right_brother leftmost_son E F

長男、次弟を配列のインデクスで指し示している 長男次弟表現による木の表現1 [0] -1 F -1 root [1] [2] A 2 [3] A B C D [4] -1 B 5 [5] C [6] -1 E [7] [8] F -1 D -1 E node 長男、次弟を配列のインデクスで指し示している leftmost_son right_brother cell

注 root [0] [1] [2] 2 [3] [4] [5] [6] [7] [8] cell 4 A -1 F B 5 6 C 8 E D root [1] [2] 2 [3] 節点のデータを配列の任意の位置に置くことが可能 [4] [5] 空いている場所を利用して、複数の木のデータを1つの配列に詰めることができる それらの木を1つに結合したり、分離したりしやすい [6] [7] [8] node leftmost_son right_brother cell

実現例 struct cell { char node; int leftmost_son; int right_brother; }; … -1 F -1 struct cell { char node; int leftmost_son; int right_brother; }; … struct cell T[10]; int root = 2; [1] root 2 [2] 4 A -1 [3] [4] -1 B 5 [5] 6 C 8 [6] -1 E [7] [8] -1 D -1 [9] node leftmost_son right_brother cell

長所と短所(長男次弟表現による表現) 長所 短所 親を調べにくい（⇒親の情報が頻繁に必要であれば、セルの要素に親の位置を加えると良い）

二分木(binary tree) (p.46～) 2 1 3 4 6 5 以下の性質をもつ節点だけから成る木 空の木も二分木 2 1 3 4 6 5 以下の性質をもつ節点だけから成る木 　　　　　　　一つだけもつ 　　　　　　　　　を1つずつもつ 空の木も二分木 左の子（left child）と右の子(right child)を 長男次男表現は、任意の木を2分木を用いて表現したものと考えられる

相異なる二分木 1 2 1 2 3 4 5 3 4 5 6 6

配列による実現 a 1 2 2 1 3 4 6 5 d a b c e f g b 3 -1 c 4 5 d -1 -1 e 6 -1 f left right nodename [0] a 1 2 2 1 3 4 6 5 d a b c e f g [1] b 3 -1 [2] c 4 5 [3] d -1 -1 [4] e 6 -1 [5] f -1 -1 [6] g -1 -1 子は常に２個以下

ポインタによる実現 struct node { nametype nodename; struct node *left; 節点の名前を表す適当なデータ型 例えば char など struct node { nametype 　 nodename; struct node *left; struct node *right; }; … struct node *root;

ポインタによる実現 d a b c e f g a b c d e f g left right nodename root ポインタによる実現　 d a b c e f g left right nodename root node型の構造体 を指すポインタ a b c d e f g node型の構造体