| dbo:abstract
|
- 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). (de)
- El ancestro común más bajo (ACB) es un concepto dentro de la Teoría de grafos y Ciencias de la computación. Sea T un árbol con raíz y n nodos. El ancestro común más bajo entre dos nodos v y w se define como el nodo más bajo en T que tiene a v y w como descendientes (donde se permite a un nodo ser descendiente de él mismo). El ACB de v y w en T es el ancestro compartido de v y w que está localizado más lejos de la raíz. El cómputo del ancestro común más bajo puede ser útil, por ejemplo, como parte de un procedimiento para determinar la distancia entre pares de nodos en un árbol: la distancia de v a w puede ser calculada como la distancia desde la raíz hasta v, sumada con la distancia desde la raíz hasta w, menos dos veces la distancia desde la raíz hasta su ancestro común más bajo. En una estructura de datos árbol donde cada nodo referencia a su padre, el ancestro común más bajo puede ser determinado de forma muy simple encontrando la primera intersección de los caminos desde v and w hasta la raíz. En general, el tiempo computacional requerido por este algoritmo es O(h) donde h es la altura del árbol (longitud del camino más largo desde una hoja hasta la raíz). Sin embargo, existen muchos algoritmos para procesar árboles con los que el ancestro común más bajo puede ser encontrado de forma más rápida. Se puede buscar en tiempo constante por pregunta después de un preprocesamiento en tiempo lineal. Sin preprocesamiento se puede mejorar el tiempo de cómputo del algoritmo ingenuo hasta O(log h) almacenando los caminos a través del árbol usando skew-binary random access lists, premitiendo aún al árbol ser extendido en tiempo constante (Edward Kmett (2012)). (es)
- In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor). The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor. In ontologies, the lowest common ancestor is also known as the least common ancestor. In a tree data structure where each node points to its parent, the lowest common ancestor can be easily determined by finding the first intersection of the paths from v and w to the root. In general, the computational time required for this algorithm is O(h) where h is the height of the tree (length of longest path from a leaf to the root). However, there exist several algorithms for processing trees so that lowest common ancestors may be found more quickly. Tarjan's off-line lowest common ancestors algorithm, for example, preprocesses a tree in linear time to provide constant-time LCA queries. In general DAGs, similar algorithms exist, but with super-linear complexity. (en)
- En théorie des graphes, le plus petit ancêtre commun de deux nœuds d'un arbre est le nœud le plus bas dans l'arbre (le plus profond) ayant ces deux nœuds pour descendants. Le terme en anglais est Lowest Common Ancestor (LCA). Les expressions premier ancêtre commun et plus proche ancêtre commun sont aussi utilisées. Divers algorithmes ont été inventés pour trouver rapidement le plus petit ancêtre commun. (fr)
- Najniższy wspólny przodek (ang. lowest common ancestor, LCA) – najniższym wspólnym przodkiem dwóch wierzchołków d oraz e w ukorzenionym drzewie T jest taki rodzic wierzchołków d oraz e, którego poziom w drzewie T jest największy. (pl)
- Наименьший общий предок (нижайший общий предок) вершин u и v в корневом дереве T — наиболее удалённая от корня дерева вершина, лежащая на обоих путях от u и v до корня, т. е. являющаяся предком обеих вершин. Общепринятое сокращение — LCA от англ. lowest (least) common ancestor. (ru)
- Найменший спільний предок вершин та в кореневому дереві — найбільш віддалена від кореня дерева вершина, яка лежить на обидвох шляхах від та до кореня дерева, тобто є предком обидвох вершин. (uk)
- 在图论和计算机科学中，最近公共祖先（英語：lowest common ancestor）是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。 最近公共祖先是两个节点所有公共祖先中离根节点最远的，计算最近公共祖先和根节点的长度往往是有用的。比如为了计算树中两个节点v和w之间的距离，可以使用以下方法：分别计算由v到根节点和w到根节点的距离，两者之和减去最近公共祖先到根节点的距离的两倍即可得到v到w的距离。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 24628 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:author1Link
|
- Alfred Aho (en)
- Baruch Schieber (en)
- Daniel Sleator (en)
|
| dbp:author2Link
|
- John Hopcroft (en)
- Robert Tarjan (en)
- Martin Farach-Colton (en)
- Uzi Vishkin (en)
|
| dbp:author3Link
| |
| dbp:first
|
- John (en)
- Martin (en)
- Michael (en)
- Robert (en)
- Jeffrey (en)
- Alfred (en)
- Omer (en)
- Baruch (en)
- Uzi (en)
- Dov (en)
|
| dbp:last
|
- Sleator (en)
- Bender (en)
- Aho (en)
- Schieber (en)
- Harel (en)
- Ullman (en)
- Vishkin (en)
- Berkman (en)
- Hopcroft (en)
- Tarjan (en)
- Farach-Colton (en)
|
| dbp:wikiPageUsesTemplate
| |
| dbp:year
|
- 1973 (xsd:integer)
- 1983 (xsd:integer)
- 1984 (xsd:integer)
- 1988 (xsd:integer)
- 1993 (xsd:integer)
- 2000 (xsd:integer)
|
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En théorie des graphes, le plus petit ancêtre commun de deux nœuds d'un arbre est le nœud le plus bas dans l'arbre (le plus profond) ayant ces deux nœuds pour descendants. Le terme en anglais est Lowest Common Ancestor (LCA). Les expressions premier ancêtre commun et plus proche ancêtre commun sont aussi utilisées. Divers algorithmes ont été inventés pour trouver rapidement le plus petit ancêtre commun. (fr)
- Najniższy wspólny przodek (ang. lowest common ancestor, LCA) – najniższym wspólnym przodkiem dwóch wierzchołków d oraz e w ukorzenionym drzewie T jest taki rodzic wierzchołków d oraz e, którego poziom w drzewie T jest największy. (pl)
- Наименьший общий предок (нижайший общий предок) вершин u и v в корневом дереве T — наиболее удалённая от корня дерева вершина, лежащая на обоих путях от u и v до корня, т. е. являющаяся предком обеих вершин. Общепринятое сокращение — LCA от англ. lowest (least) common ancestor. (ru)
- Найменший спільний предок вершин та в кореневому дереві — найбільш віддалена від кореня дерева вершина, яка лежить на обидвох шляхах від та до кореня дерева, тобто є предком обидвох вершин. (uk)
- 在图论和计算机科学中，最近公共祖先（英語：lowest common ancestor）是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。 最近公共祖先是两个节点所有公共祖先中离根节点最远的，计算最近公共祖先和根节点的长度往往是有用的。比如为了计算树中两个节点v和w之间的距离，可以使用以下方法：分别计算由v到根节点和w到根节点的距离，两者之和减去最近公共祖先到根节点的距离的两倍即可得到v到w的距离。 (zh)
- 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. (de)
- El ancestro común más bajo (ACB) es un concepto dentro de la Teoría de grafos y Ciencias de la computación. Sea T un árbol con raíz y n nodos. El ancestro común más bajo entre dos nodos v y w se define como el nodo más bajo en T que tiene a v y w como descendientes (donde se permite a un nodo ser descendiente de él mismo). Se puede buscar en tiempo constante por pregunta después de un preprocesamiento en tiempo lineal. (es)
- In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor). (en)
|
| rdfs:label
|
- Lowest Common Ancestor (de)
- Ancestro común más bajo (es)
- Plus petit ancêtre commun (fr)
- Lowest common ancestor (en)
- Najniższy wspólny przodek (pl)
- Наименьший общий предок (ru)
- Найменший спільний предок (uk)
- 最近公共祖先 (图论) (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
