Gestione degli alberi binari • Softzone

albin è un programma in C a scopo didattico per la gestione degli alberi binari di ricerca. Si usa da un prompt interattivo e permette di creare un albero (con valori casuali, di dimensione data o caricato da file), salvarlo, cancellarne i nodi e visualizzarlo con diversi algoritmi di visita e di stampa. Completano il programma una semplice calcolatrice per espressioni e alcuni comandi di conversione tra basi numeriche.

In questo articolo vediamo le parti del codice che riguardano gli alberi.

Alberi binari di ricerca

Un albero binario è formato da nodi, ciascuno con al più due figli, detti sinistro e destro. In un albero binario di ricerca i valori rispettano una proprietà d’ordine: per ogni nodo, tutti i valori del sottoalbero sinistro sono minori o uguali al valore del nodo e tutti quelli del sottoalbero destro sono maggiori.

Questa proprietà permette di cercare, inserire e cancellare un valore percorrendo un solo cammino dalla radice verso le foglie, con un costo proporzionale all’altezza dell’albero: circa log n per un albero bilanciato di n nodi, ma fino a n nel caso peggiore, per esempio quando i valori vengono inseriti già ordinati e l’albero degenera in una lista.

In albin ogni nodo contiene, oltre al valore e ai due figli, anche il puntatore al padre, che semplifica il calcolo del successore e la cancellazione:

typedef struct node {
	data d;
	struct node *parent;
	struct node *left;
	struct node *right;
} node;

Negli esempi che seguono useremo l’albero ottenuto inserendo, in quest’ordine, i valori 15 6 18 3 7 17 20 2 4 13 9:

        +-20
   +-18-+
   |    +-17
15-+
   |         +-13-+
   |         |    +-9
   |    +-7-+
   +-6-+
        |    +-4
        +-3-+
             +-2

La stampa è ruotata di 90 gradi: la radice è a sinistra e il sottoalbero destro è disegnato sopra quello sinistro.

Ricerca, minimo e massimo

La ricerca scende dalla radice andando a sinistra o a destra a seconda del confronto, finché non trova il valore o non esce dall’albero:

node *search(data d, node *r) {
	while(r != NULL && d != r -> d)
		if(d < r -> d)
			r = r -> left;
		else
			r = r -> right;
	return r;
}

Il minimo si trova scendendo sempre a sinistra, il massimo sempre a destra:

node *minimum(node *r) {
	while(r -> left != NULL)
		r = r -> left;
	return r;
}

Inserimento

Il nuovo valore viene inserito come foglia. Si scende dalla radice come per la ricerca, tenendo traccia in y dell’ultimo nodo visitato, che diventerà il padre del nuovo nodo:

void insert(data d, node *r) {
	node *n, *y;

	if((n=malloc(sizeof(node)))==NULL) {
		fatal("Malloc Failed\n", 0);
	}
	n->d = d; n->left=n->right=NULL;
	y = NULL;
	while(r != NULL) {
		y = r;
		if(d <= r -> d)
			r = r -> left;
		else r = r -> right;
	}
	n -> parent = y;
	if(d <= y -> d)
		y -> left = n;
	else y -> right = n;
}

I valori uguali finiscono nel sottoalbero sinistro. Il caso dell’albero vuoto è gestito dal chiamante, che crea la radice con create().

Successore e predecessore

Il successore di un nodo è il nodo con il valore immediatamente superiore. I casi sono due:

se il nodo ha un sottoalbero destro, il successore è il minimo di quel sottoalbero;
altrimenti si risale verso la radice finché non si arriva da un figlio sinistro: il padre di quel figlio è il successore.

node *successor(node *r) {
	node *y;
	if(r -> right != NULL)
		return minimum(r -> right);
	y = r -> parent;
	while(y!=NULL && r==y ->right) {
		r = y;
		y = y -> parent;
	}
	return y;
}

Nell’albero di esempio il successore di 13 è 15: 13 non ha figlio destro, quindi si risale da 13 a 7 e da 7 a 6, sempre da figli destri, fino ad arrivare a 15 dal suo figlio sinistro 6.

Il predecessore è simmetrico: massimo del sottoalbero sinistro, oppure risalita fino a un figlio destro.

