Alberi e heap in C

In questa pagina 3

Realizzazione in C degli ADT visti in Alberi binari, Alberi binari di ricerca e Heap. Premessa: Puntatori, struct e memoria dinamica in C e Liste concatenate in C; per le basi del C si vedano Puntatori in C, Strutture (struct) in C e Gestione della memoria in C, e per la ricorsione Ricorsione e Algoritmi ricorsivi.

Albero binario con nodi collegati

typedef struct nodo {
    int val;
    struct nodo *left;
    struct nodo *right;
} Nodo;

Nodo *nuovoNodo(int v) {
    Nodo *n = malloc(sizeof(Nodo));
    n->val = v;
    n->left = n->right = NULL;
    return n;
}

Definizione (albero binario in C come puntatore alla radice). L'albero è il puntatore alla radice (NULL = albero vuoto). Gli algoritmi ricorsivi seguono lo schema delle visite: caso base r == NULL, poi i due sottoalberi.

Esempio. Con Nodo *r = nuovoNodo(5); r->left = nuovoNodo(3); si ha contaNodi(r) == 2, altezza(r) == 1 e inorder(r) stampa 3 5.

Traccia di contaNodi(r) sull'albero con radice $5$ e figlio sinistro $3$ : contaNodi(5) $=1+$ contaNodi(3) $+$ contaNodi(NULL); contaNodi(3) $=1+0+0=1$ (i suoi figli sono NULL, caso base); quindi contaNodi(5) $=1+1+0=2$ . Per altezza: foglie $0$ , albero vuoto $-1$ (così una foglia vale $1+\max(-1,-1)=0$ , coerente con la definizione di altezza in Alberi); altezza(5) $=1+\max(\text{altezza}(3),\text{altezza}(\text{NULL}))=1+\max(0,-1)=1$ . La profondità della ricorsione, e quindi lo stack (Algoritmi ricorsivi, Stack e chiamata di funzioni in ARM), è pari all'altezza dell'albero più uno.

int contaNodi(const Nodo *r) {
    return r == NULL ? 0 : 1 + contaNodi(r->left) + contaNodi(r->right);
}

int altezza(const Nodo *r) {              /* albero vuoto: -1, foglia: 0 */
    if (r == NULL) return -1;
    int hl = altezza(r->left), hr = altezza(r->right);
    return 1 + (hl > hr ? hl : hr);
}

void inorder(const Nodo *r) {
    if (r == NULL) return;
    inorder(r->left);
    printf("%d ", r->val);
    inorder(r->right);
}

void liberaAlbero(Nodo *r) {              /* postorder: figli prima, poi il nodo */
    if (r == NULL) return;
    liberaAlbero(r->left);
    liberaAlbero(r->right);
    free(r);
}

Tutte visitano ogni nodo una volta: $\Theta(n)$ . liberaAlbero deve essere un postorder: liberando la radice per prima si perdono i puntatori ai figli (dopo free(r) leggere r->left sarebbe un uso di memoria rilasciata, un puntatore pendente). Sull'albero $5,3$ l'ordine delle free è prima il nodo $3$ , poi il nodo $5$ .

Definizione (inserimento in un albero binario di ricerca con doppio puntatore). La radice può cambiare (primo inserimento), quindi si passa Nodo **:
void addBST(Nodo **r, int v) {
    if (*r == NULL)
        *r = nuovoNodo(v);
    else if (v < (*r)->val)
        addBST(&(*r)->left, v);
    else if (v > (*r)->val)
        addBST(&(*r)->right, v);          /* chiave uguale: ignorata */
}

Esempio. Con addBST(&r, 30); addBST(&r, 40); addBST(&r, 24); la visita inorder stampa 24 30 40. Passo per passo: r vale NULL, quindi addBST(&r, 30) crea la radice $30$ (e la scrive in r: per questo serve Nodo **, come nelle liste, Liste concatenate in C). Per $40$ : *r non è NULL, $40>30$ , si chiama addBST(&(*r)->right, 40), dove *r ora è il campo right della radice, ancora NULL: si crea lì il nodo. Per $24$ : $24<30$ , si scende a sinistra e si crea il nodo nel campo left. È la ricerca di TreeSearch (Alberi binari di ricerca) con l'espansione della foglia, dove la "foglia" è un campo NULL.

