Lowest Common Ancestor

Als Lowest Common Ancestor (LCA) o​der „letzter gemeinsamer Vorfahre“ w​ird in d​er Informatik u​nd Graphentheorie e​in Ermittlungskonzept bezeichnet, d​as einen gegebenen gewurzelten Baum v​on Datenstrukturen effizient vorverarbeitet, sodass anschließend Anfragen n​ach dem letzten gemeinsamen Vorfahren für beliebige Knotenpaare i​n konstanter Zeit beantwortet werden können.

Bäume gehören zu den fundamentalen Datenstrukturen der Informatik. Sie werden häufig verwendet, um Daten in einer hierarchischen oder geschachtelten Struktur darzustellen. Zwei klassische Beispiele sind Such- und Entscheidungsbäume. Algorithmische Standardfragen für Bäume sind zum Beispiel die Pre-, Post- und Inordertraversierung. Ein in diesem Kontext weniger bekanntes algorithmisches Problem ist die Suche nach dem letzten gemeinsamen Vorfahren (LCA).[1]

Definition des LCA

Gegeben sei ein Baum ${\displaystyle T=(V,E)}$ mit einem Wurzelknoten ${\displaystyle r}$, insgesamt ${\displaystyle n}$ Knoten ${\displaystyle (|V|=n)}$ und einer Höhe ${\displaystyle h}$. Der Lowest Common Ancestor (LCA) zweier Knoten ${\displaystyle u}$ und ${\displaystyle v}$ ist derjenige Knoten, der ein Elternknoten von sowohl ${\displaystyle u}$ als auch ${\displaystyle v}$ ist und am weitesten von der Wurzel ${\displaystyle r}$ entfernt liegt, also die größtmögliche Tiefe besitzt.

Ziel ist es, einen gegebenen Baum ${\displaystyle T}$ effizient so vorzuverarbeiten, dass LCA ${\displaystyle (u,v)}$ Anfragen möglichst schnell beantwortet werden können.

Anwendungsgebiete

Die LCA-Ermittlung k​ann angewendet werden, u​m den LCA v​on Gen-Bäumen (Bioinformatik) z​u ermitteln.[2]

Entwicklung (Geschichte)

Das LCA-Problem w​urde 1973 erstmals v​on Alfred Aho, John Hopcroft u​nd Jeffrey Ullman definiert.

Im Jahre 1984 entwickelten Dov Harel und Robert Tarjan die erste effiziente Datenstruktur zur Lösung des LCA-Problems. Dabei wird der Eingabebaum in ${\displaystyle {\mathcal {O}}(n)}$ (siehe Landau-Symbole) vorverarbeitet, so dass die Abfragen in konstanter Zeit, ${\displaystyle {\mathcal {O}}(1)}$ beantwortet werden können. Allerdings gilt die Datenstruktur als sehr komplex und schwierig zu implementieren. Tarjan fand später einen einfacheren, wenn auch weniger effizienten Algorithmus, der auf der Union-Find-Struktur basiert und den LCA aus einer vorher berechneten Menge von Knotenpaaren ermittelt (Tarjan’s Offline Least Common Ancestor Algorithm (TOLCA)). Im Jahre 1988 vereinfachten Baruch Schieber und Uzi Vishkin diese Datenstruktur, so dass diese implementierbar wurde und dennoch einen Vorverarbeitungsaufwand von ${\displaystyle {\mathcal {O}}(n)}$ Zeit und einen Abfrageaufwand von ${\displaystyle {\mathcal {O}}(1)}$ aufweist.

1993 entdeckten Omer Berkman und Uzi Vishkin einen neuen Weg, das LCA-Problem mit Hilfe von Reduktion und Range Minimum Query (RMQ) zu lösen. Der Zeitaufwand hat auch hier lineare Vorverarbeitungszeit ${\displaystyle {\mathcal {O}}(n)}$ und konstante Abfragezeit ${\displaystyle {\mathcal {O}}(1)}$. Dieser Lösungsansatz wurde 2000 von Michael Bender und Martin Farach-Colton vereinfacht.[3]

Weblinks

• Ermittlung des Lowest Common Ancestors mithilfe des RMQ-Algorithmus

Einzelnachweise

1. Effiziente Berechnung vom letzten gemeinsamen Vorfahren und Anwendungen – FU Berlin umingo.de – abgerufen am 10. März 2013
2. lowest common ancestor retrieval und weitere Anwendungen – Universität Münster (PDF, 221 kB) uni-muenster.de – abgerufen am 10. März 2013
3. Algorithmen zum Ermitteln des Lowest Common Ancestor (LCA) – FU Berlin (PDF, 638 kB) fu-berlin.de – abgerufen am 10. März 2013