Alberi Binari di Ricerca

3.1 Definizione di un albero binario di ricerca (BST)

Un albero binario di ricerca (BST) è un albero binario con le seguenti proprietà:

• Per ogni nodo, il suo sottoalbero sinistro contiene solo nodi con chiavi minori rispetto alla chiave del nodo stesso.
• Per ogni nodo, il suo sottoalbero destro contiene solo nodi con chiavi maggiori rispetto alla chiave del nodo stesso.
• Entrambi i sottoalberi di ciascun nodo sono anch'essi alberi binari di ricerca.

Esempio di BST:

BST è l'acronimo di Binary Search Tree – letteralmente «Albero Binario di Ricerca». In pratica è un’organizzazione di dati a forma di “albero”, attraverso il quale è possibile effettuare ricerche molto rapidamente. La struttura ad albero è infatti una sorta di ordinamento nascosto/astuto degli elementi.

Visita in-order

Scopo della visita — Formare una lista di nodi (o dati dai nodi, questione di terminologia e rilevanza pratica) in un certo modo. La visita in-order (simmetrica) è una visita in cui la radice dell'albero si colloca tra i risultati delle visite corrispondenti al sottoalbero sinistro e destro.

Insieme alla proprietà dell'albero binario di ricerca (riguardante le disuguaglianze, vedi teoria) questo implica che la visita in-order di un albero binario di ricerca ci fornirà una lista ordinata di nodi – fantastico! Ecco come si presenterà la visita del suddetto albero:

3.2 Principi di funzionamento e proprietà dei BST

Principi di funzionamento:

• Organizzazione dei dati: Il BST organizza i dati in modo da garantire una ricerca, inserimento e cancellazione degli elementi efficaci.
• Struttura ricorsiva: Ogni nodo del BST obbedisce alle stesse regole della radice dell'albero, rendendo la struttura ricorsiva.
• Equilibrio: Per garantire un'ottima performance il BST deve essere equilibrato, cioè l'altezza dei sottoalberi sinistro e destro deve essere pressoché uguale.

Proprietà dei BST:

• Ordinamento: In qualsiasi momento è possibile visitare l'albero in ordine "in-order" (sottoalbero sinistro → nodo corrente → sottoalbero destro), per ottenere tutti gli elementi in ordine ordinato.
• Tempo delle operazioni:
  • In media il tempo di esecuzione delle operazioni di ricerca, inserimento e cancellazione è O(log n), dove n è il numero di nodi.
  • Nel peggiore dei casi (se l'albero non è equilibrato) il tempo delle operazioni può raggiungere O(n).
• Chiavi uniche: Tutte le chiavi in un BST devono essere uniche per mantenere l'ordinamento.

3.3 Operazioni principali

1. Inserimento (Insertion):

Principio di funzionamento:

• Iniziamo dal nodo radice.
• Confrontiamo la chiave del nuovo nodo con la chiave del nodo corrente.
• Se la nuova chiave è inferiore, procediamo verso il sottoalbero sinistro, se è maggiore – verso il destro.
• Ripetiamo il processo finché non troviamo un posto adatto per l'inserimento del nuovo nodo (ovvero, manca o il figlio sinistro o destro).

Algoritmo:

1. Se l'albero è vuoto, il nuovo nodo diventa il nodo radice.
2. Altrimenti troviamo ricorsivamente il posto giusto e aggiungiamo il nuovo nodo.

2. Cancellazione (Deletion):

Principio di funzionamento:

• Individua il nodo da eliminare.
• Considera tre casi:
• Il nodo è una foglia (non ha figli): semplicemente rimuoviamo il nodo.
• Il nodo ha un figlio: sostituiamo il nodo con il suo figlio.
• Il nodo ha due figli: troviamo il nodo più piccolo nel sottoalbero destro (o il più grande nel sinistro), copiamo il suo valore nel nodo da eliminare e rimuoviamo ricorsivamente il nodo più piccolo nel sottoalbero destro.

Algoritmo:

1. Trova il nodo con la chiave specificata.
2. A seconda del caso, esegui la cancellazione appropriata e redistribuzione dei nodi.

3. Ricerca (Search):

Principio di funzionamento:

• Iniziamo dal nodo radice.
• Confrontiamo la chiave del nodo cercato con la chiave del nodo corrente.
• Se la chiave coincide, restituiamo il nodo.
• Se la chiave è inferiore, procediamo verso il sottoalbero sinistro, se è maggiore – verso il destro.
• Ripetiamo il processo finché non troviamo il nodo con la chiave cercata o non raggiungiamo la fine dell'albero (in questo caso il nodo non è trovato).

Algoritmo:

1. Se l'albero è vuoto o la chiave del nodo coincide con quella cercata, restituiamo il nodo.
2. Se la chiave del nodo cercato è inferiore, cerchiamo ricorsivamente nel sottoalbero sinistro.
3. Se la chiave del nodo cercato è maggiore, cerchiamo ricorsivamente nel sottoalbero destro.

3.4 Esempi di problemi risolti con l'uso dei BST

1. Ricerca di un elemento in un insieme dinamico

È necessario mantenere un insieme di numeri, in cui è possibile aggiungere nuovi elementi, eliminare quelli esistenti e cercare rapidamente se un determinato numero è presente nel set.

Soluzione usando BST:

• Inserimento di nuovi elementi nell'albero.
• Rimozione di elementi esistenti.
• Ricerca di elementi nell'albero.

Esempio di utilizzo:

Mantenimento di un elenco di utenti registrati in un sistema, dove gli utenti possono essere aggiunti e rimossi, e il sistema deve rapidamente verificare se un utente è registrato.

2. Trovare l'elemento minimo e massimo

È necessario trovare rapidamente i valori minimi e massimi in un set di dati.

Soluzione usando BST:

• L'elemento minimo si trova nel nodo più a sinistra dell'albero.
• L'elemento massimo si trova nel nodo più a destra dell'albero.

Esempio di utilizzo:

Mantenimento di un sistema che monitora i prezzi delle azioni, dove è necessario trovare rapidamente il prezzo minimo e massimo al momento corrente.

3. Verifica dell'equilibrio dell'espressione

Data un'espressione matematica, è necessario verificarne l'equilibrio per quanto riguarda il numero di parentesi aperte e chiuse.

Soluzione usando BST:

Usiamo il BST per memorizzare stati intermedi nella verifica dell'equilibrio delle parentesi.

Esempio di utilizzo:

Parsing e compilazione del codice, dove è necessario verificare la corretta disposizione delle parentesi nelle espressioni.

4. Costruzione di un dizionario

È necessario creare una struttura di dati per memorizzare un dizionario, in cui le parole possono essere aggiunte, eliminate e trovate rapidamente.

Soluzione usando BST:

• Le parole vengono aggiunte all'albero in ordine alfabetico.
• La ricerca delle parole avviene tramite chiavi.

Esempio di utilizzo:

Sistema di autocorrezione del testo, dove è necessario trovare e correggere rapidamente le parole.