SICPを読む(77) 問題2.66 集合と情報検索
さて、二進木の最後の問題。「データベースをつくろう」という問題。
問題 2.66
要約すると、idからデータを検索する二進木データベースの設計をせよ。という問題。
まずはデータ構造の変更
1レコードのデータ構造を変更します。
なるべく変更点が少ない方がいいので、1レコードのデータ構造は
((id . データ) 左 右) ((0 . Scheme) () ())
とします。
データ構造を変えたので、アクセサをチョッといじります。
(define entry caar) (define data cdar)
変更点はこれだけ。ホントはentryをidに変えたい所なんだけど、色々面倒そうなので・・・。
(id . data)な対を作るコンストラクタを作っておいてっと。
(define (make-entry id data) (cons id data))
データ構造設計終わり。
データ入力の簡易化
リストでガガーっと入力したいので、サポートツール作り。
(define (make-list id l) (if (null? l) '() (cons (make-entry id (car l)) (make-list (+ id 1) (cdr l))))) (define db-list (make-list 0 '(Scheme Commn-lisp C C++ Haskell Logo Ruby JavaScript))) ; ((0 . Scheme) (1 . Commn-lisp) (2 . C) (3 . C++) ; (4 . Haskell) (5 . Logo) (6 . Ruby) (7 . JavaScript))
これで、list->treeが使えます。
(define db (list->tree db-list)) ; ((3 . C++) ((1 . Commn-lisp) ((0 . Scheme) () ()) ((2 . C) () ())) ; ((5 . Logo) ((4 . Haskell) () ()) ((6 . Ruby) () ((7 . JavaScript) () ()))))
データベース完成!!
検索してみる
element-of-set?をチョチョイといじってっと。
(define (lookup key set) (cond ((null? set) #f) ((= key (entry set)) (data set)) ((< key (entry set)) (lookup key (left-branch set))) ((> key (entry set)) (lookup key (right-branch set)))))
id(key)で検索してみます。
(lookup 0 db) ; Scheme (lookup 1 db) ; Commn-lisp (lookup 6 db) ; Ruby
うまくいきました。
