SICP 問題 2.66（二進木に対する検索処理）

Scheme SICP

問題

レコードの集合がキーの数値で順序づけられている二進木で構造化されている場合の lookup 手続きを実装せよ。

解答

今までやってきた順序づけられた二進木の検索だから、キーの値を比較する時に

  • 等しい → そのレコードを返却
  • 小さい → 左側の二進木で再帰チェック
  • 大きい → 右側の二進木で再帰チェック
ということをやってやりゃいい。

(define (lookup-for-ordered-tree key tree)
  (cond ((null? tree) #f)
	((equal? key (get-key (car tree)))
	 (car tree))
	((< key (get-key (car tree)))
	 (lookup-for-ordered-tree key (left-branch tree)))
	(else ;(< (get-key (car tree)) key)
	 (lookup-for-ordered-tree key (right-branch tree)))))

SICPの本には、レコードの構成子とかの記述がないから、ちょっと実験はメンドくせえなぁ〜と思ったらそうでもなかった。

;レコードの構成子。
;名前しか付加されてないけど、まあ住所とか電話番号とかいろいろくっつけてもいいよ。
;面倒だからやらないけど。。
(define (make-record id name)
  (list id name))

;lookup-for-ordered-tree の内部で使用されている、レコードのキーを取得する選択子。
(define (get-key record)
  (car record))

さ、じゃテストデータをつくろう！
順序づけられたリストから順序づけられた二進木を生成する list->tree 手続きを使用して・・・



gosh> (define records (list->tree (list

				   (make-record 1 "保毛川 保毛雄")

				   (make-record 3 "保毛川 保毛美")

				   (make-record 5 "不賀本 不賀之")

				   (make-record 7 "不賀本 不賀子")

				   (make-record 9 "茂賀 文太")

				   (make-record 11 "茂賀 文子"))))

records

gosh> records

((5 "不賀本 不賀之") ((1 "保毛川 保毛雄") () ((3 "保毛川 保毛美") () ())) ( (9 "茂賀 文太") ( (7 "不賀本 不賀子") () ()) ((11 "茂賀 文子") () ())))

gosh>
で、この records 二進木に対して lookup-for-ordered-tree でデータを検索！


gosh> (lookup-for-ordered-tree 3 records)

(3 "保毛川 保毛美")

gosh> (lookup-for-ordered-tree 9 records)

(9 "茂賀 文太")

gosh>
取れてるねぇ〜♪