Czy źle rozumiem znaczenie ćwiczenia 2.65 SICP?

Question

Oto ćwiczenia 2.65 z SICP:

pomocą wyników ćwiczeń 2,63 i 2,64 otrzymując Θ (n) implementacje związek ustawione i przecięcie ustawieniem zestawów realizowane jako (symetryczne) drzewo binarne.

W rozdziale "Ustaw jako listę uporządkowaną" i ćwiczeniu 2.62 mamy już zestaw związków i zestaw skrzyżowań dla uporządkowanych list. Przeszukałem Internet, odpowiedź 2.65 jest zbyt prosta do zaakceptowania, po prostu konwertują drzewa binarne na listy i nadal używają zestawu związków i skrzyżowań dla uporządkowanych list.

Moim zdaniem, musimy przekonwertować zestawy na drzewa binarne i przepisać zestaw związków i zestaw skrzyżowań dla drzew binarnych.

Czy zatem źle rozumiem znaczenie ćwiczenia 2.65 SICP? Czy istnieje dobra odpowiedź?

Answer 1

„simple” odpowiedź jest poprawna w tym przypadku: ćwiczenie jest rozwiązany przez pierwszy konwersji drzew na listach (w rzeczywistości nakazał list ponieważ robimy Inorder przechodzenie drzew), a następnie za pomocą ordered- ustaw procedury, a na końcu przekonwertuj wynikowe zbiory z powrotem na drzewa. Dlaczego to się zgadza? ponieważ opisana procedura zapewnia wymaganą złożoność O(n) przy użyciu już istniejących procedur - nie ma potrzeby ponownego odkrywania koła!

Chociaż "bezpośrednia" odpowiedź może być napisana przez manipulowanie drzewami, to zbyt wiele kłopotów i będzie to bardzo trudne (jeśli nie niemożliwe!) Do wdrożenia w O(n) bez korzystania z operacji mutacji - i do tego czasu punkt w książce, jeszcze nie użyliśmy set!, set-car! lub set-cdr!.

Answer 2

Masz rację, ty mógłby wykorzystywać wcześniejsze przykłady z tekstu jako przewodnik do pisania skutecznych wdrożeń union-set i intersection-set symetrycznych drzew binarnych. Jednak tekst wyraźnie mówi, aby użyć wyników z dwóch poprzednich ćwiczeń, więc prowadzi cię do konkretnego rozwiązania. To rozwiązanie (konwertuj drzewo binarne na listę, aby zredukować problem do już rozwiązanego) jest już O (n), co jest najlepszą kolejnością, jaką możesz uzyskać z tym problemem.