Minst gemensamma förfader

Den minst gemensamma förfadern ( lägsta gemensamma förfadern ) till hörnen u och v i det rotade trädet T är den vertex som är längst bort från trädets rot, som ligger på båda vägarna från u och v till roten, dvs. är förfader till båda hörn. Den allmänt accepterade förkortningen är LCA från engelska.  lägsta (minst) gemensamma anfader .

Algoritmer

Den enklaste, mest naiva algoritmen för att hitta den minst gemensamma förfadern är att beräkna djupen av u och v och gradvis arbeta dig upp i trädet från varje vertex tills en gemensam vertex hittas:

Procedur LCA( u , v ): h1 := depth( u ) // depth( x ) = djup av vertex x h2 := depth( v ) medan h1 ≠ h2: om h1 > h2: u  := förälder( u ) h1 := h1 - 1 annat : v  := förälder( v ) h2 := h2 - 1 medan u ≠ v : u  := parent( u ) // parent( x ) = omedelbar förfader till x v  := parent( v ) returnera u

Körtiden för denna algoritm är O ( h ), där h  är höjden på trädet. Dessutom kan O ( n ) tidsförbehandling krävas för att hitta den omedelbara förfadern till alla noder i trädet (men denna struktur finns vanligtvis redan i trädet).

Det finns dock snabbare algoritmer:

• Binär lyftalgoritm som kräver O ( n log n ) förbearbetningstid och O (log n ) frågetid (beräknar den minst gemensamma förfadern av två hörn). Tanken är att för varje vertex beräkna en förfader 2k bort från den för alla k , och använda den informationen för att påskynda den naiva algoritmen ovan.
• Tarjans algoritm i tid O ( n α ( n ) + m ), där m är antalet frågor. Detta är dock den så kallade offlinealgoritmen: den kräver att alla förfrågningar är tillgängliga i förväg, innan arbetet påbörjas.
• Bender-Farah-Colton-algoritm som kräver O ( n ) förbearbetningstid och O (1) frågetid.

Litteratur

• Bender M., Farach-Colton M. LCA-problemet återbesökt  // Proceedings of the 4th Latin American Symposium on Theoretical Informatics. - Springer-Verlag, 2000. - Vol. 1776. - S. 88-94. - doi : 10.1007/10719839_9 .

Länkar

• Implementering av Bender-Farah-Colton-algoritmen av David Epstein