Alberi

Le strutture dati ad albero sono usate per rappresentare le informazioni che abbiano una struttura gerarchica, il tipico esempio di una struttura gerarchica è dato dai rapporti di parentela, un altro esempio è dato dall’organizzazione dei file e delle cartelle all’interno del filesystem di un computer.

In tutti questi casi, ed in molti altri, la struttura migliore per mantenere i dati organizzati è quella ad albero. Tuttavia gli alberi sono molto utilizzati anche come struttura per favorire la ricerca.

Concetti sugli alberi

Riassumiamo quindi le varie cose viste in alcune definizioni

Completiamo quindi la lista dei “gradi di parentela” in un albero:

• padre (parent): unico nodo antenato diretto (la radice non ha padre)
• figli (children): nodi discendenti diretti (collegate da una freccia)
• discendenti (descendants): figli, nipoti, pro-nipoti, …,
• antenati (ancestor): padre, nonno, bisnonno, …
• fratelli (siblings): nodi che hanno lo stesso padre
• cugini (cousins): nodi con padre diverso, ma alla stessa altezza (vedi sotto)

La sequenza di nodi che si ottiene percorrendo un albero viene chiamato percorso (path). Partendo dalla radice è possibile raggiungere i vari nodi attraverso uno specifico percorso. Da un nodo qualsiasi è inoltre possibile raggiungere la radice e uno qualsiasi degli antenati attraverso un unico percorso.

Dato un nodo, chiamiamo profondità (depth) di quel nodo il numero di antenati, ad esempio Fred ha profondità 2 (i suoi due antenati sono David e Alice), Mallory ha profondità 4; la radice (Alice nell’esempio) ha profondità 0.

Inoltre ad ogni nodo associamo un’altezza (height) che è il numero massimo di discendenti sullo stesso percorso, ad esempio l’altezza di Bob è 2, l’altezza di David è 3, l’altezza di Gill è 0. Chiamiamo altezza dell’albero l’altezza della radice, nell’esempio l’altezza di Alice è 4, quindi l’albero nella figura ha altezza 4.

Riassumiamo i concetti esposti nella seguente definizione.

ADT Albero

Una struttura dati astratta per gli alberi dovrebbe comprendere alcune operazioni per l’accesso ai nodi dell’albero. Le modifiche ad un albero solitamente si fanno accedendo direttamente ai nodi coinvolti

• Root restituisce la radice dell’albero.
• Size restituisce il numero totale di nodi dell’albero.
• AllNodes restituisce tutti i nodi dell’albero.
• InternalNodes restituisce i nodi interni dell’albero.
• Leaves restituisce i nodi foglia dell’albero.
• Search restituisce, se esiste, il nodo con valore dato.
• SetRoot imposta il nodo radice dell’albero.

Alberi in Java

Come nel caso delle liste, anche le strutture dati ad albero utilizzando il concetto di posizione che chiamiamo nodo. I nodi sono collegati tra di loro in modo da formare la struttura di albero. Negli alberi i collegamenti esistono tra un nodo e i suoi figli, nella pratica viene anche utilizzato un collegamento da un nodo verso il proprio padre. Ovviamente le foglie non hanno collegamento verso i figli mentre la radice non ha collegamento al padre.

Il nodo contiene anche un valore che rappresenta l’informazione che si vuole memorizzare. Nell’esempio sopra il nodo radice (colorato di rosso) conterrà il valore Alice ed avrà il collegamento ai figli che sono tre nodi contenenti i valori Bob, David e Gill.

L’interfaccia Java per un nodo dell’albero viene mostrata di seguito.

La classe TreeNode

public interface ITreeNode {
    Object value();
    ITreeNode parent();
    ITreeNode[] children();
    void setValue(Object val);
    void setParent(ITreeNode parent);
    void addChild(ITreeNode child);
    void removeChild(ITreeNode child);
    boolean isRoot();
    boolean isLeaf();
    boolean isInternal();
}

L’interfacci contiene diversi metodi per:

• interrogare il nodo
  • value() restituisce il valore
  • parent() restituisce il padre
  • children() restituisce tutti i figli
• modificare il nodo
  • setParent() imposta il collegamento al padre
  • addChild() aggiunge il collegamento ad un nuovo figlio
  • removeChild() rimuove il collegamento ad un figlio esistente
• utili informazioni
  • isRoot() determina se il nodo è radice
  • isLeaf() determina se il nodo è una foglia
  • isInternal() determina se il nodo è interno

L’implementazione in Java dell’interfaccia ITreeNode viene lasciata come esercizio in quanto non richiede particolari accorgimenti (ad eccezione do addChild e removeChild che devono mantenere la struttura ad albero).

La classe Tree

In pratica la struttura ad albero è interamente determinata dai collegamenti tra i nodi. Per questo motivo l’interfaccia ITree sotto dichiarata non contiene metodi per la modifica, ma solo per la sua interrogazione. L’unica eccezione è rappresentata dal metodo setRoot che permette di impostare il nodo radice

