Tree traversal

A differenza delle liste collegate, degli array unidimensionali e di altre strutture dati lineari, che sono canonicamente attraversate in ordine lineare, gli alberi possono essere attraversati in più modi. Possono essere attraversati in ordine di profondità o di larghezza. Ci sono tre modi comuni per attraversarli in ordine di profondità: in-order, pre-order e post-order. Oltre a queste traversate di base, sono possibili vari schemi più complessi o ibridi, come le ricerche limitate in profondità come la ricerca iterativa in profondità-prima. Quest’ultima, così come la ricerca breadth-first, può anche essere usata per attraversare alberi infiniti, vedi sotto.

Strutture dati per l’attraversamento degli alberiModifica

L’attraversamento di un albero comporta l’iterazione su tutti i nodi in qualche modo. Poiché da un dato nodo c’è più di un possibile nodo successivo (non è una struttura dati lineare), allora, assumendo un calcolo sequenziale (non parallelo), alcuni nodi devono essere differiti-memorizzati in qualche modo per una visita successiva. Questo è spesso fatto tramite uno stack (LIFO) o una coda (FIFO). Poiché un albero è una struttura dati autoreferenziale (definita ricorsivamente), la traversata può essere definita per ricorsione o, più sottilmente, per corecursione, in modo molto naturale e chiaro; in questi casi i nodi differiti sono memorizzati implicitamente nello stack delle chiamate.

La ricerca in profondità è facilmente implementata tramite uno stack, anche ricorsivamente (tramite lo stack delle chiamate), mentre la ricerca in larghezza è facilmente implementata tramite una coda, anche corecursivamente.:45-61

Ricerca di profondità di albero binarioModifica

Traversata di profondità (percorso punteggiato) di un albero binario:

• Pre-ordine (accesso al nodo in posizione rossa ●):

  F, B, A, D, C, E, G, I, H;

• In-order (accesso al nodo in posizione verde ●):

  A, B, C, D, E, F, G, H, I;

• Post-order (accesso al nodo in posizione blu ●):

  A, C, E, D, B, H, I, G, F.

Queste ricerche sono dette depth-first search (DFS), poiché l’albero di ricerca viene approfondito il più possibile su ogni figlio prima di passare al fratello successivo. Per un albero binario, sono definite come operazioni di accesso ad ogni nodo, a partire dal nodo corrente, il cui algoritmo è il seguente:

Lo schema ricorsivo generale per attraversare un albero binario è questo:

1. Scendere di un livello fino all’argomento ricorsivo N. Se N esiste (è non vuoto) eseguire le seguenti tre operazioni in un certo ordine: L: attraversare ricorsivamente il sottoalbero sinistro di N. R: Attraversa ricorsivamente il sottoalbero destro di N. N: Accesso (visita) al nodo corrente N stesso.
2. Ritorno salendo di un livello e arrivando al nodo padre di N.

Ci sono tre metodi (modelli) in quale posizione del percorso (traversata) rispetto al nodo (nella figura: rosso, verde o blu) deve avvenire la visita (accesso) del nodo. La scelta di esattamente un colore determina esattamente una visita di un nodo come descritto di seguito. L’accesso a tutti e tre i colori risulta in una triplice visita dello stesso nodo che produce la sequenzializzazione “all-order”:

F-B-A-A-B-D-C-C-D-E-E-E-D-B-F-G-G- I-H-H-H- I- I-G-F

Pre-order, NLREdit

1. Accede alla parte dati del nodo corrente (nella figura: posizione rossa).
2. Attraversa il sottoalbero sinistro chiamando ricorsivamente la funzione di preordine.
3. Attraversa il sottoalbero destro chiamando ricorsivamente la funzione di preordine.

La traversata di pre-ordine è una traversata topologicamente ordinata, perché un nodo genitore viene processato prima di uno qualsiasi dei suoi nodi figli.

In-order, LNREdit

1. Traversa il sottoalbero sinistro chiamando ricorsivamente la funzione in-order.
2. Accede alla parte di dati del nodo corrente (nella figura: posizione verde).
3. Traversa il sottoalbero destro chiamando ricorsivamente la funzione in-order.

In un albero di ricerca binario ordinato in modo tale che in ogni nodo la chiave sia maggiore di tutte le chiavi del suo sottoalbero sinistro e minore di tutte le chiavi del suo sottoalbero destro, l’in-order traversal recupera le chiavi in ordine crescente.

Inversione dell’ordine, RNLEdit

1. Traversa il sottoalbero destro chiamando ricorsivamente la funzione di inversione dell’ordine.
2. Accede alla parte dati del nodo corrente.
3. Traversa il sottoalbero sinistro chiamando ricorsivamente la funzione di inversione dell’ordine.

In un albero di ricerca binario, l’inversione dell’ordine recupera le chiavi in ordine decrescente.

Post-order, LRNEdit

1. Traversa il sottoalbero sinistro chiamando ricorsivamente la funzione post-order.
2. Traversa il sottoalbero di destra chiamando ricorsivamente la funzione di post-ordine.
3. Accede alla parte di dati del nodo corrente (in figura: posizione blu).

La traccia di una traversata è chiamata sequenzializzazione dell’albero. La traccia della traversata è una lista di ogni nodo visitato. Nessuna sequenzializzazione secondo il pre-, in- o post-ordine descrive l’albero sottostante in modo univoco. Dato un albero con elementi distinti, sia il pre-ordine che il post-ordine accoppiato con l’in-ordine è sufficiente per descrivere l’albero in modo univoco. Tuttavia, il pre-ordine con il post-ordine lascia qualche ambiguità nella struttura dell’albero.

Albero genericoModifica

Per attraversare qualsiasi albero con la ricerca in profondità, eseguire le seguenti operazioni ad ogni nodo:

1. Se nodo non presente restituire.
2. Accedere (= visitare) il nodo (posizione di pre-ordine).
3. Per ogni i da 1 a numero_di_figli – 1 fare:
   1. Ricorrere all’i-esimo figlio.
   2. Accede al nodo (posizione in-ordine).
4. Traversa ricorsivamente l’ultimo figlio.
5. Accede al nodo (posizione post-ordine).

A seconda del problema in questione, le operazioni di pre-ordine, post-ordine, e soprattutto una delle operazioni di (numero_di_figli – 1) in-ordine possono essere nulle, o si vuole accedere solo a un figlio specifico, quindi queste operazioni sono opzionali. Inoltre, in pratica, più di una delle operazioni di pre-ordine, in-ordine e post-ordine può essere richiesta. Per esempio, quando si inserisce in un albero ternario, un’operazione di pre-ordine viene eseguita confrontando gli elementi. Un’operazione di post-ordine può essere necessaria in seguito per riequilibrare l’albero.

Ricerca a monte, o ordine di livelloModifica

Ordine di livello: F, B, G, A, D, I, C, E, H.

Gli alberi possono anche essere attraversati in ordine di livello, dove si visita ogni nodo di un livello prima di andare ad un livello inferiore. Questa ricerca è chiamata ricerca per ampiezza (BFS), poiché l’albero di ricerca è ampliato il più possibile ad ogni profondità prima di andare alla profondità successiva.

Altri tipiModifica

Ci sono anche algoritmi di attraversamento degli alberi che non si classificano né come ricerca per profondità né per ampiezza. Uno di questi algoritmi è la ricerca ad albero Monte Carlo, che si concentra sull’analisi delle mosse più promettenti, basando l’espansione dell’albero di ricerca su un campionamento casuale dello spazio di ricerca.