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のステップ数が必要。

二進木は速度と引き換えにメモリを食う。