09: Alberi

Un albero è una struttura dati composta da nodi, ognuno con un valore e collegamenti ad altri nodi.

La radice è il nodo principale da cui si diramano tutti gli altri nodi.

Le foglie sono i nodi terminali senza ulteriori rami.

I nodi interni sono i nodi che hanno almeno un figlio.

Un figlio è un nodo direttamente collegato a un altro nodo detto padre.

Un padre è un nodo che ha almeno un figlio.

I fratelli sono nodi che condividono lo stesso padre.

Un discendente è un nodo raggiungibile da un dato nodo attraverso un percorso discendente.

Il livello di un nodo in un albero è il numero di archi che si devono attraversare per raggiungere il nodo dalla root. Il livello della root è 0.

L'altezza di un albero è il livello del nodo che ha il livello massimo tra tutti i nodi.

Il grado di un albero è il numero di figli del nodo che ha il maggior numero di figli.

In alcuni casi la root può essere vista come una sorgente da cui viene distribuita qualcosa verso le foglie, o come un pozzo che raccoglie qualcosa che arriva dalle foglie.

Un albero ordinato è un albero in cui l'ordine in cui compaiono i figli di un nodo è importante. Due alberi con gli stessi nodi, ma in ordine diverso, sono considerati diversi se ordinati, e identici se non ordinati.

Un albero binario posizionale è un albero in cui l'ordine dei nodi figli è significativo. Questo significa che un nodo figlio sinistro è diverso da un nodo figlio destro.

L'insieme BT(A) rappresenta tutti gli alberi binari posizionali possibili costruiti usando elementi dell'insieme A. L'albero vuoto (∅) è considerato parte dell'insieme.

La definizione induttiva di BT(A) parte dall'albero vuoto e poi costruisce nuovi alberi aggiungendo un nodo radice con due sottoalberi (sinistro e destro), che devono già essere alberi binari posizionali.

Ogni nodo in un albero binario posizionale ha un'etichetta, un puntatore sinistro (left) e un puntatore destro (right), che puntano rispettivamente al sottoalbero sinistro e destro del nodo.

La cardinalità di un albero corrisponde al numero totale dei suoi nodi.

La cardinalità di un albero binario posizionale è il numero totale di nodi presenti nell'albero.

L'algoritmo 2Tree-Card(T) calcola la cardinalità di un albero binario posizionale visitando ricorsivamente tutti i nodi.

La cardinalità di un albero rappresentato con child e sibling è il numero totale di nodi nell'albero.

L'algoritmo kTree-Card(T) calcola la cardinalità di un albero rappresentato con child e sibling visitando iterativamente tutti i nodi.

L'altezza di un albero binario posizionale è la lunghezza del percorso più lungo dalla radice a una foglia.

L'algoritmo 2Tree-Hight(T) calcola l'altezza di un albero binario posizionale scorrendo ricorsivamente tutti i nodi.

L'altezza di un albero rappresentato con child e sibling è il numero massimo di livelli che si possono scendere dall'albero partendo dalla radice.

L'algoritmo kTree-Hight(T) calcola l'altezza di un albero rappresentato con child e sibling scorrendo iterativamente tutti i nodi.

Una visita in profondità di un albero (Tree-DFS) visita tutti i nodi di un ramo del albero prima di passare al ramo successivo. Ad esempio, visita tutti i figli di un nodo prima di visitare i figli del fratello di quel nodo. La visita in profondità si può ottenere con una pila.

Un algoritmo iterativo che implementa la visita in profondità di un albero usando una pila. L'algoritmo inizia con la radice dell'albero, aggiunge l'albero alla pila e visita quindi ogni nodo, aggiungendo i suoi figli alla pila. Quando la pila è vuota, la visita è completa.

Una rappresentazione di un albero in un grafo dove ogni nodo ha riferimenti diretti a tutti i suoi figli.

Una visita in ampiezza di un albero (Tree-BFS) visita tutti i nodi di un livello dell'albero prima di passare al livello successivo. Ad esempio, visita tutti i figli di un nodo prima di visitare i figli dei suoi fratelli.

Un algoritmo iterativo che implementa la visita in ampiezza di un albero utilizzando una coda. L'algoritmo inizia con la radice dell'albero, aggiunge l'albero alla coda e visita quindi ogni nodo, aggiungendo i suoi figli alla coda. Quando la coda è vuota, la visita è completa.

Un metodo per visitare tutti i nodi di un albero in modo sistematico, partendo dalla radice e visitando ogni ramo fino alle foglie.

Algoritmo ricorsivo che implementa la visita in profondità su un albero rappresentato con puntatori "child" e "sibling".

Struttura dati utilizzata nell'algoritmo Tree-DFS per memorizzare l'ordine di visita dei nodi.

Operazione che aggiunge un elemento al bordo superiore della pila.

Operazione che rimuove ed elimina un elemento dal bordo superiore della pila.

La complessità computazionale della visita in profondità (DFS) è O(n), dove n è il numero di nodi nell'albero.

Algoritmo che visita tutti i nodi di un albero, partendo dalla radice e visitando i figli di ogni nodo prima di passare ai fratelli.

Struttura dati utilizzata nell'algoritmo BFS per memorizzare i nodi da visitare.