第11回
知識(履歴)の蓄積

例題

情報処理演習II

例題１．二分木二分木の定義 二分木の１つの節を，構造体 node 型として定義する– node 型は，left，right の２つの属性から構成

node 構造体を定義している
node 型

枝節

leftright（実行結果は出ない）

二分木の例

node 構造体

node 構造体名前

構造体の名前(define-struct node(left right))(define-struct node (left right))
make-node : (tree tree -> node) コンストラクタ
node-left : (node -> tree)

属性の並び（それぞれの属性にも名前がある）

属性の並び

node-right : (node -> tree)

セレクタ

node? : (anything -> boolean) node 構造体かを調べる(注) コンストラクタ，セレクタで「tree」とあるのは，二分木のこと（次ページ参照）

1

二分木(binary tree)
二分木（binary tree）の再帰的定義
1. empty (再帰的定義の基底)
2. 部分木を持つ節を表す node 構造体(make-node tleft tright)
tleft ・・・ 左の部分木
tright ・・・ 右の部分木

実習

empty の場合empty
対応
左の部分木も右の部分木も無いような二分木（中身が無い二分木）(make-nodeemptyempty)(make-nodeempty(make-nodeemptyempty))

DrScheme の使用

実習の進め方 資料を見ながら、「実習」を行ってみる

 DrScheme の起動

プログラム → PLT Scheme → DrScheme その後、各自「課題」に挑戦する– 各自で自習 ＋ 巡回指導
– 遠慮なく質問してください 今日の実習では「Intermediate Student」に設定Language→ Choose Language 自分のペースで先に進んで構いません→ Intermediate Student→ OK ボタン

DrScheme の使用 / ステップ実行

実習１. 二分木の高さ

 プログラム実行の振る舞いを観察するツール

二分木の高さを求める関数 height を定義し，実行する 「定義用ウインドウ」のみを使用（通常の実行と異なる）
 「Intermediate Student」に設定する必要あり
Language→ Choose Language

高さ： ０→ Intermediate Student→ Run ボタンempty

高さ： ２(make-nodeempty(make-nodeemptyempty))

2

「実習１．二分木の高さ」の手順

二分木の高さの実行例

1. 次を「定義用ウインドウ」で，実行しなさい• 入力した後に，Run ボタンを押す(define-struct node(left right));; height : tree -> number;; measure the height of a tree abt(define (height abt)
(cond[(empty? abt) 0][else (+ 1(max (height (node-left abt))(height (node-right abt))))]))
2. その後，次を「実行用ウインドウ」で実行しなさい(height empty)(height (make-nodeempty(make-nodeemptyempty)))height 関数

二分木の高さ1.

入力 abt が empty ならば： → 終了条件
→ 自明な解0
2.

そうで無ければ：– 右の部分木と、左の部分木の高さを求め、大きいほうに１を加える;; height : tree -> number;; measure the height of a tree abt(define (height abt)
(cond終了条件
自明な解[(empty? abt) 0][else (+ 1(max (height (node-left abt))(height (node-right abt))))]))

height の内部に height (再帰による繰り返し)
左の部分木の高さは０(empty なので）右の部分木の高さは１

実習２. アキュムレータスタイル
二分木の高さを求める関数 height を，今度は，アキュムレータスタイル(accumulator style)で定義し，実行する

高さ： ０

empty

高さ： ２

(make-nodeempty(make-nodeemptyempty))

実習２の手順1. 次を「定義用ウインドウ」で，実行しなさい• 入力した後に，Run ボタンを押す(define-struct node(left right));; height : tree -> number;; measure the height of a tree abt0
(define (height abt0)(local (;;accum represents how many nodes height-a;;has encountered on its way to abt from abt0
(define (height-a abt accum)(cond[(empty? abt) accum][else (max (height-a (node-left abt)(+ accum 1))(height-a (node-right abt)(+ accum 1)))])))(height-a abt0 0)))3

実習２の手順

実習２の実行例

2. その後，次を「実行用ウインドウ」で実行しなさい(height empty)(height (make-nodeempty(make-nodeemptyempty)))

二分木の高さ1.

入力 abt が empty ならば： → 終了条件
現在のアキュムレータの値2.

→ 自明な解そうで無ければ：– 「アキュムレータの値」に１を加えて，右の部分木、左の部分木の高さを求める．
* アキュムレータには，現在計算中の木の高さが入る

height 関数;; height : tree -> number;; measure the height of a tree abt(define (height abt0)(local (;;accum represents how many nodes height-a;;has encountered on its way to abt from abt0
(define (height-a abt accum)(cond 終了条件
自明な解[(empty? abt) accum][else (max (height-a (node-left abt)(+ accum 1))(height-a (node-right abt)(+ accum 1)))])))(height-a abt0 0)))

左右の部分木の高さの大きい方を選択(max演算を使う)

課題１．二分探索木
 次ページ以降で説明する二分探索木（binarysearch tree) についての問題

