計数工学プログラミング演習 ( 第 6 回 ) 2016/05/24 DEPARTMENT OF MATHEMATICAL INFORMATICS 1
今日の内容 : 再帰呼び出し 2 分探索木 深さ優先探索 課題 : 2 分探索木を用いたソート 2
再帰呼び出し 関数が, 自分自身を呼び出すこと (recursive call, recursion) 再帰を使ってアルゴリズムを設計すると, 簡単になることが多い 関数内部で宣言される変数は,CPU のスタック上に確保される int factorial(int n) int x; if (n == 0) return 1; x = factorial(n-1); return n * x; 3
2 分探索木とは何か? 各節点は key, left, right, parent フィールドを持つ 2 分探索木条件 (binary-search-tree property) 節点 y が x の左部分木に属する key[y] key[x] 節点 y が x の右部分木に属する key[x] key[y] 2 5 3 7 3 5 7 8 2 5 8 5 4
2 分探索木の構造体 typedef struct node struct node *left; // 左の子へのポインタ struct node *right; // 右の子へのポインタ struct node *parent; // 親へのポインタ searchkey_t key; // 探索に使うキー value_t value; // 付属値 node; typedef struct node *root; // 根節点のポインタ tree; 5
2 分探索木に対する質問操作 質問操作は高さに比例した時間で終了する 探索 : 2 分探索木の中から, ある与えられたキーを持つ節点のポインタを求める ( 存在しなければ NULL) node *tree_search(node *x, searchkey_t k) if (x == NULL k == x->key) return x; if (k < x->key) return tree_search(x->left,k); else return tree_search(x->right,k); 6
探索の正当性 キー k が見つかったら探索を終了する k が key(x) より小さい場合 2 分探索木条件より,k は x の右部分木にはない 左部分木に対して探索を続行する k が key(x) より大きい場合 右部分木に対して探索を続行する 探索する節点は根からのパスになる 実行時間は O(h) (h: 木の高さ ) 7
この場合の再帰は while ループにできる node *tree_search(tree *T, searchkey_t k) node *x; x = T->root; // 根ノード while (x!= NULL && k!= x->key) if (k < x->key) x = x->left; else x = x->right; return x; 8
今回はキーは文字列なので単純に比較できない key_cmp(x, y) 以下の値を返す関数とする x == y なら 0 x < y なら負の値 x > y なら正の値 node *tree_search(tree *T, searchkey_t k) node *x; x = T->root; // 根ノード while (x!= NULL && key_cmp(k, x->key)!= 0) if (key_cmp(k, x->key) < 0) x = x->left; else x = x->right; return x; 9
挿入と削除 要素を挿入 / 削除したあとも2 分探索木条件が満たされる必要がある 挿入は比較的簡単 削除は複雑 どちらも O(h) 時間 今回は削除は扱わない 10
挿入 5 z 6 3 7 y tree_insert(tree *T, node *z) x 2 5 z 6 8 node *x, *y; y = NULL; x = root(t); while (x!= NULL) // z を挿入する場所 x を決める y = x; if (key(z) < key(x)) x = left(x); 挿入場所は必ず葉 else x = right(x); // y は x の親 parent(z) = y; // z の親を y にする if (y == NULL) root(t) = z; // T が空なら z が根節点 else if (key(z) < key(y)) left(y) = z; // y の子を z にする else right(y) = z; 11
深さ優先探索, 幅優先探索 木やグラフの探索法 深さ優先探索 (depth-first search, DFS) 行き止まりになるまで先に進む 幅優先探索 (breadth-first search, BFS) 全体を同時に探索する DFSはスタック ( 再帰 ),BFSはキューで実現できる 1 2 5 1 2 3 3 4 6 4 5 6 DFS BFS 12
木の中間順巡回 木の中間順巡回 ( 通りがけ順, inorder tree walk) 根の左部分木に出現するキー集合 根のキー 右部分木に出現するキー集合の順にキーを出力 木の根から辿ると, 全てのキーをソートされた順序で出力できる この再帰は while ループにできない inorder_tree_walk(node *x) if (x!= NIL) inorder_tree_walk(left(x)); print(key(x)); inorder_tree_walk(right(x)); 2 5 3 13 THE 5UNIVERSITY OF TOKYO 2 5 3 5 7 7 8 8
void inorder_tree_walk(node *x) if (x!= NULL) inorder_tree_walk(x->left); printf("%s %s n",x->key, x->value); inorder_tree_walk(x->right); 14
その他の巡回法 先行順巡回 ( 行きがけ順, preorder tree walk): 根節点を先に出力し, 次に左右の部分木を出力 後行順巡回 ( 帰りがけ順, postorder tree walk): 先に左右の部分木を出力し, 最後に根節点を出力 PREORDER_TREE_WALK(node x) if (x!= NIL) print(key(x)); PREORDER_TREE_WALK(left(x)); PREORDER_TREE_WALK(right(x)); POSTORDER_TREE_WALK(node x) if (x!= NIL) POSTORDER_TREE_WALK(left(x)); POSTORDER_TREE_WALK(right(x)); print(key(x)); 15
課題 :2 分探索木を用いたソート 入力 : 標準入力から英単語と和訳のペアの集合を読み込む 出力 : 標準出力に, 単語のペアを英単語の辞書順に並べたものを出す int main(int argc, char *argv[]) tree *T; node *x; char buf1[100], buf2[100]; char *eng, *jpn; T = allocate_tree(); while (1) if (scanf(" %s %s", buf1, buf2) < 2) break; eng = strdup(buf1); jpn = strdup(buf2); x = allocate_node(eng, jpn); tree_insert(t, x); inorder_tree_walk(t->root); free_tree(t); return 0; 16
提出するソースコードの中に, 学生証番号, 氏名, メールアドレスをコメントとして書いておく 締切 : 2016 年 5 月 17 日 ( 火 ) 17:35 ( 演習終了時 ) 17
作成する関数 node *allocate_node(char *eng, char *jpn) 英語と日本語の文字列を持つノードを作る tree *allocate_tree(void) 空の木 T を作る (T-root == NULL) void tree_insert(tree *T, node *z) 木にノードを挿入 void inorder_tree_walk(node *x) 18