2.1 Componenti principali di un albero
Albero è un tipo speciale di grafo, che è acyclic e connected. In un albero esiste un unico percorso tra qualsiasi coppia di nodi, il che rende la sua struttura gerarchica.
Componenti principali di un albero:
1. Nodi:
- Elementi principali di un albero che contengono dati.
- Ad esempio, ogni cerchio nel diagramma rappresenta un nodo.
2. Radice:
- Nodo che non ha nodi padre. È il punto di inizio dell'albero.
- Ad esempio, il nodo superiore nel diagramma.
3. Foglie:
- Nodi che non hanno nodi figli. Si trovano alle "estremità" dell'albero.
- Ad esempio, i nodi in fondo al diagramma.
4. Archi:
- Connessioni tra nodi. Determinano le relazioni genitore-figlio tra i nodi.
- Ad esempio, le linee che collegano i nodi nel diagramma.
5. Sottoalberi:
- Qualsiasi sottoinsieme di un albero composto da un nodo e da tutti i suoi discendenti.
- Ad esempio, un ramo dell'albero che parte da un nodo.
Caratteristiche importanti di un albero:
1. Altezza dell'albero:
- Lunghezza del percorso dalla radice alla foglia più lontana.
- Ad esempio, il numero di livelli nel diagramma.
2. Profondità del nodo:
- Lunghezza del percorso dalla radice al nodo specificato.
- Ad esempio, il numero di livelli dalla radice al nodo specifico.
2.2 Alberi binari
Possiamo distinguere diversi tipi di alberi. Iniziamo dai più semplici.
Albero binario è un albero in cui ogni nodo ha non più di due nodi figli, chiamati discendenti sinistro e destro.
Esempio di albero binario:
Tipi speciali di alberi binari:
Albero binario completo:
Tutti i livelli dell'albero, tranne l'ultimo, sono completamente riempiti e tutti i nodi dell'ultimo livello sono posizionati il più a sinistra possibile.
Albero binario perfetto:
Tutti i nodi interni hanno esattamente due nodi figli e tutte le foglie si trovano allo stesso livello.
Albero binario bilanciato:
La differenza di altezza tra i sottoalberi di qualsiasi nodo non supera 1.
Albero binario di ricerca:
Per qualsiasi nodo, il suo sottoalbero sinistro contiene solo nodi con valori minori, mentre il sottoalbero destro contiene solo nodi con valori maggiori.
2.3 Alberi n-ari
Un albero n-ario è un albero in cui ogni nodo può avere non più di n nodi figli.
Tipi speciali di alberi n-ari:
1. Albero ternario (Ternary Tree):
Ogni nodo ha non più di tre nodi figli.
2. Albero k-ario (k-ary Tree):
Ogni nodo ha non più di k nodi figli.
Esempio di albero 3-ario (ogni nodo ha non più di tre nodi figli):
2.4 Esempi di utilizzo degli alberi
1. File system
Applicazione degli alberi: Rappresentazione della struttura gerarchica di file e cartelle in un sistema operativo.
Il nodo radice rappresenta la directory principale, i nodi interni — le cartelle, e le foglie — i file. Le operazioni includono la creazione, l'eliminazione e lo spostamento di file e cartelle.
2. Albero decisionale
Applicazione degli alberi: Analisi e machine learning per prendere decisioni.
I nodi interni rappresentano domande o condizioni, i rami — risposte possibili, e le foglie — decisioni finali o azioni. Ad esempio, la diagnosi delle malattie in medicina in base ai sintomi.
3. Documento XML/HTML
Applicazione degli alberi: Rappresentazione strutturata dei dati in formato XML o HTML.
Il nodo radice rappresenta l'intero documento, i nodi interni — tag ed elementi, e le foglie — nodi di testo e attributi. Ciò aiuta nel parsing e manipolazione del contenuto dei documenti.
4. Struttura organizzativa
Applicazione degli alberi: Rappresentazione della gerarchia nelle organizzazioni e aziende.
Il nodo radice rappresenta il CEO, i nodi interni — i manager e i dipartimenti, e le foglie — i dipendenti. Ciò aiuta a visualizzare e gestire la struttura organizzativa.
5. Gioco degli scacchi
Applicazione degli alberi: Rappresentazione delle mosse possibili nel gioco.
Il nodo radice rappresenta lo stato iniziale del gioco, i nodi interni — mosse possibili, e le foglie — stati finali del gioco. Ciò aiuta nella pianificazione delle strategie e nelle decisioni nei programmi di scacchi.
GO TO FULL VERSION