imported>ⵓ: +https ⇄

2025-12-04T19:22:48Z

+https ⇄

Neue Seite

[[Datei:Lowest common ancestor.svg|mini|hochkant=0.65|In diesem Baum ist der LCA der Knoten ''x'' und ''y'' in Dunkelgrün markiert. Andere gemeinsame Vorfahren sind in Hellgrün dargestellt.]]
Als '''Lowest Common Ancestor''' oder '''Least Common Ancestor''' ('''LCA'''), deutsch ''„letzter gemeinsamer [[Out-Tree#Vorfahr|Vorfahre]]“'', wird in der [[Informatik]] und [[Graphentheorie]] ein Ermittlungskonzept bezeichnet, das einen gegebenen gewurzelten [[Binärbaum|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).<ref>[https://www.mi.fu-berlin.de/inf/groups/ag-ti/theses/bachelor_finished/kresse_antonia/index.html ''Effiziente Berechnung vom letzten gemeinsamen Vorfahren und Anwendungen – FU Berlin'']. Auf: fu-berlin.de – abgerufen am 22. Januar 2023</ref>

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

Ziel ist es, einen gegebenen Baum <math>T</math> effizient so vorzuverarbeiten, dass LCA <math>(u,v)</math> 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 <math>\mathcal{O}(n)</math> (siehe [[Landau-Symbole]]) vorverarbeitet, so dass die Abfragen in konstanter Zeit, <math>\mathcal{O}(1)</math> 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 <math>\mathcal{O}(n)</math> Zeit und einen Abfrageaufwand von <math>\mathcal{O}(1)</math> aufweist.

1993 entdeckten [[Omer Berkman]] und Uzi Vishkin einen neuen Weg, das LCA-Problem mit Hilfe von Reduktion und [[Range Minimum Query|Range Minimum Query (RMQ)]] zu lösen. Der Zeitaufwand hat auch hier lineare Vorverarbeitungszeit <math>\mathcal{O}(n)</math> und konstante Abfragezeit <math>\mathcal{O}(1)</math>. Dieser Lösungsansatz wurde 2000 von [[Michael Bender]] und [[Martin Farach-Colton]] vereinfacht.<ref name="Bender2000" /><ref>[https://page.mi.fu-berlin.de/alt/vorlesungen/sem09/Algorithmen%20zum%20Ermitteln%20des%20Lowest%20Common%20Ancestor_M2.pdf ''Algorithmen zum Ermitteln des Lowest Common Ancestor (LCA) – FU Berlin''] (PDF, 638 kB) fu-berlin.de – abgerufen am 10. März 2013</ref>

== Anwendungsgebiete ==
Die LCA-Ermittlung kann angewendet werden, um den LCA (Last common ancestor, auch [[Most recent common ancestor]], MRCA) von [[Phylogenetischer Baum|Gen-Bäumen]] ([[Bioinformatik]]) zu ermitteln.<ref>{{Internetquelle |autor=Jana Hertel, Peter F. Stadler |url=https://www.bioinf.uni-leipzig.de/publications/supplements/15-037 |titel=BIOINF 15-037: The Expansion of Animal MicroRNA Families Revisited |werk=bioinf.uni-leipzig.de |hrsg=Bioinformatics Leipzig |sprache=en |abruf=2023-01-22}}</ref>

== Verallgemeinerung ==
[[Datei:Lowest common ancestors in a DAG.svg|mini|hochkant=0.65|Ein [[Gerichteter azyklischer Graph|gerichteter azyklischer Graph]] mit den gemeinsamen Vorfahren von ''x'' und ''y'' in Hellgrün und ihren LCAs in Dungkelggrün.]]
Ursprünglich wurde der Begriff des LCA im Zusammenhang mit Bäumen untersucht, doch kann er auch für [[Gerichteter azyklischer Graph|gerichtete azyklische Graphen]] ({{enS|directed acyclic graphs}}, DAGs) definiert werden. Dabei wird davon ausgegangen, dass die Kanten des DAG von den Eltern zu den Kindern führen. Die ursprüngliche Definition von Aït-Kaci ''et al.'' (1989)<ref name="Ait1998" /> wurde von Bender ''et al.'' (2005) vereinfacht.<ref name="Bender2005" />

== Weblinks ==
* [http://www.it-cow.de/post/Ermittlung-des-Lowest-Common-Ancestors-mithilfe-des-RMQ-Algorithmus-WIP.aspx Ermittlung des Lowest Common Ancestors mithilfe des RMQ-Algorithmus]

== Einzelnachweise ==
<references>
<ref name="Ait1998">
{{cite journal |first1=H. |last1=Aït-Kaci |first2=R. |last2=Boyer |first3=P. |last3=Lincoln |first4=R. |last4=Nasr |title=Efficient implementation of lattice operations |journal=ACM Transactions on Programming Languages and Systems |volume=11 |issue=1 |pages=115–146 |date=1989  |doi=10.1145/59287.59293 |language=en }}
</ref>
<ref name="Bender2000">
Michael A. Bender, Martin Farach-Colton: ''The LCA problem revisited.'' In: ''Proceedings of the 4th Latin American Symposium on Theoretical Informatics.'' Serie: ''Lecture Notes in Computer Science'', Band 1776, Springer-Verlag, 2000, ISBN 978-3-540-67306-4, S. 88–94; [[doi:10.1007/10719839_9]] ({{enS}}).
</ref>
<ref name="Bender2005">
{{cite journal |last1=Bender |first1=Michael A. |first2=Martín |last2=Farach-Colton |first3=Giridhar |last3=Pemmasani |first4=Steven |last4=Skiena |first5=Pavel |last5=Sumazin |title=Lowest common ancestors in trees and directed acyclic graphs |journal=Journal of Algorithms |volume=57 |issue=2 |year=2005 |pages=75–94  |doi=10.1016/j.jalgor.2005.08.001 |language=en }}
</ref>
</references>

[[Kategorie:Graphentheorie]]
[[Kategorie:Theoretische Informatik]]

Lowest Common Ancestor - Versionsgeschichte

imported>ⵓ: +https ⇄