問題2-66 (2.3.3 Example: Representing Sets)

データをどう表現するかでプログラムの性能に大きな影響があるよというお話がなされてきたのだけど、最初はクソ簡単で直感的な表現にして後から性能を上げるようにするのも一つの手だよとおっしゃられておられる。たぶんその例なんだろうけど、問題2-66は順序無しリストで表現されたデータベース上でのlookupを2分木で表現されたデータベース上でのlookupにしろって課題。

こんなlookupを定義してやれば

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) #f)
	((= given-key (entry set-of-records)) set-of-records)
	((< given-key (entry set-of-records))
	 (lookup given-key (left-branch set-of-records)))
	((> given-key (entry set-of-records))
	 (lookup given-key (right-branch set-of-records)))))

順序付き2分木上をわりかし高速に検索できるようになる。はず。

(define first 
  (make-tree 7
	     (make-tree 3
			(make-tree 1 '() '())
			(make-tree 5 '() '()))
	     (make-tree 9
			'()
			(make-tree 11 '() '()))))

(lookup 3 first) ; (3 (1 () ()) (5 () ()))