Als Lowest Common Ancestor (LCA) oder „letzter gemeinsamer Vorfahre“ wird in der Informatik und Graphentheorie ein Ermittlungskonzept bezeichnet, das einen gegebenen gewurzelten Baum von Datenstrukturen effizient vorverarbeitet, sodass anschließend Anfragen nach dem letzten gemeinsamen Vorfahren für beliebige Knotenpaare in 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).

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.

Entwicklung (Geschichte)

Das LCA-Problem wurde 1973 erstmals von Alfred Aho, John Hopcroft und 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.

Anwendungsgebiete

Die LCA-Ermittlung kann angewendet werden, um den LCA von Gen-Bäumen (Bioinformatik) zu ermitteln.

Weblinks

• Ermittlung des Lowest Common Ancestors mithilfe des RMQ-Algorithmus

Einzelnachweise

1. ↑ Effiziente Berechnung vom letzten gemeinsamen Vorfahren und Anwendungen – FU Berlin fu-berlin.de – abgerufen am 22. Januar 2023
2. ↑ Algorithmen zum Ermitteln des Lowest Common Ancestor (LCA) – FU Berlin (PDF, 638 kB) fu-berlin.de – abgerufen am 10. März 2013
3. ↑ Jana Hertel, Peter F. Stadler: BIOINF 15-037: The Expansion of Animal MicroRNA Families Revisited. In: bioinf.uni-leipzig.de. Bioinformatics Leipzig, abgerufen am 22. Januar 2023 (englisch).