public interface ITree {
    ITreeNode getRoot();
    void setRoot(ITreeNode root);
    ITreeNode[] getNodes();
    ITreeNode[] getLeaves();
    ITreeNode[] getInternalNodes();
    int size();
    boolean isEmpty();
    ITreeNode search(Object o);
}   

Notiamo anche l’esistenza di un metodo search che permette di cercare un dato oggetto all’interno dell’albero. La ricerca in un albero è un problema che merita di essere trattato a parte, in particolare quando si parlerà di visite di un albero.

public TreeNode(Object value, ITreeNode parent, ITreeNode[] children)

Tree tree = new Tree();
// aggiunge radice ed altri nodi a 'tree'
// ...
tree.getRoot().addChild(new TreeNode());

Semplici algoritmi su alberi

Vediamo qui alcuni semplici algoritmi su alberi.

Profondità di un nodo

Abbiamo visto sopra che la profondità di un nodo è il numero di antenati di quel nodo, dato un ITreeNode come possiamo calcolare la sua profondità? La strategia risolutiva è molto semplice e sfrutta la ricorsione.

1
2
3
4
5
6

public static int getDepth(ITreeNode node) {
    if (node.parent() == null) {
        return 0;
    }
    return 1 + getDepth(node.parent());
}

L’algoritmo è semplice:

• se il nodo è la radice (node.parent() == null), allora la sua profondità è 0,
• altrimenti la sua profondità sarà uno più della profondità del padre per calcolare la quale usiamo la ricorsione (getDepth(node.parent())).

Altezza di un nodo

Il calcolo dell’altezza di un nodo utilizza un approccio simile al calcolo della profondità, tuttavia ci sono due importanti differenze:

• la ricorsione sarà sui figli anziché sul padre e quindi ci saranno tante chiamate ricorsive quanti sono i figli;
• una volta che conosco l’altezza dei figli devo prendere il massimo di queste per calcolare l’altezza del nodo.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public static int getHeight(ITreeNode node) {
    // 'node' is a leaf, its height is 0
    if (node.isLeaf()) {
        return 0;
    }
    // get the height of each children
    ITreeNode[] children = node.children();
    int[] childrenHeights = new int[children.length];
    for (int i = 0; i < children.length; i++) {
        childrenHeights[i] = getHeight(children[i]);
    }
    // get the height of the highest child
    int maxHeight = childrenHeights[0];
    for (int i = 1; i < childrenHeights.length; i++) {
        maxHeight = (maxHeight > childrenHeights[i]) ? maxHeight : childrenHeights[i];
    }
    return maxHeight + 1;
}

Alberi binari

Finora abbiamo visto che non c’è limite al numero di figli che un nodo di un albero può avere. Se prendiamo l’intero albero chiamiamo arietà (arity) il numero di figli del suo nodo con il maggior numero di figli. Nell’esempio sopra l’albero ha arietà 3 in quanto sia Alice che Jean hanno tre figli mentre gli altri nodi interni ne hanno meno di 3.

Per avere una struttura ad albero e non una semplice lista (che è un albero con arietà 1), l’albero deve avere almeno arietà 2. Cioè deve esistere almeno un nodo con almeno due figli. Chiamiamo albero binario (binary tree) un albero in cui tutti i nodi hanno al massimo due figli (tuttavia, possono averne uno o zero).

In un albero binario possiamo semplificare la gestione dei figli di un nodo in quanto questi possono essere 0, 1 o 2. Spesso si fa riferimento ai figli sinistro (left child) e destro (right child) immaginando l’albero disegnato nel modo che abbiamo visto sopra.

In un albero binario un cammino (path) può essere indicato semplicemente indicando, per ogni nodo, se si segue il figlio destro o il figlio sinistro. Ad esempio, il cammino dalla radice (53) alla foglia 55 può essere descritto indicando il nodo di partenza (in questo caso la radice) e successivamente indicando i figli attraversati in questo case: destro (56), sinistro (55) e destro (55).

La seguente interfaccia estende ITreeNode e definisce l’interfaccia BinaryTreeNode che aggiunge i metodi per recuperare ed impostare i figli sinistro e destro.

public interface IBinaryTreeNode extends ITreeNode {
    ITreeNode getLeftChild();
    void setLeftChild(ITreeNode child);
    ITreeNode getRightChild();
    void setRightNode(ITreeNode child);
}

Visite di un albero

La visita (visit) di un albero è l’operazione che attraverso (visita) tutti i nodi esattamente una volta. Normalmente durante la visita ad un nodo viene effettuata un’operazione, ad esempio la stampa a video del suo valore. Tuttavia rimane il problema dell’ordine in cui visitare i nodi.

• print(node): che mostra a console il valore (funzione di comodo al posto di System.out.println(node.vaue())),
• arrList.add(node): che aggiunge node ad una struttura dati, ad esempio un ArrayList<IBinaryTreeNode>,
• sum += node.value().intValue(): nel caso si stia eseguendo la somma dei valori nei nodi,
• …

Il modo migliore per provare l’effettivo funzionamento del codice è sostituire doOperation(node) con System.out.println(node.value()).

Pre-order

