Note: this wiki is now retired and will no longer be updated!
The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.
SICP exercise 2.64
The following procedure list->tree converts an ordered list to a balanced binary tree. The helper procedure partial-tree takes as arguments an integer n and list of at least n elements and constructs a balanced tree containing the first n elements of the list. The result returned by partial-tree is a pair (formed with cons) whose car is the constructed tree and whose cdr is the list of elements not included in the tree.
(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))))))))
a. Write a short paragraph explaining as clearly as you can how partial-tree works. Draw the tree produced by list->tree for the list (1 3 5 7 9 11).
b. What is the order of growth in the number of steps required by list->tree to convert a list of n elements?
Solution, part A.
partial-tree divides its input list into 3 parts: a new list containing the first (n − 1) / 2 elements in the list, the middle element of the list, and another list containing the remaining elements. The two new lists are created recursively by applying partial-tree to each half of the input list. (The middle element is simply the car of the list of elements remaining after creating the first new list.) If the list is empty, partial-tree returns an empty list, which corresponds to the end of a branch. Because the input list is ordered, all of the elements in the first new list are smaller in magnitude than the middle element, and all of the elements in the second new list are greater than the middle element. It then creates a balanced tree rooted at the middle element whose left branch is the first new list and whose right branch is the second new list. Because the left and right branches were created recursively by partial-tree, each of those branches is balanced, as well, eventually resulting in a balanced tree that corresponds to the original input list.
The tree produced by list-tree for the list (1 3 5 7 9 11) is identical to the right-most tree in figure 2.16 of the text (the tree rooted at 5).
Solution, part. B.
list-tree's order of growth is determined by partial-tree. partial-tree visits each element in the original input list exactly once (it must, in order to make each element the entry of a node in the balanced tree): this is θ(n) operations. Each visit performs a single cons, which requires a constant-factor number of steps for our purposes, so the overall order of growth in steps is also θ(n).