|
|
Sia dato un insieme finito ed ordinato di elementi detti nodi. Se tale insieme è non vuoto, allora un particolare nodo è designato come radice, ed i rimanenti nodi, se esistono, sono a loro volta partizionati in insiemi ordinati disgiunti. Una struttura dati cosi costruita è detta albero ordinato o più semplicemente albero. Un albero è una struttura fondamentale che si presta a rappresentare svariate situazioni:
partizioni successive di un insieme in sottoinsiemi disgiunti;
organizzazione gerarchiche di dati;
procedimenti enumerativi o decisionali.
Un esempio di albero ordinato può essere un albero genealogico di una dinastia, che divide gerarchicamente i suoi membri in successive generazioni, a partire dal progenitore:
Altro esempio di albero può essere un albero decisionale in cui ci sono dei nodi di scelta (quelli con ?). Il ramo a sinistra corrisponde a si (test positivo), il ramo a destra corrisponde a no (test negativo).
La terminologia usata nel trattare gli alberi è uno strano misto di termini matematici, botanici e di parentela:
L’ albero ordinato può essere interpretato come una generalizzazione di una sequenza lineare, in cui ciascun elemento ha un solo predecessore (padre) e più successori (figli). Una lista può essere vista come un particolare albero con un’ unica foglia e in cui ogni nodo ha al più un figlio. Analogamente alle operazioni sulle liste, quelle definite sugli alberi ordinati, prevedono la possibilità di spostarsi da un nodo ad un suo parente (figlio fratello o padre), ed inoltre di inserire o cancellare interi sottoalberi. Le operazioni tipiche degli alberi sono:
Operatori di creazione
CREALBERO: per creare un albero
Operatori di interrogazione
ALBEROVUOTO: per verificare che l’ albero sia vuoto;
Operatori di selezione
RADICE: per accedere direttamente alla radice di un albero;
PADRE: per accedere al padre di un nodo;
PRIMOFIGLIO: per accedere al primo figlio di un nodo;
SUCCFRATELLO: per accedere al fratello successivo di un nodo;
Operatori di controllo
FOGLIA: per controllare che un nodo non abbia figli;
FINEFRATELLI: per controllare che siano stati considerati tutti i fratelli;
Operatori di modifica
INSRADICE: per inserire la radice in un albero vuoto;
INSSOTTOALBERO: per inserire un sottoalbero;
CANCSOTTOALBERO: per cancellare un sottoalbero.
La specifica sintattica di questi operatori è la seguente:
Indichiamo con il termini “albero” l ‘insieme di tutti gli alberi ordinati, come definiti precedentemente, e con T un generico albero ordinato. La specifica semantica, con relative precondizioni e postcondizioni, sarà la seguente:
Gli effetti delle operazioni INSSOTTOALBERO e CANSOTTOALBERO sono chiariti nella seguente figura:
Per saperne di più consulta i seguenti approfondimenti:
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.