SICP問題2.64

教科書で定義されている順序づけられたリストを釣り合ってる二進木に変換する手続きlist->treeと補助手続きpartial-tree

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

ここでquotient は整数の割り算の商を求める関数らしい。

a. partial-tree がどう働くか? list->tree がリスト(1 3 5 7 9 11)に対して作る木はどう描かれるか?
paritial-tree はリストとリストの長さを与えられるが、この長さを使用してリストを半分にし、中心の値をエントリ、値が小さい方のリストを左ツリー、値が大きい方のリストを右ツリーとして、それぞれのツリーを作成するのに、partial-tree を再帰的に呼び出す。
この関数によって(1 3 5 7 9 11)に対して作成される木は

(partial-tree 1 3 5 7 9 11)
; => (5 partial-tree(1 3) partial-tree(7 9 11))
; => (5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))

となり、以下のように描かれる

     5
   /   \
  1     9
   \   / \
    3 7   11

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

n 個の要素のリストを変換するのに必要なステップ数はpartial-treeを呼び出す回数となり、それは以下のようになる。

n=1 の時 (1 + 0 + 0) = 1
n=2 の時 (1 + (1 + 0 + 0) + 0) = 2
n=3 の時 1 + (1 + 0 + 0) + (1 + 0 + 0) = 3
n=4 の時 1 + (1 + (1 + 0 + 0) + 0) + (1 + 0 + 0) = 4
n=5 の時 1 + (1 + (1 + 0 + 0) + 0) + (1 + (1 + 0 + 0) + 0) = 5
...

よってステップ数の増加は Θ(n)となる。