Visita di un albero senza l’uso della ricorsione

In questo articolo voglio descrivere come eseguire la visita di un albero (binario per semplicità) senza utilizzare un algoritmo ricorsivo. L’argomento, oltre che di interesse puramente didattico, ha applicazioni pratiche in quanto gli algoritmi ricorsivi, sebbene più eleganti, risultano meno performanti. Ma procediamo con ordine:

Alberi Binari

Gli alberi binari sono strutture dati gerarchica caratterizzate dal fatto che ogni nodo, oltre a contenere una componente informativa, può avere al massimo due riferimenti ad altri nodi.

Una possibile implementazione java di un nodo è la seguente:

Mentre l’implementazione dell’albero binario é:

Ricerca (Ricorsiva) in un Albero Binario

Il problema della ricerca all’interno di un albero binario (o in inglese Tree Traversal) si riferisce, in computer science, al processo di visita di tutti i nodi appartenenti allo stesso, secondo un ordine stabilito a priori ed in modo che ogni nodo sia visitato una ed una sola volta. Con un albero binario sono possibili 3 strategie di visita:

  • preordine o ordine anticipato: si visita prima il nodo corrente e poi i sottoalberi sinistro e destro;
  • inordine o ordine simmetrico: si visita prima il sottoalbero sinistro e poi il nodocorrente e poi il sottoalbero destro;
  • postordine o ordine posticipato: si visita prima il sottoalbero sinistro, poi quello destro e poi il nodo corrente.

bintree pre order traverseConcentrandoci per semplicità alla visita in preordine e prendendo in considerazione l’albero binario di figura, l’ordine di visita dei nodi è: A, B, C, D, E, F, G.

La figura, inoltre, mostra il percorso che l’algoritmo di visita dovrebbe seguire. In particolare si nota, ad esempio, che una volta visitato il nodo radice A il suo albero di destra è visitato solo dopo aver completato la visita dell’intero albero di sinistra.

A questo punto implementare un algoritmo di visita in preordine utilizzando la ricorsione è molto semplice:

Soluzione Non Ricorsiva

L’algoritmo ricorsivo è indubbiamente molto elegante e di semplice comprensione, ma ha come svantaggi principale l’inefficienza. Se il processo di ispezione del nodo (la system.out del nostro esempio per intenderci) non è particolarmente oneroso, la maggior parte del tempo di elaborazione è, infatti, occupato dalla JVM nella gestione dello stack di esecuzione. Questo perché ad ogni invocazione della procedura preorderTraversal la JVM prende il controllo per creare un nuovo record di attivazione nello stack con le relative informazioni sulla nuova esecuzione. Tale processo viene eseguito tante volte quanti sono i nodi dell’albero.

Fortunatamente è possibile implementare un algoritmo più efficiente utilizzando una soluzione iterativa che si inspira proprio dal modo in cui la JVM gestisce lo stack di esecuzione. L’idea, infatti, è quella di avvalersi dell’uso di una stack, ovvero di una struttura dati ausiliaria caratterizzata dal fatto che la modalità di accesso è di tipo LIFO (Last In First Out). L’algoritmo iterativo sostanzialmente utilizza lo stack per inserirvi i nodi che devono ancora essere visitati, simulando di fatto lo stack di esecuzione gestito dalla JVM. L’immagine seguente, gentilmente “rubata” dal sito Algorithms, è una chiara rappresentazione di quanto detto.

Preorder traversal gif

A completamento dell’articolo presento una implementazione java di in Iterator che, utilizzando la ricorsione, consente la visita di un albero binario in preordine.