Alberi e heap in C

Realizzazione in C degli ADT visti in Alberi binariAlbero binario e albero binario proprio; interfaccia; relazioni tra nodi, foglie e altezza (m = n-m+1, h+1 <= m <= 2^h, 2h+1 <= n <= 2^(h+1)-1) con dimostrazioni; visita inorder; parse tree e valutazione di espressioni; heightSum come esempio di calcolo di un'informazione più ricca.Alberi binari →, Alberi binari di ricercaAlbero binario di ricerca come albero binario proprio con entry nei nodi interni e foglie vuote; inorder crescente; TreeSearch; get, put e remove (due casi, con predecessore inorder) in Theta(h); altezza fino a n-1; esempi di inserimenti; alberi aumentati con campi size e max e algoritmi di conteggio e interrogazione in O(h).Alberi binari di ricerca → e HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap →. Premessa: Puntatori, struct e memoria dinamica in CPuntatori e passaggio per riferimento in C, array e aritmetica dei puntatori, stringhe, struct e typedef con l'operatore ->, malloc e free, puntatore a puntatore per modificare una testa; compilazione con Makefile; errori tipici (puntatori pendenti, perdite di memoria, off-by-one).Puntatori, struct e memoria dinamica in C → e Liste concatenate in CLista singolarmente concatenata in C con nodo struct e testa passata per riferimento (Nodo **); addHead, addTail ricorsiva e iterativa, pop, inversione in loco, liberazione; coda con puntatori a testa e coda; ricorsione sulle liste; costi.Liste concatenate in C →.

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;
}

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.

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.

Inserimento in un albero binario di ricerca. 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 */
}

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 ricercaAlbero binario di ricerca come albero binario proprio con entry nei nodi interni e foglie vuote; inorder crescente; TreeSearch; get, put e remove (due casi, con predecessore inorder) in Theta(h); altezza fino a n-1; esempi di inserimenti; alberi aumentati con campi size e max e algoritmi di conteggio e interrogazione in O(h).Alberi binari di ricerca →) lo si aggiorna risalendo dopo l'inserimento ricorsivo.

Heap su array

Un min-heap (HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.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.

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);
}

insert e removeMin costano $\Theta(\log n)$, bottomUp $\Theta(n)$ (vedi Costruzione di uno heapCostruire uno heap da un array di n entry: approccio top-down con n-1 insert, Theta(n log n); approccio bottom-up con down-heap dalle foglie verso la radice, Theta(n), con dimostrazione della somma; esempi svolti, in loco; unione di due alberi con heap-order.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.

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.