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.

Istruzioni specifiche per CoffeeScript

Un'istanza di BinarySearchTree deve avere tre proprietà: data, left e right.

Un'istanza deve avere questi metodi:

• insert che aggiunge un nuovo dato all'albero. Questo aggiungerà un nuovo nodo «foglia» da qualche parte nell'albero.
• each che accetta un argomento «callback». Cioè una funzione che verrà chiamata su ogni dato dell'albero in ordine.

Questo esercizio è un ottimo posto per fare pratica con la ricorsione.