[Algoritmo] Albero binario rosso o nero

[first100]

Salve a tutti,

devo svolgere il seguente esercizio :
Sia T un albero binario i cui nodi possono essere neri o rossi. Scrivere un algoritmo che stabilisce se esiste un intero i tale che tutti i nodi a profondita i hanno o stesso colore.

Allora il problema è che alla stessa profondità i dovrei avere sempre o tutto un colore o l'altro. O non è cosi? Non riesco a capire

Grazie a chi mi aiuterà

[apatriarca]

Credo che i colori siano assegnati nell'esercizio in modo completamente casuale. Puoi sostituire i due colori con altro e l'esercizio rimane lo stesso. Per esempio potresti avere un albero con la radice rossa e un figlio nero e uno rosso.

[onlyReferee]

"apatriarca":
[...]
Per esempio potresti avere un albero con la radice rossa e un figlio nero e uno rosso.

Mi permetto di correggerti: in un albero rosso-nero deve valere la proprietà che entrambi i figli di un nodo avente colore rosso devono essere neri. L'albero da te descritto pertanto non è un albero rosso-nero.

[apatriarca]

Sono d'accordo, ma qui non mi sembra che si stia parlando di albero rosso-nero. Ha infatti scritto "un albero binario i cui nodi possono essere neri o rossi". Non si fa riferimento ad altre condizioni e non si parla di "albero rosso-nero". Per cui secondo me vanno considerati alberi più generali. Anche se la scelta dei due colori potrebbe essere fonte di ambiguità e incomprensioni.

[first100]

Preciso che la traccia dell'esercizio è come l'ho scritta, io mi sto un pò incartando sul fatto nero rosso e non riesco a procedere

[first100]

Come controllare che tutti i nodi ad una certa profondità siano dello stesso colore? devo sempre partire dalla radice? Come si può fare in maniera efficiente?

Grazie

[apatriarca]

Il metodo più semplice è usare una struttura dati aggiuntiva (anche solo un'array di lunghezza uguale all'altezza dell'albero).

[onlyReferee]

"apatriarca":Sono d'accordo, ma qui non mi sembra che si stia parlando di albero rosso-nero. Ha infatti scritto "un albero binario i cui nodi possono essere neri o rossi". Non si fa riferimento ad altre condizioni e non si parla di "albero rosso-nero". Per cui secondo me vanno considerati alberi più generali. Anche se la scelta dei due colori potrebbe essere fonte di ambiguità e incomprensioni.

Ok, d'accordo. Se la scelta dei colori è casuale e non ha nulla a che vedere con gli alberi rosso-neri così come li conosciamo i ragionamenti reggono.

"apatriarca":Il metodo più semplice è usare una struttura dati aggiuntiva (anche solo un'array di lunghezza uguale all'altezza dell'albero).

Più semplice ed anche di minor complessità computazionale a mio giudizio.

[first100]

Ho trovato un algoritmo per la visita in ampiezza di un albero binario :

void bfs(v)
{
queue.enqueue(v);
while (!queue.isEmpty()) {
p = (BSTNode) queue.dequeue();
p.visit();
if (p.leftChild != null)
queue.enqueue(p.leftChild);
if (p.rightChild != null)
queue.enqueue(p.rightChild);
}
}

In pratica aggiunge nella coda il livello corrente, e poi passa ad esaminare i figli, il controllo se sono dello stesso colore secondo voi dove dovrei farlo ?
Grazie