Albero binario di ricerca

Istruzioni

Inserisci e cerca numeri in un albero binario.

Quando dobbiamo rappresentare dati ordinati, un array non è una buona struttura dati.

Immaginiamo di avere l'array [1, 3, 4, 5] e di aggiungervi 2, che diventa così [1, 3, 4, 5, 2]. Ora dobbiamo ordinare di nuovo l'intero array! Possiamo migliorare la cosa rendendoci conto che dobbiamo solo creare spazio per il nuovo elemento [1, nil, 3, 4, 5] e poi inserirlo nello spazio che abbiamo creato. Ma questo ci obbliga comunque a spostare di una posizione molti elementi.

Gli alberi binari di ricerca, invece, possono operare su dati ordinati in modo molto più efficiente.

Un albero binario di ricerca è formato da una serie di nodi collegati. Ogni nodo contiene un dato (ad esempio il numero 3), una variabile chiamata left e una variabile chiamata right. Le variabili left e right puntano a nil oppure ad altri nodi. Dato che questi altri nodi hanno a loro volta altri nodi al di sotto, diciamo che le variabili left e right puntano a sottoalberi. Tutti i dati nel sottoalbero sinistro sono minori o uguali al dato del nodo corrente, e tutti i dati nel sottoalbero destro sono maggiori del dato del nodo corrente.

Ad esempio, se avessimo un nodo contenente il dato 4 e aggiungessimo il dato 2, il nostro albero sarebbe così:

      4
     /
    2

Se poi aggiungessimo 6, sarebbe così:

      4
     / \
    2   6

Se poi aggiungessimo 3, sarebbe così

       4
     /   \
    2     6
     \
      3

E se poi aggiungessimo 1, 5 e 7, sarebbe così

          4
        /   \
       /     \
      2       6
     / \     / \
    1   3   5   7

Crediti

Le immagini sono state create da habere-et-dispertire usando PGF/TikZ di Till Tantau.

Implementazione

Implementare una struttura ad albero efficiente e modificabile in Cairo (o in qualsiasi linguaggio puramente funzionale con memoria immutabile) è impegnativo, perché questi linguaggi sono progettati per evitare di modificare i dati dopo che sono stati creati. Questa immutabilità significa che, invece di aggiornare direttamente un nodo dell'albero, ogni volta che lo modifichi bisogna creare una nuova versione dell'albero.

Per mostrare perché accade questo, immagina una semplice struttura ad albero binario in cui ogni nodo ha un figlio sinistro e uno destro. Diciamo che partiamo da un piccolo albero come questo:

       1
      / \
     2   3

Ora, supponiamo di voler aggiungere un nuovo nodo 4 come figlio sinistro del nodo 2. In un linguaggio puramente funzionale (come in Cairo o Haskell), la memoria è immutabile, quindi non possiamo semplicemente aggiungere il nodo 4 direttamente a 2. Dobbiamo invece creare una nuova versione di ogni nodo lungo il percorso dalla radice al nodo modificato, perché ogni nodo lungo questo percorso ora punta a un sottoalbero nuovo o modificato.

Ecco come apparirebbe il processo:

1. Aggiungi il nodo 4 al nodo 2:

   • Crea una nuova versione del nodo 2, che ora ha 4 come figlio sinistro.

       2'
      / 
     4   
   

2. Aggiorna il nodo radice:

   • Poiché il nodo 1 originariamente puntava al vecchio 2, creiamo una nuova versione del nodo radice 1' che ora punta al nodo aggiornato 2' a sinistra e mantiene il nodo 3 a destra.

       1'
      / \
     2'  3
   

Quindi l'albero risultante diventa:

       1'
      / \
     2'  3
    /
   4

Questo nuovo albero (1') assomiglia ancora all'originale, ma con un percorso aggiornato. Il punto chiave è che abbiamo dovuto ricreare ogni nodo lungo il percorso (da 1 a 2) per preservare l'immutabilità, dato che i nodi esistenti non possono essere modificati sul posto. L'albero originale esiste ancora (per esempio, per tutti i riferimenti alla sua radice originale 1), mentre questo nuovo albero rappresenta lo stato modificato.

Negli alberi di grandi dimensioni, questo approccio può diventare costoso, perché ogni nuova modifica richiede di ricreare un percorso di nodi dalla radice al nodo aggiornato, anche se in realtà cambia solo una piccola parte dell'albero.