Albero (informatica)


In informatica, un albero o struttura ad albero (tree in inglese) è la struttura dati che si riconduce al concetto di albero con radice presente nella teoria dei grafi. Un albero si compone di due tipi di sottostrutture fondamentali: il nodo, che in genere contiene informazioni, e l'arco, che stabilisce un collegamento gerarchico fra due nodi: si parla allora di un nodo padre dal quale esce un arco orientato che lo collega ad un nodo figlio.

Si chiede inoltre che ogni nodo possa avere al massimo un unico arco entrante, mentre dai diversi nodi possono uscire diversi numeri di archi uscenti. Si chiede infine che l'albero possegga un unico nodo privo di arco entrante: questo nodo viene detto radice (root) dell'albero. Ogni nodo che non presenta archi uscenti è detto foglia (leaf node) e in ogni albero finito, cioè con un numero finito di nodi, si trova almeno un nodo foglia. Ovviamente, un nodo può essere contemporaneamente padre (se ha archi uscenti) e figlio (se ha un arco entrante, ovvero se è diverso dalla radice).

Solitamente ogni nodo porta con sé delle informazioni e molto spesso anche una chiave con cui è possibile identificarlo univocamente all'interno dell'albero. L'altezza o profondità dell'albero è il massimo delle lunghezze dei suoi cammini massimali, cammini che vanno dalla radice alle sue foglie.

Indice

Tipi di albero


Principalmente gli alberi si dividono in alberi non ordinati e alberi ordinati. I primi non seguono alcuna regola per quanto riguarda le relazioni padre-figlio, mentre i secondi impongono che tra il nodo padre e i nodi figli ci sia un ben preciso ordinamento. I più utilizzati in ambito informatico sono sicuramente gli alberi ordinati. Un'altra classificazione può essere fatta in base al numero massimo di figli che un nodo può avere. Si può parlare dunque di Alberi binari in cui ogni nodo può avere al massimo due figli, oppure di Alberi n-ari in cui non vi è un limite al numero massimo di nodi figlio.

Un'ulteriore caratterizzazione è quella che si basa sul cosiddetto bilanciamento: un albero è perfettamente bilanciato se ha tutte le foglie al medesimo livello, ovvero se ogni foglia dell'albero ha la medesima distanza dalla radice. Un albero è \({\displaystyle \Delta }\)-bilanciato se, per ogni nodo N, detto K l'insieme dei massimi livelli raggiungibili seguendo tutte le foglie di N, la differenza tra il massimo ed il minimo di K non è maggiore di \({\displaystyle \Delta }\).

L'insieme di nodi al di sopra un nodo compone l'insieme dei predecessori, quelli che seguono sono i discendenti.

I tipi di albero più diffusi sono i seguenti:

Implementazioni


L'implementazione più diffusa degli alberi si basa su liste concatenate, ovvero da oggetti (i nodi) che referenziano altri oggetti.

Java

Un'interfaccia tipica di un nodo di un albero binario in Java può essere la seguente:

public class Nodo {
    public Nodo figlioSinistro;
    public Nodo figlioDestro;    //le informazioni contenute dal nodo, di tipo Object per generalizzare
    public Object informazioni;
    //una chiave univoca per identificare il nodo, ad esempio un intero
    public int chiaveUnivoca; 
}

Notoriamente, gli alberi heap sono implementabili anche tramite array o vettori

C

typedef int TKey;
typedef int TSat;
struct SInfo{
  TKey key;
  TSat satellite;
};
typedef struct SInfo TInfo;struct SNode {
  TInfo info;
  struct SNode *left;
  struct SNode *right;
};
typedef struct SNode TNode;
typedef TNode* TTree;
TTree tree_create(){
   return NULL;
}
TTree tree_destroy(TTree tree) {
   if(tree_empty(tree)==true)
     return NULL;
   else if((tree->left==NULL) && (tree->right==NULL)) {
     free(tree);
     return NULL;
   } else {
     tree->left = tree_destroy(tree->left);
     tree->right = tree_destroy(tree->right);
     free(tree);
     return NULL;
   }
}
TNode* tree_search_recursive(TTree tree, TKey key){
  if((tree_empty(tree)==true) || equal(tree->info.key, key))
    return tree;
  else {
    if(greater(key, tree->info.key))
      return tree_search_recursive(tree->right, key);
    else
      return tree_search_recursive(tree->left, key);
  }
}
TTree tree_insert_recursive(TTree tree, TInfo info){
  if(tree_empty(tree)==true){
    TNode* newnode;
    newnode=(TNode*) malloc(sizeof(TNode));
    if(newnode==NULL){
      printf("Errore di allocazione");
      exit(1);
    }
    newnode->right=newnode->left=NULL;
    newnode->info=info;
    return newnode;
  } else if(!greater(info.key,tree->info.key)){
    tree->left=tree_insert_recursive(tree->left,info);
    return tree;
  } else {
    tree->right=tree_insert_recursive(tree->right,info);
    return tree;
  }
}
TTree tree_delete_ver2(TTree tree, TKey key){
  if(tree_empty(tree)==true)             /* Albero vuoto */
    return NULL;
  else if(greater(tree->info.key, key)) {
                                         /* Cancellazione nel Ramo di Sinistra */
    tree->left=tree_delete_ver2(tree->left, key); 
    return tree;
  }
  else if(greater(key, tree->info.key)) { 
                                      /* Cancellazione nel Ramo di Destra */
    tree->right=tree_delete_ver2(tree->right, key);
    return tree;
  } else {                            /*tree->info.key==key */
                                     /*Cancellazione della Radice */
    TNode* min_right, *alias;
    if(tree_empty(tree->right)==true)
      alias=tree->left;
    else {
      min_right=tree_min(tree->right);
      min_right->left=tree->left;
      alias=tree->right;
    }
    free(tree);
    return alias;
  }
}

Visita di alberi in profondità


Molti algoritmi che operano sugli alberi richiedono di visitare tutti i nodi dell'albero, ovvero di definire un (sotto) algoritmo che dato un albero costruisce permutazione dell'insieme dei suoi nodi. I metodi di visita in profondità sono i seguenti.

void visitapreordine(Nodepointer start)
{
  if (start == NULL) return;
  
  start->markup = 1;
  printf(%d %d\n, start->valore, start->markup);  visitapreordine(start->son_sx);
  visitapreordine(start->son_dx);
 }

Nodepointer è un puntatore al nodo radice da cui parte la ricerca in pre-ordine. son_sx e son_dx sono rispettivamente i figli sinistro e destro del nodo da cui parte la ricerca. L'algoritmo descritto si limita a stampare a video il valore e il markup del nodo considerato.

void visitainordine(Nodepointer start)
{
  if (start == NULL) return;  visitainordine(start->son_sx);
  start->markup = 1;
  printf(%d %d\n, start->valore, start->markup);
  visitainordine(start->son_dx);
}

Nodepointer è un puntatore al nodo radice da cui parte la ricerca in ordine. son_sx e son_dx sono rispettivamente i figli sinistro e destro del nodo da cui parte la ricerca. L'algoritmo descritto si limita a stampare a video il valore e il markup del nodo considerato.

void visitapostordine(Nodepointer start)
{
  if (start == NULL) return;  visitapostordine(start->son_sx);
  visitapostordine(start->son_dx);
  start->markup = 1;
  printf(%d %d\n, start->valore, start->markup);}

Nodepointer è un puntatore al nodo radice da cui parte la ricerca in post-ordine. son_sx e son_dx sono rispettivamente i figli sinistro e destro del nodo da cui parte la ricerca. L'algoritmo descritto si limita a stampare a video il valore e il markup del nodo considerato.

Ciascun metodo può essere applicato in modo ricorsivo, ovvero per "visita di un sottoalbero" si intenderà l'applicazione dello stesso algoritmo di visita al nodo radice di tale sottoalbero. In alternativa è possibile implementare la visita in profondità facendo uso di una pila.

Un esempio di metodo esclusivamente non ricorsivo di visita di un albero è invece dato dalla visita in ampiezza.

Voci correlate


Altri progetti


Collegamenti esterni











Categorie: Alberi (strutture dati)




Data: 04.10.2021 08:21:16 CEST

Sorgente: Wikipedia (Autori [Cronologia])    Licenza: CC-BY-SA-3.0

Modifiche: Tutte le immagini e la maggior parte degli elementi di design correlati a questi sono stati rimossi. Alcune icone sono state sostituite da FontAwesome-Icons. Alcuni modelli sono stati rimossi (come "l'articolo ha bisogno di espansione) o assegnati (come" note "). Le classi CSS sono state rimosse o armonizzate.
Sono stati rimossi i collegamenti specifici di Wikipedia che non portano a un articolo o una categoria (come "Redlink", "collegamenti alla pagina di modifica", "collegamenti a portali"). Ogni collegamento esterno ha un'icona FontAwesome aggiuntiva. Oltre ad alcuni piccoli cambiamenti di design, sono stati rimossi i media container, le mappe, i box di navigazione, le versioni vocali e i geoformati.

Notare che Poiché il dato contenuto viene automaticamente prelevato da Wikipedia in un determinato momento, una verifica manuale è stata e non è possibile. Pertanto LinkFang.org non garantisce l'accuratezza e l'attualità del contenuto acquisito. Se ci sono informazioni che al momento sono sbagliate o che hanno una visualizzazione imprecisa, non esitate a Contattaci: e-mail.
Guarda anche: Impronta & Politica sulla riservatezza.