2.64

练习 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)
          )
         )
        (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
                 )
                )
              )
            )
          )
        )
      )
  )
​x
 
#<undef>

a) 请简要地并尽可能清楚地解释为什么partial-tree能完成工作。请画出将list->tree用于表(1 3 5 7 9 11)产生的树。

b) 过程list->tree转换n个元素的表所需的步数以什么量级增长？

a) 先做个实验吧。

先把 tree 的选择函数定义写一下：

 
(define entry car)
(define left-branch cadr)
(define right-branch caddr)
​
(define (quotient n m) 
  (floor (/ n m))
  )
 
#<undef>

再把 tree 的构造函数定义写一下：

 
(define (make-tree entry left right)
  (list entry left right)
  )
​
(list->tree (list 1 3 5 7 9 11))
 
(5 (1 nil (3 nil nil)) (9 (7 nil nil) (11 nil nil)))

真的可以！

完成的过程真是妙不可言！首先，使用 quotient 计算出左子树的最大大小，然后用总长度减掉左子树的最大大小再减1，得到右子树的最大大小。因此左子树和右子树的大小是差不多的（平衡的）。被减掉的那个1，就成为了树根。

首先从所有的元素里挑出左子树的最大大小那么多元素，构建左子树。然后从没有被放进左子树的元素中构建右子树。最后，将树根、左子树、右子树组合成一棵树。于是完成了工作（剩下的没有被放进树中的元素（如果有的话），和树一起组合成序对返回）。

b) 假设 partial-tree 所需的步数是以 f(n) 的量级增长。那么对于给定的 n，又会分别调用两次 partial-tree，即 f(n) = f(n/2) + f(n/2) = 2 * f(n/2)。

当 n = 1 时，左子树大小为0，右子树大小为0，只有树根，只需要一步，即 f(1) = 1。

所以，partial-tree 所需的步数是以 $f(n) = 2 * log^{n}_{2}$ 的量级增长的。