[Algo] Esercizio padri

[Pablitos23]

Dato un albero T di n nodi rappresentato tramite il vettore dei padri P e un intero h, dare lo pseudocodice di un algoritmo che in tempo O(n) calcola il numero di nodi ad altezza h nell'albero T.

La mia idea.

Per prima cosa ricostruisco l'albero dal vettore dei padri e poi effettuo una visita modificata dell'albero in modo che mi ritorna il numero di nodi all'altezza h.

Padri( P:vettore dei padri, h: int ) -> numero di nodi ad altezza h
    Nodo root = CreateTree(P)      /* ritorna il nodo dell'albero creato dal vettore dei padri
    int altezza = Vis( root , h )      /* ritorna il numero di nodi di altezza h

   return altezza

Vis( T: nodo radice, h:int ) -> numero di nodi all'altezza h
   if T==NULL or h<=1 return 0
   if k == 0 return 1
   return Vis(T.left, h-- ) + Vis(T.right, k--)

La procedura CreateTree ancora la devo elaborare.
Avrò una complessità della funzione Padri pari a O(n) ???

Ciao e buona serata

[apatriarca]

CreateTree consiste semplicemente nell'invertire le relazioni. Crei un array di nodi e poi scorri l'array dei padri e aggiungi il figlio nel nodo padre corrispondente. La complessità è certamente lineare.

[Pablitos23]

Va bene la mia procedura di visita specifica per gli alberi binari?
Mi sta venendo un dubbio dato che la traccia non specifica che si tratta esclusivamente di alberi binari.

[apatriarca]

No, la visita la devi fare per un generico albero.

[Pablitos23]

Ciao, riprendo quest'esercizio dato che ho l'esame a breve e da allora non l'ho risolto.
Quindi una possibile strategia potrebbe essere la seguente:

- inizializzo una lista delle adiacenze pari a P.length;

ListAdj(P.length)

- per ogni indice i in P, aggiungo nella lista delle adiacenze in P, il figlio i;

ListAdj[P[i]].add(i)

Così avrò la lista delle adiacenze del mio grafo diretto e aciclico, ovvero un abero e vi posso applicare una BFS per calcolare i nodi ad una certa altezza, dato che la BFS su un albero ha complessità al max O(|V|+|E|) dove |E| = |V|-1 in un albero. Quindi rientro in un O(n).

Però come capisco qual'è la radice dell'albero su cui cominciare la BFS??

Grazie e buona giornata

[Pablitos23]

Ecco un possibile pseudocodice, vorrei avere vostri consigli.

Padri( P: vettore dei padri, h: int ) -> ritorna il numero di nodi ad altezza h

   ListAdj <- lista delle adiacenze di lunghezza pari a P.length
   A <- array dei gradi entranti di ogni nodo inizializzato a 0 di lunghezza P.length
   Dist <- array delle distanze di ogni nodo dalla radice
   Nodo root <- inizializzato a null
   int nodi <- 0 

   for nodo n in P then
      if n != P[n] then
          ListAdj[ P[n] ].add( n )
          A[n] = A[n] + 1

   int minDegree <- infinity
   for nodo n in A then
      if A[n]  < minDegree then
         minDegree <- A[n]
         root <- n

   Dist <- BFS(root)
   for nodo n in Dist then
      if Dist[n] == h then
         nodi <- nodi +1

   return n

La complessità dovrebbe essere O(n).