In questo tutorial imparerai a conoscere la struttura dei dati ad albero. Inoltre, imparerai a conoscere diversi tipi di alberi e le terminologie utilizzate in tree.
Un albero è una struttura dati gerarchica non lineare costituita da nodi collegati da archi.
Un albero
Perché la struttura dei dati ad albero?
Altre strutture di dati come array, elenchi collegati, stack e code sono strutture di dati lineari che memorizzano i dati in sequenza. Per eseguire qualsiasi operazione in una struttura dati lineare, la complessità temporale aumenta con l'aumento della dimensione dei dati. Ma non è accettabile nel mondo computazionale di oggi.
Diverse strutture di dati ad albero consentono un accesso più rapido e semplice ai dati poiché si tratta di una struttura di dati non lineare.
Terminologie ad albero
Nodo
Un nodo è un'entità che contiene una chiave o un valore e puntatori ai relativi nodi figlio.
Gli ultimi nodi di ogni percorso sono chiamati nodi foglia o nodi esterni che non contengono un collegamento / puntatore a nodi figli.
Il nodo che ha almeno un nodo figlio è chiamato nodo interno .
Bordo
È il collegamento tra due nodi qualsiasi.
Nodi e bordi di un albero
Radice
È il nodo più in alto di un albero.
Altezza di un nodo
L'altezza di un nodo è il numero di bordi dal nodo alla foglia più profonda (cioè il percorso più lungo dal nodo a un nodo foglia).
Profondità di un nodo
La profondità di un nodo è il numero di bordi dalla radice al nodo.
Altezza di un albero
L'altezza di un albero è l'altezza del nodo radice o la profondità del nodo più profondo.
Altezza e profondità di ogni nodo in un albero
Grado di un nodo
Il grado di un nodo è il numero totale di rami di quel nodo.
foresta
Una raccolta di alberi disgiunti è chiamata foresta.
Creare una foresta da un albero
Puoi creare una foresta tagliando la radice di un albero.
Tipi di albero
- Albero binario
- Albero di ricerca binario
- Albero AVL
- B-Tree
Traversata dell'albero
Per eseguire qualsiasi operazione su un albero, è necessario raggiungere il nodo specifico. L'algoritmo di attraversamento dell'albero aiuta a visitare un nodo richiesto nell'albero.
Per saperne di più, visita il percorso tra gli alberi.
Applicazioni ad albero
- Gli alberi di ricerca binari (BST) vengono utilizzati per verificare rapidamente se un elemento è presente in un insieme o meno.
- L'heap è un tipo di albero utilizzato per l'ordinamento dell'heap.
- Una versione modificata di un albero chiamato Tries viene utilizzata nei router moderni per memorizzare le informazioni di routing.
- I database più diffusi utilizzano B-Trees e T-Trees, varianti della struttura ad albero che abbiamo appreso sopra per memorizzare i loro dati
- I compilatori utilizzano un albero della sintassi per convalidare la sintassi di ogni programma che scrivi.