課題– ここで説明している二分探索木は，数値属性をキーとする二分探索木である– 数値による探索を行う関数 search を説明している– この search 関数を，文字列データについて動くよ
うに書き換えなさい4

二分探索木(binary search tree)

二分探索木のための valnode 構造体

 二分木(binary tree)の一種
 データの配置に規則あり– 左の部分木の節に含まれるデータは，自分より小さい– 右の部分木の節に含まれるデータは，自分より大きい(define-struct(define-struct valnodevalnode(value(value leftleft right))right))

value データの探索のためのデータ構造

leftright

35
21

二分探索木の例

46134061
69

枝枝

value

valueleftright

二分探索木の節 二分探索木の節 (node) を，valnode 構造体として定義する
名前(define-struct valnode(value left right))

leftright

二分探索木の例(make-valnode 35(make-valnode 21(make-valnode 13 empty empty)
empty)(make-valnode 46(make-valnode 40 empty empty)(make-valnode 61empty
35(make-valnode 69 empty empty))))21134640

上の Scheme 式が表現する
二分探索木

61

属性の並び

（それぞれの属性にも名前がある）

二分探索木による探索
 根(root)から始める
 探索キーの値と，各節点のデータを比較し，目標となるデータを探す– 探索キーよりも節点のデータが小さいときは，右側の子をたどる

69

二分探索木による探索の例(例） 40である節点を探す場合
1. 根の値(35)と，探索キー(40)を比較
2. 探索キーの方が大きいので，右側の子節点へ移る
3. 次に移った節点の値(46)と探索キー(40)を比較し4. 探索キーの方が小さいので，左の子節点へ移る
5. 次に移った節点(40)が，目標の節点である– 探索キーよりも節点のデータが大きいときは，左側の子をたどる

352113464061695

二分探索木による探索

二分探索木による探索実行例(define-struct valnode(value left right))(define (search x a-tree)(cond[(empty? a-tree) false][(< x (valnode-value a-tree))(search x (valnode-left a-tree))][(< (valnode-value a-tree) x)(search x (valnode-right a-tree))][else true]))

課題２．二分探索木

課題２．二分探索木

 次ページ以降で説明するように，二分探索木

 次のデータについての二分探索木を作り，関の節 (node) を，今度は，次のように定義する

数 search-bt の実行結果を報告しなさい(define-struct node (sn pn left right))
node 型

snpn

数値（シリアル番号）

leftreight

左の部分木

シンボル
右の部分木

sn をキーとする• 左の部分木の節に含まれる sn は，自分より小さい• 右の部分木の節に含まれる sn は，自分より大きい

課題２での二本探索木の節の構造体定義(define-struct node (sn pn left right))

63'A

29'B

89'C

15'D

77'E

95'F

二分探索木への節の挿入
二分探索木に節を挿入する関数add-node(add-node bt (list 89 'J));; add-node : node (listof number symbol) -> node(define (add-node bt alosp)(cond[(empty? bt)(make-node (first alosp) (first (rest alosp))
empty empty)]
[else
(cond
[(= (node-sn bt) (first sp)) bt][(> (node-sn bt) (first sp))
(make-node (node-sn bt) (node-pn bt)(add-node (node-left bt) alosp)(node-right bt))][else(node-left(make-node (node-sn bt) (node-pn bt)(node-left bt)(add-node (node-right bt) alosp))])]))

bt

課題２での，二分探索木の再帰的定義
1. empty (再帰的定義の基底)
2. 部分木を持つ節を表す node 構造体(make-node sn pn tleft tright)
tleft ・・・ 左の部分木, tright ・・・ 右の部分木
sn ・・・ 数値, pn ・・・ シンボルempty (make-node
63 'A empty empty)(make-node
63 'A(make-node
29 'B empty(make-node
89 'Cempty empty))
empty)

63 ‘A

29 ‘B

36 ‘Jbt)(add-node (node-right bt) (list 89 'J))

6

二分探索木への節の一括挿入;;create-bt : node(lof (lof number symbol))->node(define (create-btree bt lof-alosp)(cond[(empty? lof-alosp) bt][else(create-btree(add-node bt (first lof-alosp))(rest lof-alosp))]))(define lof-alosp(list (list 63 'A)(list 29 'B)(list 89 'C)(list 15 'D)(list 77 'E)(list 95 'F)(list 10 'G)(list 24 'H)(list 99 'I)(list 36 'J)(list 21 'K)(list 22 'L)(list 88 'M)(list 90 'N)(list 100 'O)(list 76 'P)(list 35 'Q)(list 3 'R)))

課題３．二分探索木のグラフィックス表示
 次ページ以降で説明する draw-tree 関数を使って，課題２の二分探索木をグラフィックス表示しなさいdraw-tree
0y1

a-posn1=(x1,y1)
x2 x1;; 節を描く
draw-node : node posn -> boolean
y2a-node;;(define (draw-node a-node a-posn) …);;枝(branch)を描く
a-posn2=(x2,y2)
draw-line : node posn posn -> true;;(define (draw-line a-node a-posn1 a-posn2) … )節と枝を描く;; draw-node-and-branches : node posn number -> true;; (define (draw-node-and-branches node a-posn width) .. )左右の節の位置を求める;; get-next-left-posn : posn number -> posn;;(define (get-next-left-posn a-posn width) .. );; get-next-right-posn : posn number -> posn;;(define (get-next-right-posn a-posn width) .. )二分探索木の探索(define lof-alosp;;search-bt : node number->symbol(list (list 63 'A)(define (search-bt bt sn)(list 29 'B)(list 89 'C)(cond(list 15 'D)[(empty? bt) 'none](list 77 'E)[else(list 95 'F)(cond(list 10 'G)[(= sn (node-sn bt))(node-pn bt)]
(list 24 'H)[(< sn (node-sn bt))
(list 99 'I)(search-bt (node-left bt) sn)](list 36 'J)[else (search-bt (node-right bt) sn)])]))(list 21 'K)(list 22 'L)(list 88 'M);; test(list 90 'N)>(define bt (create-bt empty(list 100 'O)
lof-alosp))(list 76 'P)>(search-bt bt 77)(list 35 'Q)'E(list 3 'R)))

木を描く
初期設定;; set a canvas size
(define WIDTH 700) (define HEIGHT 730);; set disk radius and color(define d-radius 5) ;; a disk radius(define d-color ‘red) ;; a disk color(define l-color ‘blue) ;; a line color;; set root position(define TopMargine 30) ;; top margin(define Root-Pos (make-posn (/ WIDTH 2)(+ d-radious TopMargine)));;(define bt (create-btree empty lof-alosp)) ;; create a binary tree
(start WIDTH HEIGHT);; create a canvas(draw-tree bt Root-Pos);; draw a binary tree(stop);; end節(node)を描く;; draw-node : node posn -> boolean;; draw a disk and a string at a-posn position Nodeの番号を表示．
(define (draw-node a-node a-posn)
その際，文字(and列に変換(draw-solid-disk a-posn d-radius d-color)(draw-solid-string a-posn(number->string (node-sn a-node)))));; test(start WIDTH HEIGHT)(draw-node (make-node 63 ‘A empty empty)(make-posn 350 20))7

親子間の枝(branch)を描く

a-posn1=(x1,y1)
x2 x1y1y2;; draw-line : node posn posn -> truea-node(define l-color ‘blue) ;; a line color(define (draw-line a-node a-posn1 a-posn2) a-posn2=(x2,y2)(cond;; if a-node is empty, the branch will not be drawn.
[(empty? a-node) true][else(draw-solid-line a-posn1 a-posn2 l-color)]));;test(draw-line (make-node 29 ‘B emtpy empty)(make-posn 350 20) (make-posn 120 30))

節と枝を描く(define Interval-Time 0.1) ;; 0.1秒次の実行を待つ;; draw-node-and-branches : node posn number -> true
(define (draw-node-and-branches node a-posn width)(andwidth node a-posn;; draw node
(draw-node node a-posn)(sleep-for-a-while Interval-Time);; draw left and right branches
right-nodeleft-node(draw-line (node-left node) a-posn
width/2(get-next-left-posn a-posn (/ width 2)))(sleep-for-a-while Interval-Time)(draw-line (node-right node) a-posn(get-next-right-posn a-posn (/ width 2)))))

左右の子節の場所計算(define TopMargin 10) ;;キャンバスの上端のマージン(define N (length lof-alosp)) ;;節の数;; DP:節間の高さ(define DP (/ (- HEIGHT TopMargin) (- N (log N))));; get-next-left-posn : posn number -> posn(define (get-next-left-posn a-posn width)(make-posn (- (posn-x a-posn) width)(+ (posn-y a-posn) DP)))63 ‘A a-posnDP29 ‘B;; get-next-right-posn : posn number number -> posn;; (define (get-next-right-posn a-posn width)(make-posn (+ (posn-x a-posn) width)(+ (posn-y a-posn) DP)))width

木を描く;; draw-tree : node posn number -> true;; draw a node and branches and then traverse left and rigth nodes(define (draw-tree node a-posn width)根(root)(cond[(empty? node) true][else(and;; draw node and edges(draw-node-and-branches node a-posn width);; traverse left and right nodes(draw-tree (node-left node)(get-next-left-posn a-posn (/ width 2)) (/ width 2))(draw-tree (node-right node)(get-next-right-posn a-posn (/ width 2)) (/ width 2)))]))
キャンバスを描く;;
rootの位置(start WIDTH HEIGHT)(draw-tree (create-btree empty lof-alosp) Root-Pos)
Root-Pos=(make-posn (/ WIDTH 2) (+ d-radious TopMargine))

8