Allgemeine Umwandlung von Baum zu Binärbaum

Question

Wie groß ist die Komplexität von Zeit und Raum bei der Umwandlung eines allgemeinen Baums in einen binären ?!

Dank

Answer 1

Ich weiß nicht, was Sie von meinem „allgemeinem Baum.“ Ungeachtet dessen ist die Komplexität der Einfügung in einen ausgeglichenen Binärbaum O(log n), wobei n die Anzahl der derzeit im Baum enthaltenen Elemente ist. Daher würde ein vollständiger Baum aus einer Liste von Elementen O(n log n) sein, wobei n die Gesamtzahl der Elemente angibt eingefügt werden.

Sie müssen auch die Zeit angeben, die benötigt wird, um Elemente aus dem anderen Baum zu erhalten. Diese Zeit hängt von der Art des Baumes ab, den Sie haben. Aus Gründen des Arguments nehme ich an, dass Sie es in linearer Zeit durchlaufen können, also Daten aus dem vorhandenen Baum zu erhalten ist O(n).

Das macht Ihre gesamte Zeit Komplexität O(n + (n log n)).

Der zusätzliche Platzbedarf ist n * sizeof(node), wobei sizeof(node) die Größe Ihres binären Baumknotens ist. Beachten Sie, dass, wenn die Elemente, die in den "allgemeinen Baumknoten" gespeichert sind, Zeiger sind, Sie nicht die Kosten für das Kopieren der tatsächlichen Objekte bezahlen müssen - nur der Overhead des binären Baumknotens, der typischerweise drei Zeiger ist: der Daten, die linke untergeordnete Verbindung und die rechte untergeordnete Verbindung.