Welche Kombinationen von Pre-, Post- und In-Order-Sequentialisierung sind einzigartig?

Wir wissen nachbestellung,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

und vorbestellen

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

und in-order Traversal resp. Sequentialisierung.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

Man kann leicht erkennen, dass keiner der beiden einen bestimmten Baum eindeutig beschreibt, auch wenn wir paarweise unterschiedliche Schlüssel / Bezeichnungen annehmen.

Welche Kombinationen der drei können dazu verwendet werden und welche nicht?

Positive Antworten sollten einen (effizienten) Algorithmus zur Rekonstruktion des Baums und einen Beweis (eine Idee) für die Richtigkeit enthalten. Negative Antworten sollten Gegenbeispiele liefern, dh verschiedene Bäume, die die gleiche Darstellung haben.

algorithms binary-trees Raphael
quelle

Zunächst gehe ich davon aus, dass alle Elemente unterschiedlich sind. Keine Anzahl von Sequentialisierungen gibt Auskunft über die Form eines Baumes mit Elementen [3,3,3,3,3]. Es ist natürlich möglich, einige Bäume mit doppelten Elementen zu rekonstruieren. Ich weiß nicht, welche netten ausreichenden Bedingungen vorliegen.

Wenn Sie die negativen Ergebnisse fortsetzen, können Sie einen Binärbaum nicht vollständig aus seinen Sequentialisierungen vor und nach der Bestellung neu erstellen. [1,2]Vorbestellung, Nachbestellung [2,1]muss 1an der Wurzel haben, 2kann aber entweder das linke Kind oder das rechte Kind sein. Wenn Sie sich nicht um diese Mehrdeutigkeit kümmern, können Sie den Baum mit dem folgenden Algorithmus rekonstruieren:

Sei der Durchlauf vor der Bestellung und der Durchlauf nach der Bestellung. Wir müssen , und dies ist die Wurzel des Baumes. $[x_1,\dots,x_n]$ $[y_n,\ldots,y_1]$ $x_1=y_1$
$x_2$ ist das am weitesten links stehende Kind der Wurzel und ist das am weitesten rechts stehende Kind. Wenn , ist der Wurzelknoten unär; Verwenden Sie und , um den einzelnen Teilbaum zu erstellen. $y_2$ $x_2 = y_2$ $[x_2,\ldots,x_n]$ $[y_n,\ldots,y_2]$
Ansonsten seien und die Indizes, so dass und . ist das Durchlaufen des linken Teilbaums vor der Bestellung, das des rechten Teilbaums und ähnlich das Durchlaufen nach der Bestellung. Der linke Teilbaum hat Elemente und der rechte Teilbaum hat Elemente. Für jeden Teilbaum einmal wiederholen. Diese Methode verallgemeinert sich übrigens auf Bäume mit beliebiger Verzweigung. Ermitteln Sie mit einer beliebigen Verzweigung die Ausdehnung des linken Teilbaums und schneiden Sie die Elemente aus beiden Listen ab. Wiederholen Sie diesen Vorgang, um den zweiten Teilbaum von links abzuschneiden, und so weiter. $i$ $j$ $x_2 = y_i$ $y_2 = x_j$ $[x_2,\ldots,x_{j-1}]$ $[x_j,\ldots,x_n]$ $j-2=n-i+1$ $i-2=n-j+1$
$j-2$

Wie gesagt, ist die Laufzeit mit Worst Case (im Fall von zwei Kindern durchsuchen wir jede Listenlinie). Sie können wiederum , dass in , wenn man die Listen vorverarbeiten ein aufzubauen finite Map - Struktur von Elementwerten an Positionen in den Eingangslisten . Verwenden Sie auch ein Array oder eine finite Karte, um von Indizes zu Werten zu wechseln. Halten Sie sich an globale Indizes, damit rekursive Aufrufe die gesamte Zuordnung erhalten und einen Bereich als Argument verwenden, um zu wissen, wie verfahren werden soll. $O(n^2)$ $\Theta(n^2)$ $O(n\,\mathrm{lg}(n))$ $n\,\mathrm{lg}(n)$

Mit der Vorbestellungsüberquerung und der In-Order-Überquerung können Sie den Baum wie folgt neu : $[x_1,\ldots,x_n]$ $[z_1,\ldots,z_n]$

Die Wurzel ist der Kopf des Vorbestellungsdurchlaufs . $x_1$
Sei der Index mit . Dann ist der Durchlauf in der richtigen Reihenfolge des linken Kindes und der Durchlauf in der richtigen Reihenfolge des rechten Kindes. Gemessen an der Anzahl der Elemente ist der Durchlauf der Vorbestellung des linken Kindes und des rechten Kindes. Verwenden Sie diese Option, um die linken und rechten Teilbäume zu erstellen. $k$ $z_k = x_1$ $[z_1,\ldots,z_{k-1}]$ $[z_{k+1},\ldots,z_n]$ $[x_2,\ldots,x_k]$ $[x_{k+1},\ldots,x_n]$

Wieder ist dieser Algorithmus wie angegeben und kann in wenn die Liste in einer endlichen Karte von Werten zu Positionen vorverarbeitet wird. $O(n^2)$ $O(n\,\mathrm{lg}(n))$

Post-Order plus In-Order ist natürlich symmetrisch.

Gilles 'SO - hör auf böse zu sein'
quelle

Gibt es hier einen Tippfehler: "[1,2] Vorbestellung, [1,2] Nachbestellung muss 1 an der Wurzel haben, aber 2 kann entweder das linke Kind oder das rechte Kind sein." Die Nachbestellung eines solchen Baum wäre [2,1] nicht [1,2], ob 2 ein linkes oder rechtes Kind ist. Meinen Sie auch, wenn sowohl Vorbestellung als auch Nachbestellung gegeben sind, wir den Baum nicht rekonstruieren können, oder meinen Sie, wenn wir nur eine von ihnen bekommen, können wir den Baum nicht rekonstruieren?

CEGRD,

@CEGRD Die Nachbestellung war in der Tat ein Tippfehler. Das Beispiel zeigt, dass Sie den Baum in diesem Fall nicht vollständig rekonstruieren können: Sie können nicht wissen, ob 2es sich um ein linkes oder ein rechtes Kind handelt. Dies entspricht dem Fall "einzelner Teilbaum" des Rekonstruktionsalgorithmus.

Gilles 'SO- hör auf böse zu sein'

Wie ändert sich dies, wenn wir wissen, dass es sich um einen binären Suchbaum handelt? Für den einfachen Fall in Ihrem Beispiel ([1,2] Vorbestellung, [2,1] Nachbestellung) können wir feststellen, dass die Wurzel 1 ist und dass 2 das richtige Kind ist (weil 2 größer als 1 ist). ... Recht?

Fersarr

Welche Kombinationen von Pre-, Post- und In-Order-Sequentialisierung sind einzigartig?

Antworten: