Allgemeiner Baum zu binärer Baumkonvertierung Komplexität

Question

Was ist die Zeit und die Raumkomplexität der Umwandlung eines allgemeinen Baumes in Binärer?!

Vielen Dank

Answer 1

Ich weiß nicht, was du mit "allgemeinem Baum" meinst. Unabhängig davon ist die Komplexität des Insertionskomplexität in einen ausgewogenen binären Baum O(log n), wo n Ist die Anzahl der Gegenstände derzeit im Baum. Das Erstellen eines vollständigen Baums aus einer Liste von Elementen wäre daher, dass es sich O(n log n), wo n Ist die Gesamtzahl der zu eingefügten Elemente.

Sie müssen auch die Zeit aufnehmen, die erforderlich ist, um Gegenstände vom anderen Baum zu erhalten. Diese Zeit hängt von der Art des Baumes ab, den Sie haben. Aus Gründen der Argumentation gehe ich davon aus O(n).

Das macht Ihre Gesamtzeitkomplexität O(n + (n log n)).

Der erforderliche zusätzliche Platz wird sein n * sizeof(node), wo sizeof(node) ist die Größe Ihres binären Baumknotens. Beachten Sie, dass Sie nicht die Kosten für das Kopieren der tatsächlichen Objekte bezahlen müssen, wenn die in den "allgemeinen Baum" gespeicherten Elementen Zeiger sind-nur den Overhead des Binärbaumknotens, der normalerweise drei Zeiger ist: die Daten, die linke Kinderverbindung und die rechte Kinderverbindung.