|
|
Gli elementi di un insieme A possono essere contenuti nei nodi di un albero binario B, detto albero binario di ricerca, che verifica le seguenti proprietà:
per ogni nodo u, tutti gli elementi contenuti nel sottoalbero radicato nel figlio sinistro di u sono minori dell’elemento contenuto in u;
L’operatore “appartiene” può essere implementato come una ricerca binaria sull’albero, dato che tale ricerca si basa sulla visita di un cammino radice-foglia. Lo schema di ricerca è simile a quello della ricerca binaria; si confronta l’elemento corrente con quello che si cerca, se non corrisponde si cerca nel sottoalbero a sinistra [destra] del nodo corrente se l’elemento cercato è minore [maggiore].
Supponiamo che sia h il massimo livello delle foglie allora “appartiene” ha complessità O(h). L’operatore “min” corrisponde a visitare il cammino che parte dalla radice ed è composto dai nodi a sinistra del nodo precedente.
Supponiamo che sia h il massimo livello delle foglie allora anche “min” è O(h). Per realizzare l’operatore “inserisci” occorre come prima cosa verificare l’appartenenza dell’elemento all’insieme. Tale ricerca ci indica, in caso di non appartenenza, in quale sottoalbero va inserito il nuovo elemento.
Supponiamo che sia h il massimo livello delle foglie allora anche “inserisci” è O(h). Per realizzare l’operatore cancella o cancellamin si verifica prima di tutto l’appartenenza dell’elemento u per individuarne la posizione e poi possiamo distinguere i tre seguenti casi:
se u non ha figli, si rimuove il nodo;
se u ha un solo figlio f, si rimuove u rendendo f figlio del padre di u;
se u ha due figli, si sostituisce l’elemento da cancellare x con il più piccolo elemento y tale che y>x. y sta nel nodo v raggiungibile scendendo sempre a sinistra nel sottoalbero radicato nel figlio destro di u. Si scambiano pi y con x ed x viene cancellato
Anche questi operatori hanno complessità O(h) dove h è il massimo livello delle foglie. Tutti gli operatori hanno quindi complessità O(h). Purtroppo però il livello massimo delle foglie h non è limitato superiormente da log n ma da n. Infatti, successivi inserimenti e cancellazioni possono portare ad un albero non bilanciato ma allungato che, nel caso pessimo, ha lunghezza O(n). Quindi per contenere h entro O(log n) occorre studiare opportuni operazioni per bilanciare il contenuto dell’albero. Per esempio, di seguito viene fatta una rotazione sul nodo 8 dopo l’ inserimento del nodo 9.
Vi sono strutture dati che sono state studiate appositamente per permettere una “facile” realizzazione del bilanciamento. Esse sono:
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.