Albero binario di ricerca

Istruzioni

Inserire e cercare numeri in un albero binario.

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

Supponiamo di avere l'array [1, 3, 4, 5] e di aggiungervi 2, così diventa [1, 3, 4, 5, 2]. Ora dobbiamo ordinare di nuovo l'intero array! Possiamo migliorare la situazione se ci rendiamo conto che ci serve solo fare spazio per il nuovo elemento [1, nil, 3, 4, 5] e poi inserire l'elemento nello spazio che abbiamo creato. Ma questo richiede comunque di spostare molti elementi di una posizione.

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

Un albero binario di ricerca è formato da una serie di nodi collegati tra loro. 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 sotto di sé, 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.

Per esempio, se avessimo un nodo che contiene il dato 4 ed aggiungessimo il dato 2, il nostro albero apparirebbe così:

      4
     /
    2

Se poi aggiungessimo 6, apparirebbe così:

      4
     / \
    2   6

Se poi aggiungessimo 3, apparirebbe così

       4
     /   \
    2     6
     \
      3

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

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

Crediti

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