Costo $\Theta(h)$ , con $h$ altezza dell'albero. Inserendo $30, 40, 24, 58, 48, 26, 11, 13$ la visita inorder stampa 11 13 24 26 30 40 48 58 (ordine crescente) e l'altezza è $3$ (verificato eseguendo il codice).

Per uno struct con più campi (ad esempio una entry chiave-valore) si definisce una struct Entry e il nodo contiene un campo Entry data; il confronto avviene sulla chiave. Per un campo aggiuntivo che dipende dai sottoalberi (es. il massimo dei valori del sottoalbero, vedi Alberi binari di ricerca) lo si aggiorna risalendo dopo l'inserimento ricorsivo.

Heap su array

Definizione (min-heap su array con indici da 1). Un min-heap (Heap) è un array h con indici da 1 (h[0] non si usa): figli di i in 2i e 2i+1, padre in i/2. last è il numero di entry.

Esempio. Con last = 7, i figli di i = 3 sono h[6] e h[7], e il padre di h[7] è h[3]. In C la divisione tra interi positivi tronca, quindi 7 / 2 == 3 coincide con $\lfloor 7/2\rfloor$ (Tipi, operatori e controllo del flusso in C); per questo h[i / 2] è il padre senza chiamare altre funzioni. Perché gli indici partono da $1$ si veda Heap (con indici da $0$ le formule si complicano).

void insert(int h[], int *last, int v) {
    int i = ++(*last);
    h[i] = v;
    while (i > 1 && h[i / 2] > h[i]) {        /* up-heap bubbling */
        int t = h[i]; h[i] = h[i / 2]; h[i / 2] = t;
        i /= 2;
    }
}

int indexMinChild(const int h[], int last, int i) {   /* richiede 2*i <= last */
    int res = 2 * i;
    if (res + 1 <= last && h[res + 1] < h[res]) res++;
    return res;
}

void downHeap(int h[], int last, int i) {
    while (2 * i <= last) {
        int j = indexMinChild(h, last, i);
        if (h[i] <= h[j]) break;
        int t = h[i]; h[i] = h[j]; h[j] = t;
        i = j;
    }
}

int removeMin(int h[], int *last) {
    int m = h[1];
    h[1] = h[(*last)--];                      /* l'ultima entry va in radice */
    downHeap(h, *last, 1);
    return m;
}

void bottomUp(int h[], int last) {            /* costruzione in O(n) */
    for (int k = last / 2; k >= 1; k--)
        downHeap(h, last, k);
}

Proprietà (costi di insert, removeMin e bottomUp in C). insert e removeMin costano $\Theta(\log n)$ , bottomUp $\Theta(n)$ (vedi Costruzione di uno heap). Prova: da 11 9 7 13 3 4, bottomUp produce 3 9 4 13 11 7; dopo insert(2) i due removeMin restituiscono $2$ e $3$ , e resta 4 9 7 13 11.

Esempio. Da 11 9 7 13 3 4, bottomUp produce 3 9 4 13 11 7; dopo insert(2), due removeMin restituiscono 2 e 3 e resta 4 9 7 13 11.

Traccia, con last = 6 e h = [3, 9, 4, 13, 11, 7] (indici da $1$ ):

operazione	array dopo	passi
`insert(2)`	`[3, 9, 4, 13, 11, 7, 2]` poi `[3, 9, 2, 13, 11, 7, 4]` poi `[2, 9, 3, 13, 11, 7, 4]`	`last` diventa $7$ ; $2$ in posizione $7$ ; $h[3]=4>2$ scambio; $h[1]=3>2$ scambio; fine
`removeMin()` $\to 2$	`[4, 9, 3, 13, 11, 7]` poi `[3, 9, 4, 13, 11, 7]`	`h[1] = h[last--]` porta $4$ in radice e `last = 6`; figlio minore tra $9$ e $3$ è $3$ (indice $3$ ): scambio; in posizione $3$ il figlio è $h[6]=7\ge4$ : stop
`removeMin()` $\to 3$	`[7, 9, 4, 13, 11]` poi `[4, 9, 7, 13, 11]`	$7$ in radice e `last = 5`; figli $9$ e $4$ : scambio con $4$ ; in posizione $3$ non ci sono figli ( $2\cdot3=6>5$ )