Cancellazione

La cancellazione di un nodo r distingue tre casi:

r è una foglia: si elimina direttamente;
r ha un solo figlio: il figlio prende il suo posto;
r ha due figli: si copia in r il valore del suo successore, che ha al più un figlio, e si elimina il successore.

Il codice riconduce i tre casi a uno solo, scegliendo il nodo y da rimuovere fisicamente:

void delete(node **root, node *r) {
	node *y, *x;
	if (!r) return;
	if(r->left==NULL || r->right==NULL)
		y = r;
	else y = successor(r);
	if(y -> left != NULL)
		x = y -> left;
	else x = y -> right;
	if(x != NULL)
		x -> parent = y -> parent;
	if(y -> parent == NULL)
		*root = x;
	else if(y == y -> parent -> left)
		y -> parent -> left = x;
	else y -> parent -> right = x;
	if(y != r)
		r -> d = y -> d;
	free(y);
}

y è r stesso se ha al più un figlio, altrimenti il suo successore; x è l’eventuale figlio di y, che viene collegato al padre di y. La radice è passata per indirizzo perché può cambiare. Cancellando 6, che ha due figli, il suo posto viene preso dal successore 7:

        +-20
   +-18-+
   |    +-17
15-+
   |    +-13-+
   |    |    +-9
   +-7-+
        |    +-4
        +-3-+
             +-2

Visite ricorsive

Visitare un albero significa elaborare tutti i suoi nodi in un certo ordine. Le tre visite classiche differiscono solo per il momento in cui viene elaborato il nodo rispetto ai suoi sottoalberi:

preorder: nodo, sottoalbero sinistro, sottoalbero destro;
inorder: sottoalbero sinistro, nodo, sottoalbero destro;
postorder: sottoalbero sinistro, sottoalbero destro, nodo.

In albin l’elaborazione è affidata a una funzione passata come parametro, così la stessa visita serve per la stampa (do_print) e per la liberazione della memoria (do_free):

void walk_tree_ino(DataTypePtr r, void (*exec_func)(DataTypePtr))
{
	if (r != NULL)
	{
		walk_tree_ino(r->left, exec_func);
		exec_func(r);
		walk_tree_ino(r->right, exec_func);
	}
}

Le versioni preorder e postorder spostano soltanto la chiamata a exec_func. Sull’albero di esempio:

preorder:  15 6 3 2 4 7 13 9 18 17 20
inorder:   2 3 4 6 7 9 13 15 17 18 20
postorder: 2 4 3 9 13 7 6 17 20 18 15

La visita inorder di un albero di ricerca restituisce i valori in ordine crescente. La postorder elabora ogni nodo dopo i suoi figli ed è quindi quella adatta a liberare la memoria: un nodo viene deallocato quando i suoi sottoalberi non servono più.

Visite iterative

Le stesse visite si possono scrivere senza ricorsione, gestendo esplicitamente uno stack di puntatori ai nodi. È lo stack che nella versione ricorsiva viene gestito implicitamente dalle chiamate di funzione.

Nella visita inorder si scende a sinistra impilando i nodi incontrati; quando non si può più scendere si estrae un nodo, lo si elabora e si riparte dal suo figlio destro:

void walk_tree_iter_ino(DataTypePtr albero, void (*exec_func)(DataTypePtr))
{
  stack coda;

  reset(&coda);
  while (True) {
	  for (; albero; albero = albero->left)
	  {
		  push(albero, &coda);
	  }
	  if (!empty(&coda)) {
		  albero = pop(&coda);
		  exec_func(albero);
		  albero = albero->right;
	  } else { break; }
  }
}

La preorder è analoga, ma il nodo viene elaborato quando viene impilato invece che quando viene estratto.

La postorder è la più delicata, perché un nodo può essere elaborato solo dopo entrambi i sottoalberi. Il nodo in cima allo stack viene quindi solo letto con top() e la variabile comingUp indica se si sta risalendo da un figlio. Se si risale dal figlio sinistro e c’è un figlio destro si scende in quest’ultimo, altrimenti il nodo può essere elaborato ed estratto:

