PROFILPELAJAR.COM

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 a 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.

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 è $\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 e il minimo di $K$ non è maggiore di $\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:

Albero binario
Albero binario di ricerca, chiamato anche BST
Albero 2-3
Albero 2-3-4
Albero AVL
Heap
RB-Albero
B-Albero
Albero quadramentale
Albero ottale

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

Definizione struttura

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;

Creazione albero

TTree tree_create(){
   return NULL;
}

Distruzione albero

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;
   }
}

Ricerca elemento

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);
  }
}

Inserisci elemento

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;
  }
}

Elimina elemento

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.

Visita in pre-ordine: viene visitata prima la radice, dopo il sottoalbero sinistro e alla fine il sottoalbero destro

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.

Visita in ordine: Prima viene visitato il sottoalbero sinistro, poi la radice e alla fine il sottoalbero destro

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.

Visita in post-ordine: prima viene visitato il sottoalbero sinistro, poi quello destro e alla fine la radice

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.