Dato il numero X di foglie (le foglie ad anello nella foto) in un albero squilibrato con profondità 100-1000 e un numero totale di nodi di circa 15 000 000. Sto cercando il primo antenato comune per quelle foglie.
Qual è il modo più efficace per raggiungere questo obiettivo?
Considerando che hai già implementato un metodo find , puoi eseguire questa operazione:
struct NodeBin* ancestor(struct NodeBin* n, int i, int j){ // find ancestor of i and j
struct NodeBin* ni = find(n,i);
while(ni!=NULL){
printf("%d\n",ni->data);
if(find(ni,j)!=NULL) return ni;
ni=parent(n,ni->data);
}
return NULL;
}
Fondamentalmente esegue il metodo find usando il genitore di i come radice dell'albero e, se non riesce a trovare j da lì che non è l'antenato comune, passa di un livello fino a i nonno e lo fa in modo ricorsivo.
Leggi altre domande sui tag algorithms trees