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

拙いながらもpartial-treeの動作説明。
partial-treeはリストから平衡木を作成し、その平衡木を第1要素、木に含まれない要素を第2要素にリストとして返すような関数になっている。

(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))))))))

まず、引数eltsは平衡木の要素を持つリスト、nは結果となる平衡木に含まれる要素数というお話。
まずnが0のときは、結果の平衡木は空で、elts中の全要素が余りとして返される。
その他の場合は、まずn個の要素を平衡木の左部分木の要素数(left-size)と根（1個）と右部分木（right-size）の3つに分割する。平衡木と言ってもどうも完全平衡木を目指しているっぽくて、左部分木と右部分木は同数のにしている。
要素数が割り出せたら、あとはpartial-treeを再帰的に呼び出すことで、左部分木と右部分木が構成できる。順番としてはまず左部分木を作っていて、その残りカスの第1要素を根、それ以外の残りカスで右部分木を構成する。部分木さえ構成できれば、あとはmake-treeを呼び出して根と左部分木、右部分木で木を構成する。

(b)に関しては概算でアレなんですけど、という仮定の下だと1回partial-treeを呼び出すと、に対するpartial-treeを2回呼び出すことになる。要素数nに対するpartial-treeの計算量をで表したら、 （ただしcは定数）。かつとかだとすると、クソ適当にとかになる。解いたらな感じ？