SICPを読む(74) 問題2.64 二進木としての集合(2)
次は順序づけられたリストを釣合った二進木へと変換する問題。
問題 2.64
とりあえず、let*に直す。
(define (partial-tree elements n) (if (= n 0) (cons '() elements) (let* ((left-size (quotient (- n 1) 2)) (left-result (partial-tree elements left-size)) (left-tree (car left-result)) (non-left-elements (cdr left-result)) ; center & right (right-size (- n (+ left-size 1))) (this-entry (car non-left-elements)) (right-result (partial-tree (cdr non-left-elements) right-size)) (right-tree (car right-result)) (remaing-elements (cdr right-result))) (cons (make-tree this-entry left-tree right-tree) remaing-elements))))
だいぶすっきり。
で、問題だ。
a
何をやってるのか。という問題。
まず、(list->tree '(1))について考えよう。
; 1 ; / \ ; / \ ;'() '()
忘れちゃいけないのは末尾に'()が付くこと。つまり、真ん中が1、左右が'()である。
真ん中と左右のデータをどんどん振り分けるって事をしてる。
次に、partial-treeの引数nに注目してみる。
(partial-tree '(1 2 3) 0) ; (() 1 2 3) (partial-tree '(1 2 3) 1) ; ((1 () ()) 2 3) (partial-tree '(1 2 3) 2) ; ((1 () (2 () ())) 3) (partial-tree '(1 2 3) 3) ; ((2 (1 () ()) (3 () ())))
リスト左側n個をを処理して、真ん中と右側を保留しておくということがわかる。
さて、本題の(list->tree '(1 3 5 7 9 11)を追う。
まず、
(partial-tree '(1 3 5 7 9 11) 6)
分割すると、(1 3) 5 (7 9 11)となる。まずは(1 3)について処理する。
まんまリストを投げる。しかし、先頭2個だけ処理してくれ。
(partial-tree '(1 3 5 7 9 11) 2)
こんな感じ。
(partial-tree '(1 3 5 7 9 11) 0) ; (() 1 3 5 7 9 11) (partial-tree '(3 5 7 9 11) 1) ; ((3 () ()) 5 7 9 11) (partial-tree '(1 3 5 7 9 11) 2) ; ((1 () (3 () ())) 5 7 9 11)
左側が出た。5は置いといて、右側を処理。
(partial-tree '(7 9 11) 3) (partial-tree '(7 9 11) 1) ; ((7 () ()) 9 11) (partial-tree '(9 11) 2) ; ((9 () (11 () ()))) (partial-tree '(7 9 11) 3) ; ((9 (7 () ()) (11 () ())))
左右、真ん中を結合
(partial-tree '(1 3 5 7 9 11) 6) ; ((5 (1 () (3 () ())) (9 (7 () ()) (11 () ()))))
出た。で、問題みたら、明快にって書いてあった・・・しまった。明快に説明すると、
真ん中と左右に分割。左右をまた分割。分割・・・細分化されたらダダッと、make-tree。
クイックソートみたいな感じ。
b
n個のデータを処理するのに必要なステップ数はデータの数に比例する。しかし、'()を処理しなければならない。
'()の数はn + 1個になるので、n個のデータを処理するためには、(n * 2) + 1のステップ数が必要。
二進木は速度と引き換えにメモリを食う。