uni/algodat/report123/p3-fragestellungen.md

P3 Fragestellungen

Gleichheit

Wie sich erkennen lässt, handelt es sich bei den resultierenden Bäumen aus Pre Order 13 und Post Order 87 um dieselben Bäume.

Funktionsweise

Eine grundsätzliche Idee beider Algorithmen ist es, dass einer In Order Reihenfolge nicht die entsprechende Hierarchie, beispielsweise der richtige Wurzelknoten, entnommen werden kann, aber durchaus die Ordnung der Elemente. Sowohl bei einer Pre Order Reihenfolge, als auch bei einer Post Order Reihenfolge, kann sehr leicht der Wurzelknoten entnommen werden. Das erste Element der Pre Order Reihenfolge, durch die Gegebenheiten der Pre Order Reihenfolge, muss der Wurzelknoten des ursprünglichen Baumes gewesen sein. Das letzte Element der Post Order Reihenfolge, durch die Gegebenheiten der Post Order Reihenfolge, muss der Wurzelknoten des ursprünglichen Baumes gewesen sein.

Diese Kernideen können angewandt werden, um einen eleganten rekursiven Algorithmus zu finden, der sich um eine korrekte Rekonstruktion kümmert. Wurde nämlich ein Wurzelknoten gefunden, kann der In Order Reihenfolge entnommen werden, welche Elemente sich im linken Teilbaum und welche Elemente sich im rechten Teilbaum befinden müssen. Die zuvor behandelte Wurzel gilt als abgearbeitet und wird im Verlauf nicht mehr beachtet. Diese Vorgehensweise lässt sich rekursiv anwenden, da die Teilbäume ebenso zu rekonstruierende Bäume sind.

Illustrativ, angenommen preOrder[0] hat den Index n im Array inOrder, mit $0 <= n <= l, l := inOrder.length - 1$. Dann beschränkt sich die Menge der Elemente im linken Teilbaum auf die Indizes für inOrder im Interval $[0, n)$, im rechten Teilbaum auf die Indizes im Interval $(n, l]$.

Ein markanter Unterschied der Pre/In Order und Post/In Order Rekonstruktion, ist die Reihenfolge, in denen die Arrays preOrder bzw. postOrder abgearbeitet werden. Da bei einer Pre Order Ausgabe zuerst linke Teilbäume ausgegeben werden, sind die nächsten Elemente ab Index 1 immer Knoten des linken Teilbaums, während darauf folgende Elemente dem rechten Teilbaum angehören. Hier kann das Array in normaler Ordnung abgearbeitet werden. Bei einer Post Order Rekonstruktion stehen die Wurzeln immer an der letzten Stelle des zu betrachtenden Teilbereiches. Das Array wird rückwärts abgearbeitet, d.h. von $l$ bis $0$.

Pre/Post Order Rekonstruktion

Das eine Rekonstruktion alleinig mit Pre/Post Order Bäumen nicht möglich ist, soll folgendes Gegenbeispiel illustrieren.

Laufzeitkomplexität

Bei beiden Algorithmen gibt es, weil die Elemente von preOrder bzw. postOrder ausgeschöpft werden, eine Rekursionstiefe von $n$, wobei $n = inOrder.length = preOrder.length = postOrder.length$ für Bäume mit gleich vielen Knoten. Bei jedem rekursiven Aufruf muss ein entsprechendes Element des preOrder bzw postOrder Arrays im inOrder Array gefunden werden, wobei immer nur im Interval $[0, n)$ gesucht wird. Das Interval wird bei jedem rekursiven Aufruf auf eine geordnete Teilmenge des Arrays inOrder beschränkt. Wie klein diese Teilmengen mit rekursiven Aufrufen werden, hängt von der Ausartung des Baumes ab, so dass bei einem balancierter Baum die Teilmengen immer $(n-1)/2$ des ursprünglichen $n$ betragen. Daher bildet eine Ausartung des Baumes zu einer linearen Liste einen worst-case Fall, da die Teilmengen immer $n-1)$ des ursprünglichen $n$ betragen. Somit ergibt sich eine Laufzeitkomplexität im best-case von $\Omega(n*log_2(n))$ und eine Laufzeitkomplexit im worst-case von $O(n^2)$.