SICP 問題 2.64（順序づけられたリストの二進木化）

問題

次の手続 list->tree は順序づけられたリストを釣り合っている二進木へ変換する。
補助手続 partial-tree は引数として、整数 n と少なくとも n 個の要素をとり、リストの最初の n 個の要素を含む、釣り合っている木を構成する。
partial-tree が返す結果は（cons で作った）対で、その car は構成された木、cdr は木に含まれなかった要素のリストである。

(define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let* ((left-size (quotient (- n 1) 2))
	     (left-result (partial-tree elts left-size))
	     (left-tree (car left-result))
	     (non-left-elts (cdr left-result))
	     (right-size (- n (+ left-size 1)))
	     (this-entry (car non-left-elts))
	     (right-result (partial-tree (cdr non-left-elts) right-size))
	     (right-tree (car right-result))
	     (remaining-elts (cdr right-result)))
	(cons (make-tree this-entry left-tree right-tree)
	      remaining-elts))))

a. partial-tree がどう動くか、できるだけ明解な短い説明を書け。list->tree がリスト (1 3 5 7 9 11) に対して作る木を描け。

b. list->tree が n 個の要素のリストを変換するのに必要なステップ数の増加の程度はどのぐらいか。

解答

a.

・・・こういうときはコードにコメント書いていくに限るぜ！

;受け取った「要素のリスト」を釣り合った二進木に変換する。
(define (list->tree elements)
  ;受け取った要素のリストとその要素数を partial-tree に渡し、
  ;その先頭要素のみを返却する。
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= #?=n 0)
      ;要素数が０個だったら受け取った要素に空リストを連結して返却。
      ;※一体どういう意図なんだろう。。
      (cons '() elts)
      ;下記の処理で必要な各種パラメータを計算して求める
      (let* (;(要素数-1)/2 ※しかも整数
	     (left-size (quotient (- n 1) 2))
	     ;上で求めたleft-sizeで partial-tree を★★★再帰呼び出し★★★
	     ;返却するモノは・・・
	     (left-result (partial-tree elts left-size)) 
	     ;left-result の先頭要素を left-tree として保持・・・。どいうことだ？
	     (left-tree (car left-result))
	     ;left-result の残り部分を non-left-elts として保持・・・
	     (non-left-elts (cdr left-result))
	     ;right-size = 要素数 - (left-size + 1)　・・・残りの要素数？？
	     (right-size (- n (+ left-size 1)))
	     ;再帰呼び出しして帰ってきたモノの、
	     ;先頭を除く残り部分の、
	     ;更に先頭が this-entry。
	     (this-entry (car non-left-elts))
	     ;再帰呼び出しして帰ってきたモノの、
	     ;先頭を除く残り部分の、
	     ;更に先頭を除く残り部分を、
	     ;新たな要素のリストとし、それに加えて right-size を使って、
	     ;partial-tree を★★★再帰呼び出し★★★
	     (right-result (partial-tree (cdr non-left-elts) right-size))
	     ;返ってきた right-result の先頭部分を right-tree として保持
	     (right-tree (car right-result))
	     ;返ってきた right-result の先頭を除いた残りの部分を
	     ;remaining-elts として保持
	     (remaining-elts (cdr right-result)))
	;＜ partial-tree が返却するモノ＞
	;○先頭
	;　　「二進木」のデータオブジェクト。
	;○先頭を除く残りの部分
	;　　返ってきた right-result の先頭を除いた残りの部分。
	(cons (make-tree this-entry left-tree right-tree)
	      remaining-elts))))

分かったことを書き連ねてみよう。

partial-tree が返却するモノは、「先頭要素は二進木」「それ以降はリスト」。
partial-tree は呼び出される度に渡される要素数 n は約半分になっている。
left-result を求める為に partial-tree を呼び出す場合の「要素のリスト」は、常に最初に渡された「要素のリスト」と同じ。
左側の二進木が、先にガンガン生成される。（let* 内で処理がどんどん進んでいく）
左側の二進木が全部生成され終わった後に、右側の二進木が生成されていく。
right-result を求める為に partial-tree を呼び出す場合の「要素のリスト」は、左側の二進木が生成された際についでに返ってくる「それ以降はリスト」の部分を材料にしている。

こんなとこだなぁ。なんとなくわかった。
ようするに、受け取るモノは順序づけられたリストだから、リストの中央の要素と、その左側、右側で分断し、左側が左二進木になるように、右側が右二進木になるようにして最後にこの３者を使ってmake-tree してる。（受け取るのが順序付けられたリストだから可能なんだな。）

(1 3 5 7 9 11) を list->tree に作用させるとこうなった。



gosh> (list->tree '(1 3 5 7 9 11))

(5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))

gosh>

それっぽく図にしてみると・・・

こんな感じ。

b.

ロジックを解析してみたら・・・順序づけられたリストの要素を一つ一つチェックしてるだけだから、Θ(n)？（自信なし・・・）