Lowest Common Ancestor

Als Lowest Common Ancestor oder Least Common Ancestor (LCA), deutsch „letzter gemeinsamer Vorfahre“, wird in der Informatik und Graphentheorie ein Ermittlungskonzept bezeichnet, das einen gegebenen gewurzelten Baum von Datenstrukturen effizient vor­ver­arbei­tet, 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 Standard­fragen 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 ge­mein­samen Vorfahren (LCA).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.