The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root.

PropertyValue
dbpprop:abstract
  • The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). 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 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, in constant time per query after a linear time preprocessing stage.
  • Najniższy wspólny przodek (ang. Lowest Common Ancestor, w skrócie LCA) - w teorii grafów 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. Sposobem obliczania dla dwóch wierzchołków drzewa ich najniższego wspólnego przodka jest Algorytm Tarjana
  • Наименьший общий предок вершин u в v в корневом дереве T — наиболее удалённая от корня дерева вершина, лежащая на обоих путях от u и v до корня, т. е. являющаяся предком обоих вершин. Общепринятое сокращение — LCA от англ. lowest (least) common ancestor.
dbpprop:hasPhotoCollection
dbpprop:reference
dbpprop:relatedInstance
dbpprop:twoOtherUsesProperty
  • a common ancestor of all life forms
  • last universal ancestor
  • lowest common ancestors in graph theory and computer science
  • most recent common ancestor
  • the common ancestor of a set of species in evolutionary trees
dbpprop:wikiPageUsesTemplate
rdfs:comment
  • The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root.
  • Najniższy wspólny przodek (ang. Lowest Common Ancestor, w skrócie LCA) - w teorii grafów 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. Sposobem obliczania dla dwóch wierzchołków drzewa ich najniższego wspólnego przodka jest Algorytm Tarjana
  • Наименьший общий предок вершин u в v в корневом дереве T — наиболее удалённая от корня дерева вершина, лежащая на обоих путях от u и v до корня, т. е. являющаяся предком обоих вершин. Общепринятое сокращение — LCA от англ. lowest (least) common ancestor.
rdfs:label
  • Lowest common ancestor
  • Najniższy wspólny przodek
  • Наименьший общий предок
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of