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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
public class BinaryNode<E> { private E value = null; private BinaryNode left = null; private BinaryNode right = null; public BinaryNode(E value) { this.value = value; } /* Getter and Setter */ public E getValue() { return value; } public void setValue(E value) { this.value = value } public BinaryNode getLeft() { return left; } public void setLeft(BinaryNode left) { this.left = left } public BinaryNode getRight() { return right; } public void setRight(BinaryNode right) { this.right = right } /* Useful methods */ public boolean isLeaf() { return !hasLeft() && !hasRight(); } public boolean hasLeft() { return this.left != null; } public boolean hasRight() { return this.right != null; } } |
|
1 2 3 4 5 6 7 8 9 |
public class BinaryTree<E> { private BinaryNode<E> root; public BinaryTree( BinaryNode<E> root ) { this.root = root; } /* Getter and Setter */ } |
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.
Concentrandoci 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:
|
1 2 3 4 5 6 7 |
public void preorderTraversal(BinaryNode root) { if(root != null) { System.out.printf( root.value ); preorderTraversal( root.left ); preorderTraversal( root.right ); } } |
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.
A completamento dell’articolo presento una implementazione java di in Iterator che, utilizzando la ricorsione, consente la visita di un albero binario in preordine.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
public class PreorderBinaryTreeTraversal implements Iterator<BinaryNode> { private BinaryNode current; private Stack<BinaryNode> stack = new Stack<BinaryNode>(); //------------------------------------------------------------- // Costruttori //------------------------------------------------------------- public PreorderBinaryTreeTraversal( BinaryTreeImpl tree ) { this( tree.getRoot() ); } public PreorderBinaryTreeTraversal( BinaryNode root ) { if ( root != null ) { this.stack.push( root ); } } //------------------------------------------------------------ // Implementazione di Iterator //------------------------------------------------------------ public boolean hasNext(){ return !stack.isEmpty(); } public BinaryNode next() { current = stack.pop(); if ( current != null ) { if ( !current.isLeaf() ){ if ( current.hasLeft() ) { stack.push( current.getLeft() ); } if ( current.hasRight() ) { stack.push( current.getRight() ); } } } return current; } public void remove() { throw new RuntimeException( "Method not available" ); } } |