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))))))))
- Write a short paragraph explaining as clearly as you can how
partial-tree
works. Draw the tree produced bylist->tree
for the list(1 3 5 7 9 11)
. - What is the order of growth in the number of steps required by
list->tree
to convert a list of n elements?
partial-tree
WorksBefore we give our short paragraph let's first note what
quotient
does as it's used here without any description. It's official definition in the Scheme R5RS specification can be found here. However, its functionality can be summarized as returning the result of dividing the first numeric operand by the second numeric operand and, if this is not an integer value, rounding it down to the nearest integer towards zero.Okay, so given the assumptions about the operands to
partial-tree
listed above let's now describe how partial-tree
works...In the terminating case, when n=0,
partial-tree
simply returns a pair containing a representation of an empty binary tree and the unaltered list of elements it was called with (as these elements were not added to the binary tree generated). However, in the non-terminating case partial-tree
first calculates the number of elements that should go into the left sub-tree of a balanced binary tree of size n, then invokes partial-tree
with the elements and that value which both produces such a sub-tree and the list of elements not in that sub-tree. It then takes the head of the unused elements as the value for the current node, the tail as the potential elements for the right sub-tree and calculates how many elements should go into the right sub-tree of a balanced binary tree of size n. To build the right sub-tree it then invokes partial-tree
with the unused elements and the required size of the right sub-tree to build it and get any remaining elements. Finally it builds the balanced tree with the generated components and returns this tree along with any remaining elements.Note that a more succinct way of putting this would be to say that, for the non-terminating case,
partial-tree
splits the list into four: elements preceding the (n/2)th position, the element at the (n/2)th position, elements between the (n/2)th position (exclusive) and the nth position (inclusive) in the list and elements after the nth position in the list. It then builds binary trees for the first and third of these lists using recursive calls to partial-tree
, puts these sub-trees together, along with the element at the (n/2)th position, to produce a tree and returns this along with the fourth list. However, while this captures the effect of the procedure, it doesn't describe the actual implementation.I'd like to add a further note to this part of the exercise. The authors state that "
list->tree
converts an ordered list to a balanced binary tree". I'd like to correct this a little... list->tree
will convert any list into a balanced binary tree; however, if the list is ordered then list->tree
will convert it into a balanced binary search tree.As for the tree produced by
list->tree
for the list (1 3 5 7 9 11)
, well here's the procedure in action:
> (list->tree '(1 3 5 7 9 11)) '(5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))If, as in the book, we omit empty lists from the tree diagram, then this gives us the following tree: (b) Order of Growth
First, lets make the assumption that all of the list and pair operations (i.e.
car
, cdr
, cons
and list
) are Θ(1) operations. I include list
in this as make-tree
uses it.Now, excluding the recursive calls,
partial-tree
performs a fixed set of these operations for each list it processes. As a result we can say that, excluding recursive calls partial-tree
runs in constant time (i.e. Θ(1)). We also know that, due to the way in which partial-tree
operates, it makes recursive calls such that uses each index in the range 1..n exactly once. Now if you perform n invocations of an Θ(1) operation that gives you an order of growth of Θ(n).Finally,
list->tree
simply makes a single call to partial-tree
using the length of the list of elements as n. If we make a further assumption that length
is, in the worst case, Θ(n) (i.e. if it has to iterate through the list and count all the elements), then this means that list->tree
is Θ(n).
No comments:
Post a Comment