データ構造とアルゴリズム第7回木～データ構造（3）～ 1 解答（問1） Push(C,S) Push(A,S) Enq(Pop(S),Q) 末尾 A C C C S S S Enq(E,Q) 先頭 A Q A E C S Q Push(Deq(Q),S) Enq(D,Q) A A C S E C Q S E D Q Deq(Q) A D C S Q x E 2 解答（問2）  以下の3つの式を，ポーランド記法および逆ポーランド記法で表現せよ．中置表現ポーランド記法逆ポーランド記法 A+B+C ++ABC AB+C+ A*B–C -*ABC AB*C- A * B – C ÷ D + E + - * A B ÷ C D E A B * C D ÷- E + 3 解説  優先度が同じ演算子が複数ある場合は，左から順に処理 A+B+C ポーランド記法 +AB 逆ポーランド記法 +C ++ABC AB+ +C AB+C+ ABC++ではない．ABC++は中置表現に戻すとA+(B+C) になる 4 解説ポーランド記法 A * B – C÷D + E *AB - ÷CD + E 逆ポーランド記法 AB* - CD÷ + E - *AB÷CD + E AB* CD÷ - + E + - *AB÷CD E AB* CD÷ - E + 5 ポーランド記法→中置表現  「演算子 (変数または中置表現の式) (変数または中置表現の式)」ごとに中置表現に戻していく + - *AB ÷CD E A*B C÷D A*B - C÷D A*B - C÷D + E 6 逆ポーランド記法→中置表現  「 (変数または中置表現の式) (変数または中置表現の式) 演算子」ごとに中置表現に戻していく AB* CD÷ - E+ A*B C÷D A*B - C÷D A*B - C÷D+E 7 木の走査（tree traversals）   ある決まった順番で，木のをもれなくたどること木のともいう a b c d f e g i h 8 節点に順序をつける方法（先行順，前順）  preorder traversal ⇒ M-L-R M （中間順，間順）  inorder traversal ⇒ L-M-R L R （後行順，後順）  postorder traversal ⇒ L–R-M ※ 木が空なら，どの順序でも，結果は空 ※ 木がひとつの節点だけなら，どの順序でも結果は同じ（節点自身） 9 行きがけ順木をなぞっていき，各節点ににリストアップする部分木T１を行きがけ順走査部分木T2を行きがけ順に走査 n 部分木Tkを行きがけ順に走査 T1 T2 Tk 10 通りがけ順木をなぞっていき，部分木T１を通りがけ順に走査に立ち寄ったときにリストアップする部分木T2を通りがけ順に走査 n 部分木Tkを通りがけ順に走査 T1 T2 Tk 11 帰りがけ順部分木T１を帰りがけ順に走査木をなぞっていき，各節点に部分木T2を帰りがけ順に走査リストアップする部分木Tkを帰りがけ順に走査 n T1 T2 Tk 12 ラベルつきの木ラベル n1 n2 n4 a ＊ + n5 n3 b n6 a + n7 c ni：節点の名前 13 ラベルつきの木で数式を表現    図は，（a+b）*(a+c)を表現している葉：演算数内部の節点：演算子 n2 n4 a n1 ＊ + n5 n3 b n6 a + n7 c 14 行きがけ順に走査 n1 n2 n4 a ＊ + n5 n3 b n6 a + n7 c 前置表現（ポーランド記法）になっている 15 帰りがけ順に走査 n1 n2 n4 a ＊ + n5 n3 b n6 a + n7 c 後置表現（逆ポーランド記法）になっている 16 通りがけ順に走査 n1 n2 n4 a ＊ + n5 n3 b n6 a + n7 c 中置表現 17 代表的な木構造二分木  完全二分木  ヒープ  二分探索木  AVL木  B木  完全バランス木 etc…  ソーティングアルゴリズムなどでよく使用されるサーチアルゴリズムなどでよく使用される 18 二分木(binary tree)  (p.46) 各節点が，2個以下の子（節点または葉）をもつ木 n1 n2 n4 n3 n5 n6 19 完全二分木   本によって異なる定義をしている場合有葉を除くすべての節点が必ず2個の子をもつすべての葉の深さが等しい高さを k とすると葉の数 L = 2k  節点の総数 P は P = 1+21+22+…+2k = 2k+1-1= 2L-1  高さ k は k = log2(P + 1)-1 n2  葉以外の節点数Qは Q = P – L = 2k -1  枝の総数Hは n4 n5 H=P-1  n1 n3 n6 n7 20 ヒープ(heap)  すべての節点において，が格納される． n1 n2 n4 1 7 n5 10←最大値 n3 5 9 n1> n2, n3 n2> n4, n5 21 二分探索木  「二分木」の関係がある n1 n2 最小値 n4 1 7 n5 10 n3 最大値 13 8 n4<n2<n5<n1< n3 22 バランス木(balanced tree, 平衡木)  木の形が変わるとき，すなわち挿入，削除が行われるたびに，木の形を変形させて左右の部分木のバランスがとれるようにした木バランス木の種類  B木  AVL木  完全バランス木 etc... 23 B木（B氏木，B-tree）    BayerとMcCreightの考案（1972）根からすべての葉に至る経路長が一定の m分木 m階のB木    条件1：根は，葉であるか，2 ～ m 個の子を持つ条件2：根，葉以外は， m / 2 ～ m 個の子を持つ条件3：すべての葉までの深さが一定 2階のB木 3階のB木 24 AVL木   Adel'son-Verl'skii と Landis の考案(1962) すべての節点で，左部分木と右部分木のが高々１しか違わない二分木 25 完全バランス木  すべての節点で，左部分木と右部分木のが高々１個しか違わない二分木 26 木の実現 27 ラベル付きの木節点番号 (ノード番号) 0 1 3 4 D E 8 ラベル A B 2 6 5 F I 9 G C 7 H J 28 木のデータ構造木を表現するのに必要な事項  節点（および，節点に格納されている情報）  節点のつながり方 0 A 1 B 3 4 D E 2 6 G 5 F 8 I 9 J C 7 H 29 親へのポインタによる木の表現  0 A 1 B 3 4 D E 2 6 G 5 F 8 I 9 J P[0] [1] [2] [3] [4] C [5] [6] 7 [7] H [8] [9] ラベル（情報） A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 5 J 5 根の親は無いので -1とする親の節点番号（つながり方） 30 親へのポインタによる木の実現例 struct node { char label; int parent; }; … struct node P[10]; 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 31 実現例2(typedefを使用した例) typedef宣言型に対する別名を宣言する typedef struct { char label; int parent; } NODE; … NODE P[10]; 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 32 長所と短所(親へのポインタによる表現)  長所  表現がコンパクト(領域量の点で有利)   短所   子を見つけるには手間がかかる節点 i の子を探すには、配列を最初から走査し、P[k] の親の節点番号欄に i が記載されている k を探索する ⇒ 節点数 V に比例した計算手間 O (V ) 拡張性が低い 33 子のリストによる木の表現 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 無駄が多い34 子のリストによる木の表現(方法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つの節点は，「ラベル」と「子のリストへのポインタ」から成る 35 実現例 struct cell { int child_index; struct cell *next_child; }; struct node { char label; struct cell *header; }; … S[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C 1 3 6 D 5 next_child E F 2 4 7 8 9 G H I child_index J label header struct node S[10]; 36 長所と短所(子のリストによる表現) 長所  子節点の探索が容易短所 (計算手間 O (V) )   拡張性が低い．   節点を固定長の配列に連続して格納しているので，配列の要素数を越えて節点を増やせない複数の木を連結して新しい木を生成することができない． 37 長男次弟表現  節点のつながり方を「長男へのポインタ」と「弟へのポインタ」の2つの情報で表現抽象的な意味でのポインタ＝何かを指すもの木T A B leftmost_son C E F D right_brother 38 長男次弟表現による木の表現1 root 2 A B C E D F 長男、次弟を配列のインデクスで指し示している [0] [1] [2] [3] [4] [5] [6] [7] [8] -1 F -1 A -1 B 5 C -1 E 0 -1 D -1 leftmost_son node cell right_brother 39 注 root 2 節点のデータを配列の任意の位置に置くことが可能 • 空いている場所を利用して、複数の木のデータを1つの配列に詰めることができる • それらの木を1つに結合したり、分離したりしやすい [0] [1] [2] [3] [4] [5] [6] [7] [8] -1 F -1 4 A -1 -1 B 5 6 C 8 -1 E 0 -1 D -1 node leftmost_son right_brother cell 40 実現例 struct cell { char node; int leftmost_son; int right_brother; }; … struct cell T[10]; int root = 2; root 2 T[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] -1 F -1 4 A -1 -1 B 5 6 C 8 -1 E 0 -1 D -1 leftmost_son node right_brother cell 41 長所と短所(長男次弟表現による表現) 長所  短所  親を調べにくい（⇒親の情報が頻繁に必要であれば、セルの要素に親の位置を加えると良い） 42 二分木(binary tree)      0 以下の性質をもつ節点だけから成る木  1   (p.46～) 一つだけもつ一つだけもつを1つずつもつ 3 2 4 5 6 空の木も二分木左の子（left child）と右の子(right child)を長男次男表現は、任意の木を2分木を用いて表現したものと考えられる 43 相異なる二分木 0 1 3 2 4 6 0 1 5 3 2 5 4 6 44 配列による実現 left 0 a 1 b 3 d 2 c 4 e 6 g 5 f right nodename [0] a 1 2 [1] b 3 -1 [2] c 4 5 [3] d -1 -1 [4] e 6 -1 [5] f -1 -1 [6] g -1 -1 子は常に２個以下 45 ポインタによる実現 struct node { nametype nodename; struct node *left; struct node *right; }; 節点の名前を表す適当なデータ型例えば char など … struct node *root; 46 ポインタによる実現 left nodename root a right b d a node型の構造体を指すポインタ c e f g b c d node型の構造体 e f g 47