void walk_tree_iter_posto(DataTypePtr albero, void (*exec_func)(DataTypePtr))
{
  boolean comingUp = False;
  stack coda;

  reset(&coda);

  while (True)
  {
    if (!comingUp)
    {
      if (albero)
      {
        push(albero, &coda);
        albero = albero->left;
      }
      else
        comingUp = True;
    }
    else
    {
      DataTypePtr c = albero;

      if (empty(&coda)) break;
      albero = top(&coda);

      if (c == albero->left && albero->right)
      {
         albero = albero->right;
         comingUp = False;
      }
      else
      {
        exec_func(albero);
        pop(&coda);
      }
    }
  }
}

Le versioni iterative producono esattamente le stesse sequenze di quelle ricorsive.

Sostituendo lo stack con una coda si ottiene una visita diversa, che non ha un equivalente ricorsivo altrettanto naturale: la visita per livelli, che elabora la radice, poi i suoi figli, poi i nipoti e così via. Ogni nodo estratto dalla testa della coda accoda i propri figli in fondo:

  testa = fondo = 0;
  coda[fondo++] = albero;

  while (testa < fondo) {
    a = coda[testa++];
    exec_func(a);   /* analizza il nodo in testa alla coda */
    if (a->left)
	  coda[fondo++] = a->left;   /* mette in coda i figli */
    if (a->right)
	  coda[fondo++] = a->right;
  }

La coda è un array allocato con count(albero) elementi, sufficiente perché ogni nodo vi entra una sola volta. Sull’albero di esempio la visita per livelli restituisce 15 6 18 3 7 17 20 2 4 13 9, che è anche l’ordine di inserimento usato per costruirlo.

Stampa e salvataggio

Oltre alle visite, albin offre due rappresentazioni dell’intera struttura.

La prima è una forma testuale con parentesi, in cui ogni nodo è scritto come ( valore sinistro destro ) e l’albero vuoto come (). È anche il formato usato per il salvataggio su file:

void print_tree(FILE *fd, DataTypePtr albero)
{
  if (albero == NULL) {
    fprintf(fd, "()");
    return;
  }
  fprintf(fd, "( %d ", albero->d);
  print_tree(fd, albero->left);
  print_tree(fd, albero->right);
  fprintf(fd, " )");
}

( 15 ( 6 ( 3 ( 2 ()() )( 4 ()() ) )( 7 ()( 13 ( 9 ()() )() ) ) )( 18 ( 17 ()() )( 20 ()() ) ) )

La seconda è la stampa grafica già vista negli esempi. Il sottoalbero destro viene stampato prima della radice e quello sinistro dopo; un array di flag indica, per ogni livello, se va tracciata la barra verticale che collega un nodo al fratello ancora da stampare.

Uso del programma

All’avvio albin presenta un prompt in cui digitare i comandi. help ne mostra l’elenco e help comando la guida del singolo comando:

Comando	Funzione
`create -r` / `create -n num`	crea un albero con un numero casuale di nodi o con `num` nodi, riempito di valori casuali
`load file` / `save file`	carica o salva l’albero
`print opzione`	stampa l’albero con la visita o il formato scelto
`delete valore`	cancella un nodo
`clear`	distrugge l’albero corrente e libera la memoria
`calc "espressione"`	valuta un’espressione aritmetica
`hex`, `oct`, `dec`	convertono un numero tra le basi

Le opzioni di print sono -PRr, -PIr, -POr per le visite ricorsive preorder, inorder e postorder, -PRi, -PIi, -POi per le corrispondenti iterative, -PL per la visita per livelli, -Gg per la stampa grafica, -Gp per quella indentata con parentesi e -Pn per la forma con parentesi su una riga. Gli argomenti composti da più parole vanno racchiusi tra virgolette.

albin> load esempio.txt
Eseguito
albin> print -PIr
Albero generato: nodi 11

-
print_tree_ino()
2 3 4 6 7 9 13 15 17 18 20
-
albin> delete 6
Node found at 0x600002e9d140
Nodo cancellato

Il programma è stato sviluppato sotto Linux, ma compila anche con Microsoft Visual C++ tramite Makefile.win32.

Allegati

albin.tar.gz