Scheme - 記号データ(二進木としての集合(順序づけられたリストを釣り合っている二進木へ変換する手続き))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の2(データによる抽象の構築)、2.3(記号データ)、2.3.3(例: 集合の表現)、二進木としての集合の問題 2.64、a、bを解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 2.64

a.

最初のn個の要素リストから、そのn個のリストの真ん中(nが偶数の場合はその1個前)の要素を見出しとし、その左側、右側のリストからも同様に再帰的に木を作成し、それぞれを左部分木、右部分木とする木を作成し、その木とn+1番目以降の要素をリストとするリストの対を返す手続き。

list->treeがリスト(1 3 5 7 9 11)に対して作る木。

確認。

コード

sample.scm

(define tree (list->tree (list 1 3 5 7 9 11)))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> (left-branch tree)

;Value 2: (1 () (3 () ()))

1 ]=> (right-branch tree)

;Value 3: (9 (7 () ()) (11 () ()))

b.

全ての要素が見出しとなるようなリストにpartial-treeが呼び出されることになるから、ステップ数の増加の程度はΦ(n)。