Vi siete mai arrampicati su un albero ?
- Alberi binari e database -

(Aggiornamento dell'articolo al 11/05/2011)
Non ridete! E’ proprio così: un elaboratore per cercare un dato richiesto fra i numerosi archiviati in un database (elenco clienti, fornitori, scritture contabili) di una ditta o di un qualsiasi ente, si arrampica proprio su un albero … si, un albero particolare: un albero binario.
Dobbiamo, prima di dare una definizione di albero binario, fare alcune considerazioni generali su come vengono archiviati i dati in un supporto di memoria di massa (hard disk) e come questi possono essere successivamente ricercati da un calcolatore utilizzando un programma apposito. Analogamente a quanto noi esseri umani facciamo nello stilare un elenco di nominativi come per esempio un elenco di clienti di una ditta scrivendoli uno dopo l’altro su un registro cartaceo, anche un computer fa la stessa cosa inserendo i dati uno dopo l’altro senza lasciare spazi in settori dell’hard disk e catalogando con un nome il contenitore (file) dei dati stessi: ad esempio il file clienti. La posizione del dato nel file viene determinata in modo non visibile all’utente finale, ma solo conosciuto dal programma, da un puntatore numerico che determina quindi in modo univoco la posizione fisica del dato stesso. Allo stesso modo noi potremmo numerare le righe del nostro registro cartaceo e stabilire che ad ogni riga venga a corrispondere un nominativo dell’elenco.
Se nell’hard disk il puntatore determina la posizione fisica del dato da ricercare, possiamo ordinare, attraverso il nostro programma, alla testina magnetica imputata alla lettura di posizionarsi nella zona determinata dal puntatore numerico a quel dato specifico e quindi di leggerlo.
Il grosso problema che sorge, se gli elementi del nostro elenco di nominativi sono stati inseriti a caso, e quindi di per se in modo non ordinato, è che non poteremo mai conoscere o comunque avvicinarci a quello da ricercare se non ordinando all’elaboratore di leggere tutto in sequenza dal primo fino all’ultimo dato e fermarsi quando quest’ultimo è stato trovato.
Questo tipo di ricerca si chiama ricerca sequenziale. E’ evidente che tutto può funzionare egregiamente con questo algoritmo se l’elenco dei nominativi è composto da poche centinaia di elementi: un elaboratore ci metterebbe, nel peggiore dei casi, una piccola frazione di secondo a seguire lo schema previsto (lettura in sequenza di ogni singolo elemento fino al dato richiesto) e terminare poi l’elaborazione, ma se gli elementi, come spesso accade nei più diffusi database sono diverse migliaia o addirittura centinaia di migliaia, il tempo dell’elaborazione diventerebbe esageratamente troppo lungo per qualsiasi utente specialmente poi se il nominativo ricercato venga a trovarsi in fondo all’elenco.
Per ovviare a questo problema, dobbiamo ordinare l’elenco che, se si tratta di un elenco di nominativi può essere fatto ordinando alfabeticamente tutti gli elementi (ordine conosciuto anche da un elaboratore la “a” viene prima della “b” come “1” viene prima del “2” ecc.).

Un elenco telefonico, ad esempio, è un insieme di nominativi ordinati alfabeticamente.
Per costruire un algoritmo (insieme di istruzioni eseguibili da un computer) capace di ricercare in modo veloce un elemento in un insieme ordinato, dobbiamo prendere come esempio il nostro comportamento nel ricercare un nome sull’elenco telefonico. Di solito noi apriamo l’elenco a circa metà e se dopo aver letto il primo nome, quello da ricercare viene prima alfabeticamente ricerchiamo ancora aprendo la metà inferiore o al contrario ,se viene dopo, quella superiore ripetendo l’operazione fino a giungere alla pagina giusta.
Questo tipo di ricerca viene più comunemente chiamata ricerca binaria perché fa sempre riferimento normalmente nella ricerca a due insiemi di una metà: quello inferiore e quello superiore. Ovviamente se dobbiamo aggiungere un nominativo ad un elenco telefonico saremmo sempre costretti a ristamparlo integralmente e se l’elemento da aggiungere in modo ordinato deve essere incastonato all’interno, anche a ristampare tutte le pagine facendo slittare tutti gli elementi che seguono di una posizione.
La cosa non è altrettanto pensabile nell’inserimento di dati in un archivio elettronico; lo slittamento di posizioni di tutta una serie di dati per mantenere l’ordinamento comporta sempre una riscrittura ed è sempre una cosa laboriosa e lunga anche da parte di un elaboratore. Si è pensato così di mantenere la posizione fisica degli elementi uno dopo l’altro in ordine di inserimento e di ordinarli solo in modo logico e quindi non fisico aggiungendo in fase di inserimento del dato due informazioni numeriche aggiuntive ad esso e solo ad uso del programma: una rappresenta il puntatore all’elemento che lo precede in ordine alfabetico e l’altro rappresenta quello che lo segue. Per convenzione il puntatore inferiore è il primo a sinistra, il superiore quello a destra. Ricordo sempre che il puntatore rappresenta le coordinate della posizione fisica che deve assumere la testina di lettura/scrittura per leggere o scrivere il dato corrispondente.
In questo modo i dati collegati ad una coppia di puntatori, si possono rappresentare a forma di albero detto anche albero binario.

In questo tipo di alberi, alla radice, (il primo elemento inserito) seguono via, via i successivi seguendo il puntatore superiore per elementi che seguono e quello inferiore per quelli che lo precedono. I dati a cui ne seguono altri (puntatori non nulli) si chiamano nodi, quelli terminali (puntatori nulli) si chiamano foglie. Gli alberi binari si rappresentano graficamente capovolti (convenzione): la radice in alto,  nodi e foglie via, via sotto.
Se seguite passo dopo passo gli algoritmi qui rappresentati per l'inserimento dei dati e quello per la ricerca, vedrete che nel primo caso l’albero viene costruito e nel secondo invece visitato appunto per la ricerca; è, come vi avevo accennato all’inizio, se nel cercare un dato l’elaboratore si arrampicasse su un albero. Nella ricerca di un qualsiasi elemento su una guida o su un vocabolario, noi facciamo la stessa cosa, ma ormai quasi per tutto noi ci affidiamo ai computer: forse … troppo pigri per arrampicarci ancora ?     :-)
La trattazione dell’argomento non finisce qui, vi mostrerò in seguito gli algoritmi di cancellazione di un elemento e di riordino di un albero. Vi segnalerò un grossissimo problema per questo tipo di archiviazione: lo sbilanciamento degli alberi e tutto ciò che ne comporta e poi qualche accenno su programmi di bilanciamento (compattazione archivi). Seguirà una breve guida sui collegamenti di più tabelle e archivi e vi porterò (mah! …) fino a progettare un gestionale completo.    
Se farete tesoro di tutto ciò che ho detto fino ad ora sull’argomento, tutto il resto vi sembrerà una passeggiata !!
 
Vedi: Alberi di f.Camuso