Rappresentazione mediante una lista¶

Supponiamo di avere un albero come quello nella figura seguente, i cui nodi contengono chiavi intere tutte diverse in un intervallo limitato \([0,b]\).

Figura 1: Un albero di interi tutti diversi

Possiamo rappresentare questo albero attraverso una semplice lista lunga \(b\) che in posizione \(i\) ha la chiave del padre del nodo con chiave \(i\). Eccetto la radice che ha come padre se stessa.

Le chiavi dell’albero nella figura sopra sono tutte diverse e comprese nell’intervallo \([0,14]\). Tale albero può quindi essere memorizzato attraverso la seguente lista.

Figura 2: La lista corrispondente (il valore N sta per None)

Anche se le chiavi non sono intere, ma sono tutte diverse, come nella figura seguente, possiamo usare un dizionario, associando ad ogni chiave il suo unico padre.

Figura 3: Un albero di caratteri tutti diversi

Dobbiamo però aver presente, che se data una chiave, vogliamo l’elenco di tutti i suoi figli, è necessario scorrere l’intera lista (o tutti i valori del dizionario), anche se i figli sono un numero costante, per esempio 2. Dunque tale operazione ci costa \(O(n)\), dove n è il numero di nodi dell’albero.