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

Exercise 2.65: Use the results of Exercise 2.63 [qui] and Exercise 2.64 [qui] to give `Θ(n)` implementations of `union-set` and `intersection-set` for sets implemented as (balanced) binary trees.

Passo –al solito– la parola a Bill the Lizard 💥

We implemented `union-set` for the unordered list representation of sets back in exercise 2.59 [qui]. This implementation had to check all elements of one set for each element of the other, so it’s complexity was `O(n2)`, quite poor. We improved on this in exercise 2.62 [qui] when we wrote an implementation of `union-set` for the ordered list representation of sets, which was `O(n)`. The text supplied a similar implementation of `intersection-set` that was also `O(n)`. We could use these ordered set implementations as a guide to writing efficient implementations of `union-set` and `intersection-set` for balanced binary trees, but that wouldn’t require the results of the previous two exercises. Instead, we can use the `O(n)` implementations of all of the procedures we’ve built so far to perform the following steps:

• Convert the balanced binary trees to ordered lists.
• Perform the desired operation (`union-set` or `intersection-set`).
• Convert the resulting ordered set back to a balanced binary tree.
``````(define (union-set tree1 tree2)
(define (union-list set1 set2)
(cond ((null? set1) set2)
((null? set2) set1)
((= (car set1) (car set2))
(cons (car set1) (union-list (cdr set1) (cdr set2))))
((< (car set1) (car set2))
(cons (car set1) (union-list (cdr set1) set2)))
(else (cons (car set2) (union-list set1 (cdr set2))))))
(list->tree (union-list (tree->list-2 tree1)
(tree->list-2 tree2))))

(define (intersection-set tree1 tree2)
(define (intersection-list set1 set2)
(if (or (null? set1) (null? set2))
'()
(let ((x1 (car set1)) (x2 (car set2)))
(cond ((= x1 x2)
(cons x1
(intersection-list (cdr set1)
(cdr set2))))
((< x1 x2)
(intersection-list (cdr set1) set2))
((< x2 x1)
(intersection-list set1 (cdr set2)))))))
(list->tree (intersection-list (tree->list-2 tree1)
(tree->list-2 tree2))))``````

In the implementations above, I’ve just defined the earlier ordered set implementations of `union-set` and `intersection-set` as helper functions named `union-list` and `intersection-list`. With these helper functions, all `union-set` and `intersection-set` need to do is convert from tree to list and back from list to tree. We can define a few balanced trees to test that these new implementations work as expected.

Raccolgo il codice nel file `ex-2-65.rkt`. Servono anche `list->tree`, `partial-tree`, `make-tree`, `tree->list-1` e `tree->list-2`. OK anche sicp-ex e Drewiki.

🤢

Posta un commento o usa questo indirizzo per il trackback.