Pages: [1]   Go Down
Print
Author Topic: Esercizio sul "lowest common ancestor"?  (Read 815 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Giovi89
Apprendista Forumista
**
Offline Offline

Posts: 273


« on: 09-03-2010, 17:28:09 »

Salve ragazzi,
per caso sapete fare il seguente esercizio:
 Es. 12 Sia T un albero con n nodi. Si definisce come il piu’
   profondo antenato in comune (LCA, lowest common
   ancestor) tra i due nodi v e w il nodo piu’ profondo in T
   che ha tra i propri discendenti sia v che w (per
   definizione si permette che un nodo sia discendente
   di se stesso). Dati due nodi v e w si dia un algoritmo
   efficiente che ricerchi il LCA di v e w. Dare il tempo
   di esecuzione dell’algoritmo progettato.

Ho capito che presi due nodi qualunque dobbiamo trovare quel nodo che ha come discendenti entrambi i nodi, presi a caso, e che ha una certa distanza dalla radice. I nodi devono appartenere a sottoalberi differenti?
« Last Edit: 09-03-2010, 17:30:47 by Giovi89 » Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.475


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #1 on: 09-03-2010, 17:48:27 »

(per definizione si permette che un nodo sia discendente di se stesso).
Questo intanto ti aiuta a capire che se ci sono due nodi, A e B, con B figlio di A, allora il loro LCA è proprio A (in quanto A è un ancestore di se stesso e anche di B, ed è quello più lontano dalla radice).

Ho capito che presi due nodi qualunque dobbiamo trovare quel nodo che ha come discendenti entrambi i nodi, presi a caso, e che ha una certa distanza dalla radice.
No, non una certa distanza, ma proprio la massima distanza dalla radice .

I nodi devono appartenere a sottoalberi differenti?
No, direi proprio di no, non c'è questa necessità. Considera il caso più generale ok.
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
GenteGuasta
Matricola
*
Offline Offline

Posts: 28


« Reply #2 on: 09-03-2010, 17:55:18 »

ma quindi dovremmo applicare una visita dell'albero e controllare se esistono i due nodi per ogni percorso e nel frattempo contare quanto distano dalla root per poi tornare quelli con distanza maggiore giusto?
Logged
Giovi89
Apprendista Forumista
**
Offline Offline

Posts: 273


« Reply #3 on: 09-03-2010, 18:22:52 »

Grazie della spiegazione ma come ti sembra questa possibile soluzione?
   Estraiamo due sottoalberi che hanno come foglie i due nodi presi a caso,
   poi ci calcoliamo la distanza dalla radice di tutti i nodi dei due sottoalberi
   e infine andiamo a vedere qual'è quel nodo che, comune ai due sottoalberi, 
         ha la stessa distanza dalla radice

 
Logged
GenteGuasta
Matricola
*
Offline Offline

Posts: 28


« Reply #4 on: 09-03-2010, 18:48:28 »

guarda il tuo metodo mi pare un pò troppo complesso e a dirti la verità ho perso un pò di lucidità e non riesco ad interpretare bene il testo, meglio parlarne stasera e sperare ke domani non compaia...
Logged
Pages: [1]   Go Up
Print
Jump to: