"\u6700\u8FD1\u516C\u5171\u7956\u5148 (\u56FE\u8BBA)"@zh . "1983"^^ . . "El ancestro com\u00FAn m\u00E1s bajo (ACB) es un concepto dentro de la Teor\u00EDa de grafos y Ciencias de la computaci\u00F3n. Sea T un \u00E1rbol con ra\u00EDz y n nodos. El ancestro com\u00FAn m\u00E1s bajo entre dos nodos v y w se define como el nodo m\u00E1s bajo en T que tiene a v y w como descendientes (donde se permite a un nodo ser descendiente de \u00E9l mismo). Se puede buscar en tiempo constante por pregunta despu\u00E9s de un preprocesamiento en tiempo lineal."@es . . . "Uzi Vishkin"@en . . "Baruch"@en . "Baruch Schieber"@en . "1973"^^ . "\u5728\u56FE\u8BBA\u548C\u8BA1\u7B97\u673A\u79D1\u5B66\u4E2D\uFF0C\u6700\u8FD1\u516C\u5171\u7956\u5148\uFF08\u82F1\u8A9E\uFF1Alowest common ancestor\uFF09\u662F\u6307\u5728\u4E00\u4E2A\u6811\u6216\u8005\u6709\u5411\u65E0\u73AF\u56FE\u4E2D\u540C\u65F6\u62E5\u6709v\u548Cw\u4F5C\u4E3A\u540E\u4EE3\u7684\u6700\u6DF1\u7684\u8282\u70B9\u3002\u5728\u8FD9\u91CC\uFF0C\u6211\u4EEC\u5B9A\u4E49\u4E00\u4E2A\u8282\u70B9\u4E5F\u662F\u5176\u81EA\u5DF1\u7684\u540E\u4EE3\uFF0C\u56E0\u6B64\u5982\u679Cv\u662Fw\u7684\u540E\u4EE3\uFF0C\u90A3\u4E48w\u5C31\u662Fv\u548Cw\u7684\u6700\u8FD1\u516C\u5171\u7956\u5148\u3002 \u6700\u8FD1\u516C\u5171\u7956\u5148\u662F\u4E24\u4E2A\u8282\u70B9\u6240\u6709\u516C\u5171\u7956\u5148\u4E2D\u79BB\u6839\u8282\u70B9\u6700\u8FDC\u7684\uFF0C\u8BA1\u7B97\u6700\u8FD1\u516C\u5171\u7956\u5148\u548C\u6839\u8282\u70B9\u7684\u957F\u5EA6\u5F80\u5F80\u662F\u6709\u7528\u7684\u3002\u6BD4\u5982\u4E3A\u4E86\u8BA1\u7B97\u6811\u4E2D\u4E24\u4E2A\u8282\u70B9v\u548Cw\u4E4B\u95F4\u7684\u8DDD\u79BB\uFF0C\u53EF\u4EE5\u4F7F\u7528\u4EE5\u4E0B\u65B9\u6CD5\uFF1A\u5206\u522B\u8BA1\u7B97\u7531v\u5230\u6839\u8282\u70B9\u548Cw\u5230\u6839\u8282\u70B9\u7684\u8DDD\u79BB\uFF0C\u4E24\u8005\u4E4B\u548C\u51CF\u53BB\u6700\u8FD1\u516C\u5171\u7956\u5148\u5230\u6839\u8282\u70B9\u7684\u8DDD\u79BB\u7684\u4E24\u500D\u5373\u53EF\u5F97\u5230v\u5230w\u7684\u8DDD\u79BB\u3002"@zh . . . . . . . . . . . . "7196522"^^ . . "\u041D\u0430\u0438\u043C\u0435\u043D\u044C\u0448\u0438\u0439 \u043E\u0431\u0449\u0438\u0439 \u043F\u0440\u0435\u0434\u043E\u043A (\u043D\u0438\u0436\u0430\u0439\u0448\u0438\u0439 \u043E\u0431\u0449\u0438\u0439 \u043F\u0440\u0435\u0434\u043E\u043A) \u0432\u0435\u0440\u0448\u0438\u043D u \u0438 v \u0432 \u043A\u043E\u0440\u043D\u0435\u0432\u043E\u043C \u0434\u0435\u0440\u0435\u0432\u0435 T \u2014 \u043D\u0430\u0438\u0431\u043E\u043B\u0435\u0435 \u0443\u0434\u0430\u043B\u0451\u043D\u043D\u0430\u044F \u043E\u0442 \u043A\u043E\u0440\u043D\u044F \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u0435\u0440\u0448\u0438\u043D\u0430, \u043B\u0435\u0436\u0430\u0449\u0430\u044F \u043D\u0430 \u043E\u0431\u043E\u0438\u0445 \u043F\u0443\u0442\u044F\u0445 \u043E\u0442 u \u0438 v \u0434\u043E \u043A\u043E\u0440\u043D\u044F, \u0442. \u0435. \u044F\u0432\u043B\u044F\u044E\u0449\u0430\u044F\u0441\u044F \u043F\u0440\u0435\u0434\u043A\u043E\u043C \u043E\u0431\u0435\u0438\u0445 \u0432\u0435\u0440\u0448\u0438\u043D. \u041E\u0431\u0449\u0435\u043F\u0440\u0438\u043D\u044F\u0442\u043E\u0435 \u0441\u043E\u043A\u0440\u0430\u0449\u0435\u043D\u0438\u0435 \u2014 LCA \u043E\u0442 \u0430\u043D\u0433\u043B. lowest (least) common ancestor."@ru . . "Lowest common ancestor"@en . . "Robert Tarjan"@en . "Farach-Colton"@en . . "Lowest Common Ancestor"@de . . . . "Sleator"@en . "1111669741"^^ . . . . . "Als Lowest Common Ancestor (LCA) oder \u201Eletzter gemeinsamer Vorfahre\u201C wird in der Informatik und Graphentheorie ein Ermittlungskonzept bezeichnet, das einen gegebenen gewurzelten Baum von Datenstrukturen effizient vorverarbeitet, sodass anschlie\u00DFend Anfragen nach dem letzten gemeinsamen Vorfahren f\u00FCr beliebige Knotenpaare in konstanter Zeit beantwortet werden k\u00F6nnen."@de . "Vishkin"@en . . . . . . "\u041D\u0430\u0438\u043C\u0435\u043D\u044C\u0448\u0438\u0439 \u043E\u0431\u0449\u0438\u0439 \u043F\u0440\u0435\u0434\u043E\u043A"@ru . . "Ancestro com\u00FAn m\u00E1s bajo"@es . . "El ancestro com\u00FAn m\u00E1s bajo (ACB) es un concepto dentro de la Teor\u00EDa de grafos y Ciencias de la computaci\u00F3n. Sea T un \u00E1rbol con ra\u00EDz y n nodos. El ancestro com\u00FAn m\u00E1s bajo entre dos nodos v y w se define como el nodo m\u00E1s bajo en T que tiene a v y w como descendientes (donde se permite a un nodo ser descendiente de \u00E9l mismo). El ACB de v y w en T es el ancestro compartido de v y w que est\u00E1 localizado m\u00E1s lejos de la ra\u00EDz. El c\u00F3mputo del ancestro com\u00FAn m\u00E1s bajo puede ser \u00FAtil, por ejemplo, como parte de un procedimiento para determinar la distancia entre pares de nodos en un \u00E1rbol: la distancia de v a w puede ser calculada como la distancia desde la ra\u00EDz hasta v, sumada con la distancia desde la ra\u00EDz hasta w, menos dos veces la distancia desde la ra\u00EDz hasta su ancestro com\u00FAn m\u00E1s bajo. En una estructura de datos \u00E1rbol donde cada nodo referencia a su padre, el ancestro com\u00FAn m\u00E1s bajo puede ser determinado de forma muy simple encontrando la primera intersecci\u00F3n de los caminos desde v and w hasta la ra\u00EDz. En general, el tiempo computacional requerido por este algoritmo es O(h) donde h es la altura del \u00E1rbol (longitud del camino m\u00E1s largo desde una hoja hasta la ra\u00EDz). Sin embargo, existen muchos algoritmos para procesar \u00E1rboles con los que el ancestro com\u00FAn m\u00E1s bajo puede ser encontrado de forma m\u00E1s r\u00E1pida. Se puede buscar en tiempo constante por pregunta despu\u00E9s de un preprocesamiento en tiempo lineal. Sin preprocesamiento se puede mejorar el tiempo de c\u00F3mputo del algoritmo ingenuo hasta O(log h) almacenando los caminos a trav\u00E9s del \u00E1rbol usando skew-binary random access lists, premitiendo a\u00FAn al \u00E1rbol 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 . "John Hopcroft"@en . "Plus petit anc\u00EAtre commun"@fr . . "Berkman"@en . . "Tarjan"@en . . "Daniel Sleator"@en . . "\u041D\u0430\u0439\u043C\u0435\u043D\u0448\u0438\u0439 \u0441\u043F\u0456\u043B\u044C\u043D\u0438\u0439 \u043F\u0440\u0435\u0434\u043E\u043A"@uk . . . "Aho"@en . "Als Lowest Common Ancestor (LCA) oder \u201Eletzter gemeinsamer Vorfahre\u201C wird in der Informatik und Graphentheorie ein Ermittlungskonzept bezeichnet, das einen gegebenen gewurzelten Baum von Datenstrukturen effizient vorverarbeitet, sodass anschlie\u00DFend Anfragen nach dem letzten gemeinsamen Vorfahren f\u00FCr beliebige Knotenpaare in konstanter Zeit beantwortet werden k\u00F6nnen. B\u00E4ume geh\u00F6ren zu den fundamentalen Datenstrukturen der Informatik. Sie werden h\u00E4ufig verwendet, um Daten in einer hierarchischen oder geschachtelten Struktur darzustellen. Zwei klassische Beispiele sind Such- und Entscheidungsb\u00E4ume. Algorithmische Standardfragen f\u00FCr B\u00E4ume 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 . "\u041D\u0430\u0439\u043C\u0435\u043D\u0448\u0438\u0439 \u0441\u043F\u0456\u043B\u044C\u043D\u0438\u0439 \u043F\u0440\u0435\u0434\u043E\u043A \u0432\u0435\u0440\u0448\u0438\u043D \u0442\u0430 \u0432 \u043A\u043E\u0440\u0435\u043D\u0435\u0432\u043E\u043C\u0443 \u0434\u0435\u0440\u0435\u0432\u0456 \u2014 \u043D\u0430\u0439\u0431\u0456\u043B\u044C\u0448 \u0432\u0456\u0434\u0434\u0430\u043B\u0435\u043D\u0430 \u0432\u0456\u0434 \u043A\u043E\u0440\u0435\u043D\u044F \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u0435\u0440\u0448\u0438\u043D\u0430, \u044F\u043A\u0430 \u043B\u0435\u0436\u0438\u0442\u044C \u043D\u0430 \u043E\u0431\u0438\u0434\u0432\u043E\u0445 \u0448\u043B\u044F\u0445\u0430\u0445 \u0432\u0456\u0434 \u0442\u0430 \u0434\u043E \u043A\u043E\u0440\u0435\u043D\u044F \u0434\u0435\u0440\u0435\u0432\u0430, \u0442\u043E\u0431\u0442\u043E \u0454 \u043F\u0440\u0435\u0434\u043A\u043E\u043C \u043E\u0431\u0438\u0434\u0432\u043E\u0445 \u0432\u0435\u0440\u0448\u0438\u043D."@uk . "Alfred"@en . . "Jeffrey Ullman"@en . . . . "Alfred Aho"@en . . "Martin Farach-Colton"@en . "En th\u00E9orie des graphes, le plus petit anc\u00EAtre commun de deux n\u0153uds d'un arbre est le n\u0153ud le plus bas dans l'arbre (le plus profond) ayant ces deux n\u0153uds pour descendants. Le terme en anglais est Lowest Common Ancestor (LCA). Les expressions premier anc\u00EAtre commun et plus proche anc\u00EAtre commun sont aussi utilis\u00E9es. Divers algorithmes ont \u00E9t\u00E9 invent\u00E9s pour trouver rapidement le plus petit anc\u00EAtre commun."@fr . . "Martin"@en . . "John"@en . . "En th\u00E9orie des graphes, le plus petit anc\u00EAtre commun de deux n\u0153uds d'un arbre est le n\u0153ud le plus bas dans l'arbre (le plus profond) ayant ces deux n\u0153uds pour descendants. Le terme en anglais est Lowest Common Ancestor (LCA). Les expressions premier anc\u00EAtre commun et plus proche anc\u00EAtre commun sont aussi utilis\u00E9es. Divers algorithmes ont \u00E9t\u00E9 invent\u00E9s pour trouver rapidement le plus petit anc\u00EAtre commun."@fr . . . "Najni\u017Cszy wsp\u00F3lny przodek"@pl . . "Michael"@en . . . "Bender"@en . . . . . . "1993"^^ . . "24628"^^ . . . "1984"^^ . . "Najni\u017Cszy wsp\u00F3lny przodek (ang. lowest common ancestor, LCA) \u2013 najni\u017Cszym wsp\u00F3lnym przodkiem dw\u00F3ch wierzcho\u0142k\u00F3w d oraz e w ukorzenionym drzewie T jest taki rodzic wierzcho\u0142k\u00F3w d oraz e, kt\u00F3rego poziom w drzewie T jest najwi\u0119kszy."@pl . . . "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 . "1988"^^ . . . "Dov"@en . "Najni\u017Cszy wsp\u00F3lny przodek (ang. lowest common ancestor, LCA) \u2013 najni\u017Cszym wsp\u00F3lnym przodkiem dw\u00F3ch wierzcho\u0142k\u00F3w d oraz e w ukorzenionym drzewie T jest taki rodzic wierzcho\u0142k\u00F3w d oraz e, kt\u00F3rego poziom w drzewie T jest najwi\u0119kszy."@pl . "\u5728\u56FE\u8BBA\u548C\u8BA1\u7B97\u673A\u79D1\u5B66\u4E2D\uFF0C\u6700\u8FD1\u516C\u5171\u7956\u5148\uFF08\u82F1\u8A9E\uFF1Alowest common ancestor\uFF09\u662F\u6307\u5728\u4E00\u4E2A\u6811\u6216\u8005\u6709\u5411\u65E0\u73AF\u56FE\u4E2D\u540C\u65F6\u62E5\u6709v\u548Cw\u4F5C\u4E3A\u540E\u4EE3\u7684\u6700\u6DF1\u7684\u8282\u70B9\u3002\u5728\u8FD9\u91CC\uFF0C\u6211\u4EEC\u5B9A\u4E49\u4E00\u4E2A\u8282\u70B9\u4E5F\u662F\u5176\u81EA\u5DF1\u7684\u540E\u4EE3\uFF0C\u56E0\u6B64\u5982\u679Cv\u662Fw\u7684\u540E\u4EE3\uFF0C\u90A3\u4E48w\u5C31\u662Fv\u548Cw\u7684\u6700\u8FD1\u516C\u5171\u7956\u5148\u3002 \u6700\u8FD1\u516C\u5171\u7956\u5148\u662F\u4E24\u4E2A\u8282\u70B9\u6240\u6709\u516C\u5171\u7956\u5148\u4E2D\u79BB\u6839\u8282\u70B9\u6700\u8FDC\u7684\uFF0C\u8BA1\u7B97\u6700\u8FD1\u516C\u5171\u7956\u5148\u548C\u6839\u8282\u70B9\u7684\u957F\u5EA6\u5F80\u5F80\u662F\u6709\u7528\u7684\u3002\u6BD4\u5982\u4E3A\u4E86\u8BA1\u7B97\u6811\u4E2D\u4E24\u4E2A\u8282\u70B9v\u548Cw\u4E4B\u95F4\u7684\u8DDD\u79BB\uFF0C\u53EF\u4EE5\u4F7F\u7528\u4EE5\u4E0B\u65B9\u6CD5\uFF1A\u5206\u522B\u8BA1\u7B97\u7531v\u5230\u6839\u8282\u70B9\u548Cw\u5230\u6839\u8282\u70B9\u7684\u8DDD\u79BB\uFF0C\u4E24\u8005\u4E4B\u548C\u51CF\u53BB\u6700\u8FD1\u516C\u5171\u7956\u5148\u5230\u6839\u8282\u70B9\u7684\u8DDD\u79BB\u7684\u4E24\u500D\u5373\u53EF\u5F97\u5230v\u5230w\u7684\u8DDD\u79BB\u3002"@zh . . . . . "Uzi"@en . "Schieber"@en . . . "Jeffrey"@en . "2000"^^ . . . . "Harel"@en . "Hopcroft"@en . . "\u041D\u0430\u0438\u043C\u0435\u043D\u044C\u0448\u0438\u0439 \u043E\u0431\u0449\u0438\u0439 \u043F\u0440\u0435\u0434\u043E\u043A (\u043D\u0438\u0436\u0430\u0439\u0448\u0438\u0439 \u043E\u0431\u0449\u0438\u0439 \u043F\u0440\u0435\u0434\u043E\u043A) \u0432\u0435\u0440\u0448\u0438\u043D u \u0438 v \u0432 \u043A\u043E\u0440\u043D\u0435\u0432\u043E\u043C \u0434\u0435\u0440\u0435\u0432\u0435 T \u2014 \u043D\u0430\u0438\u0431\u043E\u043B\u0435\u0435 \u0443\u0434\u0430\u043B\u0451\u043D\u043D\u0430\u044F \u043E\u0442 \u043A\u043E\u0440\u043D\u044F \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u0435\u0440\u0448\u0438\u043D\u0430, \u043B\u0435\u0436\u0430\u0449\u0430\u044F \u043D\u0430 \u043E\u0431\u043E\u0438\u0445 \u043F\u0443\u0442\u044F\u0445 \u043E\u0442 u \u0438 v \u0434\u043E \u043A\u043E\u0440\u043D\u044F, \u0442. \u0435. \u044F\u0432\u043B\u044F\u044E\u0449\u0430\u044F\u0441\u044F \u043F\u0440\u0435\u0434\u043A\u043E\u043C \u043E\u0431\u0435\u0438\u0445 \u0432\u0435\u0440\u0448\u0438\u043D. \u041E\u0431\u0449\u0435\u043F\u0440\u0438\u043D\u044F\u0442\u043E\u0435 \u0441\u043E\u043A\u0440\u0430\u0449\u0435\u043D\u0438\u0435 \u2014 LCA \u043E\u0442 \u0430\u043D\u0433\u043B. lowest (least) common ancestor."@ru . . "Omer"@en . . . . . . . . . . . . "\u041D\u0430\u0439\u043C\u0435\u043D\u0448\u0438\u0439 \u0441\u043F\u0456\u043B\u044C\u043D\u0438\u0439 \u043F\u0440\u0435\u0434\u043E\u043A \u0432\u0435\u0440\u0448\u0438\u043D \u0442\u0430 \u0432 \u043A\u043E\u0440\u0435\u043D\u0435\u0432\u043E\u043C\u0443 \u0434\u0435\u0440\u0435\u0432\u0456 \u2014 \u043D\u0430\u0439\u0431\u0456\u043B\u044C\u0448 \u0432\u0456\u0434\u0434\u0430\u043B\u0435\u043D\u0430 \u0432\u0456\u0434 \u043A\u043E\u0440\u0435\u043D\u044F \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u0435\u0440\u0448\u0438\u043D\u0430, \u044F\u043A\u0430 \u043B\u0435\u0436\u0438\u0442\u044C \u043D\u0430 \u043E\u0431\u0438\u0434\u0432\u043E\u0445 \u0448\u043B\u044F\u0445\u0430\u0445 \u0432\u0456\u0434 \u0442\u0430 \u0434\u043E \u043A\u043E\u0440\u0435\u043D\u044F \u0434\u0435\u0440\u0435\u0432\u0430, \u0442\u043E\u0431\u0442\u043E \u0454 \u043F\u0440\u0435\u0434\u043A\u043E\u043C \u043E\u0431\u0438\u0434\u0432\u043E\u0445 \u0432\u0435\u0440\u0448\u0438\u043D."@uk . . . "Ullman"@en . . "Robert"@en .