Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Ernesto Burattini » 17.Alberi binari ordinati


Definizione

Un albero binario è ordinato, e viene anche chiamato albero binario di ricerca, binary search tree (BST), quando il campo chiave di ogni nodo è minore del campo chiave di ogni nodo del suo sottoalbero destro ed è maggiore del campo chiave di ogni nodo del suo sottoalbero sinistro.

Un esempio di BST

In questo caso l’ordine è quello lessicografico.

In questo caso l'ordine è quello lessicografico.


Un esempio di BST (segue)

Gli stessi dati possono essere contenuti in alberi BST di forma diversa.

Gli stessi dati possono essere contenuti in alberi BST di forma diversa.


Albero  bilanciato

Un albero si dice bilanciato se il livello di tutte le foglie è uguale all’altezza dell’albero o a questa stessa altezza meno 1.

Un albero si dice bilanciato se il livello di tutte le foglie è uguale all'altezza dell'albero o a questa stessa altezza meno 1.


Albero non bilanciato

L’albero è non bilanciato in quanto ci sono foglie al livello 2  e foglie ai livelli 3, 4, 5.

L'albero è non bilanciato in quanto ci sono foglie al livello 2 e foglie ai livelli 3, 4, 5.


Albero binario

Se un albero è bilanciato allora per fare una ricerca di una chiave in esso contenuta si esplora in un numero di passi inferiore a quello necessario per esplorare un albero non bilanciato.

Come si può osservare nell’esempio degli alberi mostrati nella figura successiva pur essendo tutti alberi BST la ricerca della chiave Riccardo viene fatta in un numero di passi decisamente diverso a seconda se l’albero è o non bilanciato.

Albero binario


Albero binario

Se un albero bilanciato ha M livelli, il numero di nodi di cui è formato può variare tra

2M e 2(M+1) -1

In un albero bilanciato il numero di passi massimo di ricerca è di O(log2 (N)) dove N è il numero di nodi.

Albero bilanciato con  M livelli

Da questa immagine si ricava facilmente che il numero di nodi N di un albero bilanciato, nota l’altezza dell’albero pari a M (o M+1) è data: (vedi figura).


Albero bilanciato con  M livelli (segue)


Albero bilanciato con  M livelli (segue)

Per trovare, quindi, una chiave in un dato BST, se esso è bilanciato il numero massimo di passi è dato dall’altezza dell’albero M. Poichè abbiamo mostrato che 2MN≤2M+1-1.

Da questa espressione per ricavare N, supposto M abbastanza grande, e quindi -1 trascurabile abbiamo:
N ≅ 2M da cui  M log2N

Quindi per un albero bilanciato, con N nodi, il numero di passi massimo per trovare una chiave è pari O(log2N), nel caso l’albero non fosse bilanciato il massimo numero di passi sarà pari a O(N).

Albero binario

Nella figura è illustrato il caso peggiore per il quale la ricerca può essere, nel caso peggiore fatta in O(N) passi.

Si può dimostrare che un albero di ricerca binario costruito in maniera casuale, quindi non necessariamente bilanciato, effettua in media un numero di passi per effettuare la ricerca pari a 1.36 * O(log2(N)).


Albero binario (segue)

Per avere un’idea della differenza che intercorre tra i valori O(N), log2(N) e 1.36* log(N) riportiamo nella tabella che segue i valori delle tra funzioni corrispondenti a diversi valori di N.


Albero binario (segue)

Di seguito ci rifaremo alla seguente struct per definire un nodo di un albero:

struct RTnodo
{
int key;
RTnodo *left, *right;
};
typedef RTnodo* Tnodo;

Per esplorare un albero vi sono tre diverse modalità.

Algoritmi di attraversamento di BST

INORDER. Visitare tutti i nodi di un BST di interi, attraversando:

  • il sotto albero sinistro;
  • la radice;
  • il sotto albero destro;

PREORDER. Visitare tutti i nodi di un BST di interi, attraversando:

  • la radice;
  • il sotto albero sinistro;
  • il sotto albero destro;

POSTORDER. Visitare tutti i nodi di un BST di interi, attraversando:

  • il sotto albero sinistro;
  • il sotto albero destro;
  • la radice;

I codici per gli attraversamenti


I codici per gli attraversamenti

Dato l’albero di figura (foto in alto)
un esempio di output è riprodotto nella foto in basso.
Allegato: visite

Per utilizzare il codice visite è necessario costruire un file di nome TREE1 .txt in cui vanno inserite le chiavi dei singoli nodi dell’albero che si vuole costruire.


Operazioni sui BST

Poiché ogni nodo di un BST punta ad altri due nodi, ciascuno dei quali è una variabile dinamica di tipo struct avremo che una variabile di tipo RTnodo, cioè un puntatore alla radice di un BST, è a sua volta una variabile BST, e può quindi essere passata da un blocco ad un altro.

In altre parole dato un nodo di un BST, questo è radice per i suoi sottoalberi e i nodi a cui punta sono a loro volta radici di altri sottoalberi.

Pertanto possiamo adoperare ricorsivamente queste variabili.

Operazioni sui BST (segue)

Le principali operazioni che ci interessa definire sono:

  • Creazione di un albero
  • Inserimento di un nuovo nodo con un valore assegnato al campo dati Key e NULL ai campi Left e Right
  • Cancellazione di un nodo
  • Selezionare un nodo data una chiave
  • Fornire informazioni sull’albero (altezza, numero nodi, livelli, figli, etc.)

I materiali di supporto della lezione

visite

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion