Hier ist die Übung 2.65 von SICP:
Verwenden Sie die Ergebnisse der Übungen 2.63 und 2.64, um Θ (n) Implementierungen von Vereinigungsmengen und Schnittmengen für Sätze zu erhalten, die als (ausgeglichene) Binärbäume implementiert sind.
Im Kapitel "Als geordnete Listen setzen" und Aufgabe 2.62 haben wir bereits die Vereinigungs- und Schnittmenge für die geordneten Listen. Ich habe das Internet durchsucht, die Antwort von 2.65 ist zu einfach zu akzeptieren, sie konvertieren nur die Binärbäume in Listen und verwenden immer noch die Vereinigungsmenge und die Schnittmenge für die geordneten Listen.
Meiner Meinung nach müssen wir die Mengen in Binärbäume umwandeln und die Vereinigungsmengen und Schnittmengen für die Binärbäume neu schreiben.
Also, verstehe ich die Bedeutung von Übung 2.65 von SICP falsch? Oder gibt es eine gute Antwort?
Die "einfache" Antwort ist in diesem Fall richtig: Die Übung wird gelöst, indem zuerst die Bäume in Listen umgewandelt werden (in der Tat geordnete Listen, weil wir die Bäume in Querrichtung durchqueren), dann Verwenden geordneter Mengenverfahren und schließlich Umwandeln der resultierenden Mengen zurück in Bäume. Warum ist das korrekt? Denn das beschriebene Verfahren erreicht die geforderte prozentuale Komplexität mit bereits bestehenden Verfahren - das Rad muss nicht neu erfunden werden!
Obwohl eine "direkte" Antwort geschrieben werden kann, indem Bäume manipuliert werden, ist es zu mühsam und es wird sehr schwierig (wenn nicht unmöglich!) in O(n) zu implementieren, ohne Mutationsoperationen zu verwenden - und bis zu An dieser Stelle im Buch haben wir noch nicht O(n) , set! oder set-car! verwendet.
Sie haben Recht, Sie könnten frühere Beispiele aus dem Text als Anleitung zum Schreiben effizienter Implementierungen von union-set und intersection-set für symmetrische Binärbäume verwenden. Der Text fordert Sie jedoch ausdrücklich auf, die Ergebnisse der beiden vorherigen Übungen zu verwenden, damit Sie zu einer bestimmten Lösung gelangen. Diese Lösung (konvertiere den Binärbaum in eine Liste, um das Problem auf einen bereits gelösten zu reduzieren) ist bereits O (n), was die beste Reihenfolge ist, die du mit diesem Problem trotzdem bekommen kannst.