## SICP – cap. 2 – sets come alberi binari – 84 . esercizio Continuo da qui, copio qui.

Exercise 2.63: Each of the following two procedures converts a binary tree to a list.

``````(define (tree->list-1 tree)
(if (null? tree)
'()
(append
(tree->list-1
(left-branch tree))
(cons (entry tree)
(tree->list-1
(right-branch tree))))))

(define (tree->list-2 tree)
(define (copy-to-list tree result-list)
(if (null? tree)
result-list
(copy-to-list
(left-branch tree)
(cons (entry tree)
(copy-to-list
(right-branch tree)
result-list)))))
(copy-to-list tree '()))``````
• Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in Figure 2.16 [post precedente]?
• Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?

Al solito passo la parola a Bill the Lizard.

The `tree->list-1` procedure checks to see if the tree passed in is `null`, and if so returns an empty list. If the tree is not `null`, it creates a list by appending the left branch of the tree, the element at the root node, and the right branch of the tree. Elements of the left and right branches are flattened into lists using recursive calls to `tree->list-1`. The `tree->list-2` procedure defines a helper function `copy-to-list` that takes the tree and a `result-list` as arguments. When the tree is `null`, it returns the `result-list` that was passed in. The `copy-to-list` helper function also uses recursive calls to the left and right branches of the tree while building the final result list. These two procedures will produce the same results for every tree.

We’re asked to test the two procedures on the trees in figure 2.16.

Inserisco il codice, completo di quello del post precedente, in `es-2.63.rkt`. We can see from these results that both procedures return an in-order traversal for every tree.

We’re also asked if the two procedures have the same order of growth for a balanced tree, and if not, which one grows more slowly?

We can see from the results above and from inspecting the two procedures that each node of the tree is visited one time by each algorithm. What happens at each of those `n` steps is subtly different though. The second procedure simply calls cons at each step, which we’ll assume is a constant-time operation, so the `tree->list-2` procedure has a time complexity of `O(n)`. The first procedure calls append at each step, which we saw in section 2.2.1 has the following definition:

``````(define (append list1 list2)
(if (null? list1)
list2
(cons (car list1) (append (cdr list1) list2))))``````

From this definition we can see that the order of growth of append is proportional to the first list argument that’s passed in. In the case of `tree->list-1`, the first list argument is the left branch of the tree, which is about half of a node’s elements for a balanced tree. This means that for each recursive call, approximately half of the number of nodes will be in the first list argument as in the previous call. Since the number of elements is cut in half on each of the `n` calls to append, the `tree->list-1` procedure has a complexity of `O(nlog n)` for a balanced tree.

Già detto che 👽 Bill 💥 rockz?

Simile ma meno didascalica la soluzione di sicp-ex.
Descrittiva quella di Drewiki.

🤢

Posta un commento o usa questo indirizzo per il trackback.