Nella visita pre-order, la prima cosa da fare è eseguire l’operazione sulla radice e poi, ricorsivamente eseguire l’operazione nei sottoalberi sinistro e destro.

1
2
3
4
5
6
7
8

public static void printPreOrder(IBinaryTreeNode node) {
    if (node == null) {
        return;
    }
    doOperation(node);
    printPreOrder(node.getLeftChild());
    printPreOrder(node.getRightChild());
}

In-order

Nella visita in-order, la prima cosa da fare è visitare il sottoalbero sinistro, successivamente si visita la radice ed infine il sottoalbero destro.

1
2
3
4
5
6
7
8

public static void printInOrder(IBinaryTreeNode node) {
    if (node == null) {
        return;
    }
    printInOrder(node.getLeftChild());
    doOperation(node);
    printInOrder(node.getRightChild());
}

Post-order

Nella visita post-order la prima cosa da fare è visitare i due sottoalberi (prima il sinistro poi il destro) e solo alla fine si visita la radice.

1
2
3
4
5
6
7
8

public static void printPostOrder(IBinaryTreeNode node) {
    if (node == null) {
        return;
    }
    printPostOrder(node.getLeftChild());
    printPostOrder(node.getRightChild());
    doOperation(node);
}

Confronto visite

Alberi di ricerca binari

Uno dei tantissimi utilizzi degli alberi è come una struttura dati per rendere efficienti operazioni di ricerca (search) di valori memorizzati. Anche se esistono alberi di ricerca di qualsiasi arietà, tra i più comuni ci sono gli alberi di ricerca binary (Binary Search Tree (BST)) che discuteremo in questa sezione.

La ricerca mediante alberi si basa sull’idea che i valori memorizzati non possano comparire in qualsiasi nodo, ma che, in base al valore stesso, si possano trovare solo in alcune posizioni ben precise. Considerando un tipo di valore che permetta il confronto con gli operatori \(<, =, >\) (e quindi anche \(\leq, \neq \geq \)), un albero di ricerca binario è definito nel seguente modo.

Quindi dalla definizione si capisce che in base al valore il nodo è posizionato in una posizione specifica. Ad esempio supponiamo di avere il valore 20 memorizzato nella radice, allora valori più piccoli (ad esempio 10) possono stare in un nodo che sia nell sottoalbero sinistro della radice, mentre valori più grandi (ad esempio 30) possono stare solo nel sottoalbero destro della radice. Per quanta riguarda i valori uguali, la regola sopra non fornisce alcun vincolo, per cui tale valore può stare sia nel sottoalbero sinistro sia in quello destro della radice.

Nell’albero di destra, invece, si vede come la proprietà di albero di ricerca binario in quanto ogni nodo ha solo nodi con valori \(\leq\) a sinistra e solo valori \(\geq\) a destra. Notiamo anche che l’unico caso di valore uguale (55) compare nella radice e nell’albero destro.

Il metodo qui sotto mostra come realizzare l’algoritmo di ricerca del valore key all’interno di un albero di ricerca binario che memorizza int.

private Node recursiveSearch(int key, Node node) {
    if (node == null || node.value == key) {
        return node;
    }
    if (key < node.value) {
        return recursiveSearch(key, node.left);
    } else {
        return recursiveSearch(key, node.right);
    }
}

Come spesso capita l’algoritmo ricorsivo risulta molto semplice e compatto da scrivere, riconosciamo:

• il caso base node == null oppure node.value == key, il primo caso si ha dopo aver raggiunto (e oltrepassato) un nodo con figlio null, mentre il secondo caso si ha quando l’elemento da cercare è stato trovato al nodo attuale;
• due chiamate ricorsive delle quali solo una viene eseguita che spostano la ricerca sul sottoalbero sinistro se il valore cercato è più piccolo di quello del nodo attuale e sul sottoalbero destro in caso contrario.

Oltre a permettere una ricerca efficiente, gli alberi di ricerca binari possiedono altre caratteristiche.

• Per recuperare il valore minimo tra tutti quelli memorizzati è sufficiente partire dalla radice e spostarsi al figlio sinistro ricorsivamente, fino a quando non si giunge ad un nodo senza figlio sinistro, tale nodo conterrà il valore minimo memorizzato nell’albero.
• In maniera speculare, il valore massimo si ottiene seguendo, dalla radice, il percorso “più a destra”.
• La visita in-order di un albero di ricerca binario produce la sequenza ordinata dei valori memorizzati sull’albero.

Bilanciamento degli alberi

Gli alberi di ricerca binari permettono la ricerca in modo semplice, la velocità con cui avviene la ricerca, tuttavia dipende da come è fatto l’albero (dalla sua topologia). Un albero di ricerca binario formato da una lista di nodi (ad esempio tutti figli sinistri), non è più veloce nella ricerca che una lista di numeri. Quand’è, quindi, che la ricerca in un albero è più veloce? L’idea è che l’albero deve essere bilanciato, vale a dire non ci devono essere dei rami troppo più lunghi di altri (la ricerca su quei rami sarebbe lenta).