Nejméně společný předek

Nejméně společný předek ( nejnižší společný předek ) vrcholů u a v v kořenovém stromu T je vrchol nejvzdálenější od kořene stromu, ležící na obou cestách od u a v ke kořenu, tj. je předkem obou. vrcholy. Obecně přijímaná zkratka je LCA z angličtiny.  nejnižší (nejméně) společný předek .

Algoritmy

Nejjednodušší a nejnaivnější algoritmus pro nalezení nejméně společného předka je vypočítat hloubky u a v a postupně se propracovávat ve stromu od každého vrcholu, dokud nenajdete společný vrchol:

Postup LCA( u , v ): h1 := hloubka ( u ) // hloubka ( x ) = hloubka vrcholu x h2 := hloubka ( v ) zatímco h1 ≠ h2: pokud h1 > h2: u  := rodič ( u ) h1 := h1 - 1 else : v  := parent( v ) h2 := h2 - 1 zatímco u ≠ v : u  := rodič ( u ) // rodič ( x ) = bezprostřední předek x v  : = rodič ( v ) vrátit u

Doba běhu tohoto algoritmu je O ( h ), kde h  je výška stromu. Kromě toho může být vyžadováno předzpracování času O ( n ) k nalezení bezprostředního předka všech uzlů ve stromu (tato struktura je však ve stromu obvykle již přítomna).

Existují však rychlejší algoritmy:

• Binární liftingový algoritmus vyžadující O ( n log n ) čas předběžného zpracování a O ( log n ) dotazovací čas (výpočet nejmenšího společného předka dvou vrcholů). Cílem je vypočítat pro každý vrchol předchůdce 2k od něj pro všechna k a použít tyto informace k urychlení výše uvedeného naivního algoritmu.
• Tarjanův algoritmus v čase O ( n α ( n ) + m ), kde m je počet dotazů. Toto je však takzvaný offline algoritmus: vyžaduje, aby všechny požadavky byly k dispozici předem, než začne práce.
• Algoritmus Bender-Farah-Colton vyžadující O ( n ) čas předběžného zpracování a O (1) čas dotazu.

Literatura

• Bender M., Farach-Colton M. The LCA problem revisited  // Proceedings of the 4th Latin American Symposium on Theoretical Informatics. - Springer-Verlag, 2000. - Sv. 1776. - S. 88-94. - doi : 10.1007/10719839_9 .

Odkazy

• Implementace Bender-Farah-Coltonova algoritmu od Davida Epsteina