Wie finde ich den ersten gemeinsamen Vorfahren eines Knotens in einem Binärbaum?

Ok, fangen wir damit an, herauszufinden, was der schlimmste Fall für diesen Algorithmus wäre. covers durchsucht den Baum von links nach rechts, sodass Sie das Worst-Case-Verhalten erhalten, wenn der Knoten, nach dem Sie suchen, das Blatt ganz rechts ist oder sich nicht im Teilbaum befindet. An diesem Punkt haben Sie alle Knoten im Teilbaum besucht, also ist covers O (n) , wobei n die Anzahl der Knoten im Baum ist.

Ähnlich verhält es sich mit commonAncestor im Worst-Case-Verhalten, wenn der erste gemeinsame Vorfahre von p und q in der Baumstruktur ganz rechts liegt. In diesem Fall wird zuerst covers zweimal aufgerufen, um in beiden Fällen das schlechteste Zeitverhalten zu erhalten. Es wird sich dann wieder auf dem rechten Teilbaum aufrufen, der bei einem ausgeglichenen Baum die Größe n/2 hat.

Wenn der Baum ausgeglichen ist, können wir die Laufzeit anhand der Rekursionsbeziehung T(n) = T(n/2) + O(n) beschreiben. Unter Verwendung des Hauptsatzes erhalten wir die Antwort T(n) = O(n) für einen ausgeglichenen Baum.

Wenn der Baum jetzt nicht ist, können wir im schlimmsten Fall die Größe des Unterbaums für jeden rekursiven Aufruf um 1 reduzieren, was die Wiederholung T(n) = T(n-1) + O(n) ergibt. Die Lösung für diese Wiederholung ist T(n) = O(n^2) .

Sie können jedoch bessere Ergebnisse erzielen.

Anstatt beispielsweise einfach zu bestimmen, welcher Teilbaum p oder q mit cover enthält, legen wir den gesamten Pfad zu p und q fest. Das dauert O(n) genau wie cover , wir halten nur mehr Informationen. Durchquere diese Pfade nun parallel und halte dort an, wo sie auseinander gehen. Dies ist immer O(n) .

Wenn Sie Zeiger von jedem Knoten zu ihrem Elternteil haben, können Sie dies sogar verbessern, indem Sie die Pfade "von unten nach oben" erzeugen und Ihnen O(log n) für einen ausgeglichenen Baum geben.

Beachten Sie, dass dies ein Raum-Zeit-Kompromiss ist, da Ihr Code O(1) Leerzeichen benötigt, dieser Algorithmus jedoch O(log n) Leerzeichen für eine ausgeglichene Struktur und O(n) Leerzeichen im Allgemeinen benötigt.

Als hammars Antwort zeigt, dass Ihr Algorithmus ziemlich ineffizient ist, da viele Operationen wiederholt werden.

Ich würde einen anderen Ansatz wählen: Anstatt für jeden potentiellen Wurzelknoten zu testen, wenn die zwei gegebenen Knoten nicht im selben Unterbaum sind (und somit der erste gemeinsame Vorfahre ist), würde ich die Pfade von der Wurzel zu bestimmen die zwei gegebenen Knoten und vergleichen Sie die Knoten. Der letzte gemeinsame Knoten auf den Pfaden von der Wurzel nach unten ist dann auch der erste gemeinsame Vorfahre.

Hier ist eine (ungetestete) Implementierung in Java:

Sowohl pathToNode als auch commonAncestor stehen in O (n).