h[(*last)--] usa il valore corrente di *last come indice e dopo lo decrementa: l'ultima entry viene letta prima che last scenda. Il costo è quello descritto in Heap: ogni funzione sale o scende lungo un cammino, al più $\lfloor\log_2 n\rfloor$ passi.

Se l'array è passato senza h[0] libero (indici da 0) le formule diventano figli 2i+1, 2i+2 e padre (i-1)/2: va deciso una volta e mantenuto in tutte le funzioni. Un max-heap si ottiene invertendo i confronti; per un heap di struct con chiave e valore si confronta il campo giusto.

Errori comuni

Passare last per valore a insert/removeMin: la dimensione non si aggiorna.
In indexMinChild leggere h[2i+1] quando 2i+1 > last.
liberaAlbero in preorder (libera il nodo e poi legge i figli).
Usare Nodo * invece di Nodo ** nell'inserimento: il primo nodo non viene mai collegato.
Mescolare indici da 0 e da 1 nello stesso heap.

Versione ripasso

Nodo: struct nodo { int val; struct nodo *left, *right; } con nuovoNodo(v) (malloc, figli NULL). L'albero è il puntatore alla radice; NULL = albero vuoto (vedi Alberi binari).
contaNodi(r): r == NULL ? 0 : 1 + contaNodi(left) + contaNodi(right). altezza(r): vuoto $-1$ , foglia $0$ , altrimenti 1 + max(hl, hr). inorder: sinistro, stampa, destro. Tutte $\Theta(n)$ .
liberaAlbero: postorder (prima i figli, poi free(r)): liberare la radice per prima lascia puntatori pendenti.
addBST(Nodo **r, v): se *r == NULL crea il nodo; $v <$ val va a sinistra, $v >$ val a destra, la chiave uguale è ignorata; costo $\Theta(h)$ (vedi Alberi binari di ricerca). Serve Nodo ** perché la radice può cambiare, come nelle liste (Liste concatenate in C).
Esempio: addBST con $30, 40, 24$ dà inorder 24 30 40. Con $30, 40, 24, 58, 48, 26, 11, 13$ l'inorder è 11 13 24 26 30 40 48 58 e l'altezza $3$ .
Heap su array da indice 1: figli di $i$ $i$ in $2i$ $2 i$ e $2i+1$ $2 i + 1$ , padre $i/2$ $i /2$ (divisione intera); last passato per puntatore (vedi Heap).
- insert(h, last, v): i = ++(*last); h[i] = v;, poi up-heap finché h[i/2] > h[i]; $\Theta(\log n)$ .
- removeMin: m = h[1]; h[1] = h[(*last)--], poi downHeap(h, *last, 1); $\Theta(\log n)$ .
- bottomUp: downHeap da last/2 a $1$ ; $\Theta(n)$ (vedi Costruzione di uno heap).
Traccia: da 11 9 7 13 3 4 bottomUp dà 3 9 4 13 11 7; dopo insert(2) due removeMin restituiscono $2$ e $3$ , e resta 4 9 7 13 11.
Costi: insert e removeMin $\Theta(\log n)$ , bottomUp $\Theta(n)$ ; ogni funzione sale o scende lungo un cammino di al più $\lfloor\log_2 n\rfloor$ passi (vedi Heap).
Ricerca in addBST: è la TreeSearch di Alberi binari di ricerca in cui la "foglia" raggiunta è un campo NULL, che viene sostituito con un nuovo nodo.
Errori tipici: last passato per valore; leggere h[2i+1] oltre last; liberaAlbero in preorder; Nodo * invece di Nodo ** in addBST; indici 0 e 1 mescolati.

Alberi e heap in C

Albero binario con nodi collegati

Heap su array

Errori comuni

Esercizi su questo argomento

Teoria collegata