Alberi binari

Indice

• 📝Definizione
• 🔎 Visita di un albero
  • Depth-First Search (DFS)
    • Pre-Order Traversal
    • In-Order Traversal
    • Post-Order Traversal
  • Breadth First Search (BFS)
    • Level Order Traversal

📝Definizione

Un albero binario è un albero in cui ogni nodo ha al massimo due figli, identificati come figlio sinistro e figlio destro.

Nota: Due alberi $T$ e $U$ che hanno gli stessi nodi, gli stessi figli per ogni nodo e la stessa radice, sono distinti qualora un nodo $u$ sia designato come figlio sinistro in $T$ e come figlio destro in $U$.
Per esempio, i seguenti due alberi binari sono diversi:

🔎 Visita di un albero

Due strategie per analizzare (visitare) tutti i nodi di un albero:

Depth-First Search (DFS)

Visto che si visita ricorsivamente ognuno dei sottoalberi dell'albero, in base al momento in cui decidiamo di stampare il nodo, la visita si suddivide in 3 modi. Qualunque metodo si scelga, il costo di una visita di un albero contenente $n$ nodi è $\mathrm{\Theta }(n)$, in quanto ogni nodo viene visitato al massimo una volta.

• Time complexity: $O(n)$ (n è il numero di elementi)
• Space complexity: $O(h)$ (h è l'altezza dell'albero)

Pre-Order Traversal

Nella visita in pre-order prima si stampa il nodo corrente, poi si visitano i figli. Nella visita in pre-order la radice è sempre il nodo visitato per primo.

void preOrder(TreeNode t) {
	if (t != NULL) {
		print(t);
		preOrder(t.left);
		preOrder(t.right);
	}
}

Esempio

graph TD
		A((A))
		B((B))
	    C((C))
	    D((D))
	    E((E))
	    F((F))
	    G((G))
	    
	    A-->B
	    A-->E
	    B-->C
	    B-->D
	    E-->F
	    E-->G

Sequenza: A B C D E F G

In-Order Traversal

Nella visita in in-order prima si stampa il ramo sinistro, poi il nodo corrente e infine il ramo destro. Quando eseguita in un albero binario di ricerca, la visita in in-order visita i nodi in ordine crescente (da qui il nome "in-order").

void inOrder(TreeNode t) {
	if (t != NULL) {
		inOrder(t.left);
		print(t);
		inOrder(t.right);
	}
}

Esempio

graph TD
		A((A))
		B((B))
	    C((C))
	    D((D))
	    E((E))
	    F((F))
	    G((G))
	    
	    A-->B
	    A-->E
	    B-->C
	    B-->D
	    E-->F
	    E-->G

Sequenza: C B D A F E G

Post-Order Traversal

Nella visita in post-order vengono visitati prima i figli, poi il nodo corrente. Nella visita in post-order la radice è sempre il nodo visitato per ultimo.

void postOrder(TreeNode t) {
	if (t != NULL) {
		postOrder(t.left);
		postOrder(t.right);
		print(t);
	}
}

Esempio

graph TD
		A((A))
		B((B))
	    C((C))
	    D((D))
	    E((E))
	    F((F))
	    G((G))
	    
	    A-->B
	    A-->E
	    B-->C
	    B-->D
	    E-->F
	    E-->G

Sequenza: C D B F G E A

Breadth First Search (BFS)

Partendo dalla radice si visitano tutti i nodi livello per livello. La visita è chiamata Level Order Traversal.
Possiamo implementarlo sia ricorsivamente sia iterativamente.

Level Order Traversal

Esempio

graph TD
		A((A))
		B((B))
	    C((C))
	    D((D))
	    E((E))
	    F((F))
	    G((G))
	    
	    A-->B
	    A-->E
	    B-->C
	    B-->D
	    E-->F
	    E-->G

Sequenza: A B E C D F G

Implementazione ricorsiva

L'idea è la seguente:

• Usiamo un for che va da $1$ a $h$ (l'altezza dell'albero)
• Ad ogni iterazione, utilizziamo il Depth-First Search (DFS) per attraversare l'albero, mantenendoci l'altezza del nodo corrente.
  • Se il nodo è nullo -> return
  • Se il livello è $1$ siamo arrivati al livello desiderato, quindi stampiamo tree->data
  • Se il livello è maggiore di $1$, allora
    • Ricorsivamente, visitiamo il figlio sinistro, decrementando il livello di $1$
    • Ricorsivamente, visitiamo il figlio destro, decrementando il livello di $1$

/* Function to print level order traversal a tree */
void levelOrderTraversal(Tree root)
{
    int h = height(root);
	for(int level = 1; level < h + 1; ++level)
        printCurrentLevel(root, level);
}

/* Print nodes at a current level */
void printCurrentLevel(Tree root, int level)
{
	if(root == NULL)
        return;
    else if(level == 1)
        cout << root.data << " ";
    else {
        printCurrentLevel(root.left, level - 1);
        printCurrentLevel(root.right, level - 1);
    }
}

/* Compute the "height" of a tree -- the number of 	nodes along the longest path from the root node
	down to the farthest leaf node. */
int height(Tree node)
{
    if (node == NULL)
        return 0;

    int leftHeight = height(node.left);
    int rightHeight = height(node.right);
    return max(leftHeight, rightHeight) + 1;
}

• Time complexity: $O(n^2)$ (n è il numero di elementi)
  • Questo perchè levelOrderTraversal() è $O(n)+O(n-1)+O(n-2)+...+O(1)$, cioè $O(n^2)$
• Space complexity:
  • $O(n)$ (se l'albero non è bilanciato, nel caso peggiore è praticamente una lista)
  • $O(\log n)$ (se l'albero è bilanciato, nel caso pessimo non devi tenere tutti gli elementi nello stack)

Implementazione iterativa (usando una coda)

L'idea è la seguente:

• Per ogni nodo, prima stampiamo il suo valore, poi lo rimuoviamo dalla coda e successivamente aggiungiamo i suoi figli nella coda.

void levelOrderTraversal(Tree root) {
    /* Base case */
    if (root == NULL)
        return;
    
    /* Create an empty queue for level order traversal */
    queue<Tree> queue;

    /* Enqueue root */
    queue.push(root);

    while(!queue.empty()) {
        /* Print front of queue and remove it from queue */
        Tree node = queue.front();
        cout << node.data << " ";
        queue.pop();

        /* Enqueue left child */
        if(node.left != NULL)
            queue.push(node.left);

        /* Enqueue right child */
        if(node.right != NULL)
                queue.push(node.right);
    }
}

• Time complexity: $O(n)$ (n è il numero di elementi)
• Space complexity: $O(w)$ (w è la massima larghezza dell'albero)