Albero

Un albero è un grafo orientato aciclico. Ogni nodo possiede c figli, ovvero n nodi raggiungibili da esso. Ogni nodo è raggiungibile direttamente da un nodo detto genitore. La radice è un nodo particolare che non ha genitore, mentre tutti gli altri nodi hanno esattamente un genitore.

I nodi che non possiedono figli sono detti foglie. Tutti i nodi raggiungibili da un dato nodo sono detti nodi discendenti, mentre tutti i nodi attraverso i quali è possibile raggiungere il nodo sono detti antenati. I genitori sono un caso particolare di nodi antenati e i figli sono un caso particolare di nodi discendenti.

La radice è il nodo antenato di tutti gli altri. Un cammino tra due nodi è definito come una sequenza di nodi, connessi tra loro, che formano un percorso tra i due nodi. Dalla radice è presente un cammino verso qualunque altro nodo, e qualunque foglia.

L'altezza di un nodo è definita come il numero di archi sul più lungo cammino discendente che va dal nodo considerato ad una foglia. L'altezza di un albero è definita come l'altezza del nodo radice.

Negli alberi binari ogni nodo ha al più due figli. Dato un nodo, l'insieme dei nodi formato dal figlio di sinistra e da tutti i nodi che discendono da esso è detto sottoalbero sinistro, e analogamente il figlio di destra e tutti i nodi che discendono da esso formano il sottoalbero di destra.

Un albero binario è detto completo o pienamente binario se ogni nodo possiede esattamente due figli oppure non ne possiede (è una foglia). In altre parole non esistono nodi con un solo figlio. Se un tale albero possiede n nodi, allora ha una altezza di log2 n. Quindi è possibile partire dalla radice e raggiungere una foglia in log2 n "passi".
albero binario

albero.png

Nell'immagine a destra si può vedere un esempio di albero. Il nodo A è la radice, mentre i nodi L, G, F sono foglie, perché non hanno nodi figlio. I figli di A sono B e C, mentre tutti gli altri sono discendenti di A.

Il nodo E ha un solo figlio H, ha come discendenti i nodi I, L e come genitore ha C. I nodi che discendono dal figlio sinistro formano il sottoalbero sinistro del nodo, e allo stesso modo i nodi che discendono dal figlio destro formano il sottoalbero destro. Ad esempio, il nodo C ha come sottoalbero destro dai nodi E, H, I, L, mentre il sottoalbero sinistro è costituito solo dal nodo F.

Alberi binari di ricerca

Un albero binario di ricerca è un albero binario che contiene oggetti che possiedono un ordinamento. Dato un nodo a e un nodo b, se b < a allora b viene posizionato come figlio sinistro, mentre se b > a viene posizionato come figlio destro.

Questa caratteristica permette di mantenere tutti i nodi inferiori ad un dato nodo alla sua sinistra e tutti i nodi superiori alla sua destra. La ricerca di un nodo avviene in modo molto veloce, se l'albero è bilanciato. Un albero è bilanciato se i nodi sono uniformemente distribuiti, ovvero la maggior parte dei nodi possiede entrambi i figli. In un albero perfettamente bilanciato, se i nodi sono N, la ricerca avviene in O(log N). Se un albero invece non è bilanciato, la ricerca diventa più lunga, fino a raggiungere il caso limite di O(n).

L'inserimento di un nodo avviene iniziando dal nodo radice e effettuando il confronto. Se è inferiore si passa al figlio sinistro, altrimenti al figlio destro. Se il figlio non è presente, allora viene inserito al suo posto il nuovo nodo. Se invece è presente, allora si confronta il nuovo nodo con il figlio, continuando con gli altri figli. La stessa procedura avviene per la ricerca di un nodo.

Si nota che la struttura dell'albero dipende dall'ordine in cui vengono inseriti i nodi. Infatti una stesso insieme di valori può generare alberi diversi. Se l'albero è bilanciato, allora esso possiede una altezza di log n, dove n è il numero di nodi dell'albero. Si nota che un albero non bilanciato appare come una concatenazione di nodi. Nel caso degenere, esso diventa una lista concatenata e la ricerca di un elemento avviene in O(n), poiché l'altezza diventa h = n-1.

Implementazione

Un nodo è una struttura che possiede un puntatore al nodo genitore, due puntatori ai nodi figli e un campo per contenere l'oggetto.

class TreeNode
{
    TreeNode parent, left, right;
    public TreeNode Parent
    {
        get { return parent; }
        set { parent = value; }
    }
    public TreeNode Left
    {
        get { return left; }
        set { left = value; }
    }
    public TreeNode Right
    {
        get { return right; }
        set { right = value; }
    }
    object data;
    public object Data
    {
        get { return data; }
    }
 
    public TreeNode(object obj)
    {
        data = obj;
    }
}

La ricerca di un nodo procede secondo una procedura ricorsiva: si parte dal nodo radice e si confronta il valore da cercare con il valore del nodo radice. Se è quello cercato l'algoritmo termina. Se non lo è ed ha un valore inferiore allora l'algoritmo riparte considerando il figlio sinistro. Se invece il valore è superiore allora si riparte dal nodo destro.
public TreeNode Search(TreeNode root, object k)
{
    if (root == null)
        return null;
    if (root.Data == k)
        return root;
    if (((IComparable)root.Data).CompareTo(k) > 0)
        return Search(root.Left, k);
    else
        return Search(root.Right, k);
}

Nell'implementazione il metodo Search riceve come parametro TreeNode root. Inizialmente viene passato il vero nodo radice dell'albero, ma successivamente vengono passati i nodi figlio.

L'inserimento di un nodo nell'albero procede allo stesso modo della ricerca. L'algoritmo tiene tuttavia traccia dell'elemento padre, in modo da poter inserire il nuovo elemento. La scansione dei nodi procede fino a quando non si trova un puntatore nullo. Successivamente viene inserito il nodo.

public void Add(TreeNode n)
{
    TreeNode x = root;
    TreeNode y = null;
 
    while (x != null)
    {
        y = x;
        if (((IComparable)n.Data).CompareTo(x.Data) < 0)
            x = x.Left;
        else
            x = x.Right;
    }
 
    n.Parent = y;
 
    if (y == null)
        root = n;
    else if (((IComparable)n.Data).CompareTo(y.Data) < 0)
        y.Left = n;
    else
        y.Right = n;
}

La cancellazione di un nodo è più difficile, perché deve essere mantenuta la struttura dell'albero. La cancellazione di un nodo senza figli può avvenire senza problemi, mentre se un nodo ha uno o più figli la procedura è più complessa.

Se il nodo ha un solo figlio, allora il nodo viene eliminato e sostituito con il figlio.

Se il nodo ha due figli, allora si cerca il successore del nodo. Esso è il nodo con valore immediatamente superiore al nodo che deve essere cancellato. Può essere individuato come il figlio più a sinistra del sottoramo di destra. Se non ha figlio destro, allora il successore è l'antenato del nodo per il quale quest'ultimo è nel sottoramo sinistro.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License