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.

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: