You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('') and can be up to 35 characters long.
62 lines
2.2 KiB
62 lines
2.2 KiB
(load "displaylib.scm")


(title "Exercise 2.64")


(print "


The following procedure list>tree converts an ordered list to a balanced binary tree. The helper procedure partialtree 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 partialtree 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 (partialtree elements (length elements))))




(define (partialtree elts n)


(if (= n 0)


(cons '() elts)


(let ((leftsize (quotient ( n 1) 2)))


(let ((leftresult (partialtree elts leftsize)))


(let ((lefttree (car leftresult))


(nonleftelts (cdr leftresult))


(rightsize ( n (+ leftsize 1))))


(let ((thisentry (car nonleftelts))


(rightresult (partialtree (cdr nonleftelts)


rightsize)))


(let ((righttree (car rightresult))


(remainingelts (cdr rightresult)))


(cons (maketree thisentry lefttree righttree)


remainingelts))))))))




a. Write a short paragraph explaining as clearly as you can how partialtree 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?


")




; a.


;


; The procedure is recursive:


;


; it first constructs (recursively) the lefttree


; and using the remaining elements of the list


; construct the root of the tree and the righttree (recursively)


;


; example: (1 3 5 7 9 11)


;


; => ( 1 3 5 7 9 11 ) 6


;


; makelefttree => (1 3 5 7 9 11) 3 > (3 (1) (5)) rest 7 9 11


; takeroot => 7


; makerighttree => (9 11) 2 > (9 (11)), rest ()


;


; result => (7 (3 (1 5)) (9 (11)))


;


; b. Order of growth


;


; recursively: f(n) = c + 2f(n/2)


; f(0) = c


;


; f(0) = c


; f(1) = c + 2f(0) ~ 3c


; f(2) = c + 2f(1) ~ 7c


; f(4) = c + 2f(2) ~ 15c


; etc...


; f(2^n) = ϴ(2^n)


;


; generally => f(n) = ϴ(n)


;


; well played!


