[fero86]

Originariamente inviato da DanieleC88

Scusa, perché? La radice avrà un genitore nullo, tutti gli altri verranno aggiornati di conseguenza durante gli inserimenti o le rimozioni, non vedo il problema. Quella di avere un puntatore al nodo padre è una prassi comune e sicuramente utile, tanto che sono sicuro sia riportata dalla stragrande maggioranza dei testi introduttivi agli algoritmi e alle strutture dati.

é naturale che la possibilitá di gestire la struttura dati esiste e che la speranza sia quella di non sbagliare mai e di non portarla mai in stato inconsistente, ma l'uomo inevitabilmente sbaglia e una struttura dati come quella é inutilmente complessa nel senso che ci sono molte piu possibilitá di inconsistenza e che é comunque possibile trovare implementazioni alternative dove i nodi non hanno il puntatore al padre.

Tanto per fare un esempio, senza avere un riferimento al nodo padre, se io ti chiedessi di scrivere una routine che riceve in input un generico nodo di un albero binario di ricerca e mi restituisce in output 1) il nodo suo successore, o 2) un valore nullo, se questo non esiste, come faresti?

non lo faccio e basta perché é una porcheria
o, come dicevo sopra, una pessima implementazione.
quando si espone un'interfaccia d'uso per uno strato di software la correttezza di design richiede che si esponga tutto in maniera opaca: non esiste che tu rifili al programmatore finale i puntatori alle tue strutture dati interne e che li rivuoi pure indietro
con un design del genere la validazione dell'input diventa impossibile.

per la visita ordinata di un albero in cui i nodi non hanno il puntatore al padre la soluzione migliore é esporre una funzione che visita tutti i nodi in ordine e per ogni nodo richiama una funzione di callback specificata dal programmatore finale. in alternativa il programmatore finale puó specificare un qualche dato che identifichi il nodo "corrente" della visita (ma non il puntatore al nodo stesso!), ad esempio l'indice del nodo nell'ordinamento, ma in questo modo la soluzione diventa inefficiente perché ad ogni passo in avanti devi ritrovare il nodo identificato da quell'indice; la cosa puó essere resa piu efficiente se si possono fare assunzioni, per esempio che l'albero sia completo e abbia altezza nota, oppure che avrá un certo numero massimo di nodi poiché in questo caso é possibile allocare staticamente un array ordinato di puntatori ai nodi che permette di ritrovare immediatamente il nodo i-esimo dell'ordinamento.

ciao

ah, gli effetti della VICIUS-ite, ancora a distanza di anni