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:

Litteratur

Länkar