C Academy · Lezione

Cercare e liberare

Trovi i nodi e liberi la memoria.

Cercare e liberare è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.

Ricerca in un BST

La ricerca sfrutta la regola di ordinamento. A ogni nodo si confronta il valore cercato con quello del nodo e si procede in uno solo dei sottoalberi.

Poiché a ogni passaggio si eliminano metà dei nodi rimanenti, il costo della ricerca dipende dall'altezza dell'albero, non dalla sua dimensione.

Ricerca ricorsiva

La ricerca ricorsiva ha due casi base: un sottoalbero vuoto significa che il valore non è stato trovato, mentre un valore corrispondente significa che è stato trovato.

Altrimenti si procede ricorsivamente a sinistra o a destra in base al confronto.

Node *search(Node *root, int target) {
    if (root == NULL || root->value == target)
        return root;
    if (target < root->value)
        return search(root->left, target);
    return search(root->right, target);
}

Ricerca iterativa

La ricerca può essere anche un semplice ciclo, evitando l'overhead della ricorsione.

Si seguono i puntatori verso il basso nell'albero finché si trova il valore cercato oppure si raggiunge la fine, indicata da NULL.

Node *search_iter(Node *root, int target) {
    while (root != NULL) {
        if (target == root->value) return root;
        root = (target < root->value)
             ? root->left : root->right;
    }
    return NULL;  /* not found */
}

La ricerca in azione

Questo programma costruisce un BST e cerca un valore presente e uno assente, stampando se ciascuno è stato trovato.

Un valore restituito diverso da NULL indica che il valore è stato trovato; NULL indica che non è presente nell'albero.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
Node *search(Node *r,int t){
    if(!r||r->value==t) return r;
    return t<r->value ? search(r->left,t) : search(r->right,t);
}

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("7:%s 99:%s\n",
        search(root,7)?"found":"no",
        search(root,99)?"found":"no");
    return 0;
}

Trovare il minimo

In un BST il valore più piccolo si trova nel nodo più a sinistra: si continua a seguire left finché non diventa NULL.

Analogamente, il massimo si trova nel nodo più a destra. Queste funzioni di supporto sono importanti per l'eliminazione e per le query su intervalli.

Node *find_min(Node *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

Perché è importante liberare la memoria

Ogni nodo proviene da malloc, quindi ogni nodo deve essere restituito con free. Dimenticare di liberarlo causa una perdita di memoria.

Tuttavia non è possibile liberare un nodo e poi leggere i puntatori ai suoi figli, quindi l'ordine di liberazione è fondamentale.

Liberare in post-order

Il modo sicuro per liberare un albero è il post-order: prima si liberano entrambi i figli, poi il nodo stesso.

In questo modo si garantisce che i puntatori left e right di un nodo vengano letti prima che la memoria di quel nodo sia rilasciata.

void free_tree(Node *root) {
    if (root == NULL) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

Un ordine errato pericoloso

Se si libera il nodo prima di procedere ricorsivamente nei suoi figli, si crea un comportamento indefinito: per raggiungere i sottoalberi si dereferenzia memoria già liberata.

Si tratta del classico bug use-after-free. Liberate sempre prima i figli.

/* WRONG: use-after-free */
void bad_free(Node *root) {
    if (!root) return;
    free(root);                 /* freed here */
    bad_free(root->left);       /* reads freed memory! */
    bad_free(root->right);
}

Evitare i puntatori pendenti

Dopo la restituzione di free_tree, il puntatore originale alla radice contiene ancora il vecchio indirizzo, ma la memoria non esiste più.

Reimpostarlo su NULL nel chiamante previene il riutilizzo accidentale di un puntatore pendente.

free_tree(root);
root = NULL;   /* avoid a dangling pointer */

Contare i nodi liberati

È possibile verificare che la liberazione funzioni contando i nodi durante la visita post-order e liberandoli subito dopo.

Questo programma costruisce un albero, lo libera e comunica quanti nodi sono stati rilasciati.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
int free_count(Node *r){
    if(!r) return 0;
    int c = free_count(r->left) + free_count(r->right);
    free(r);
    return c + 1;
}

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("freed=%d\n", free_count(root));
    root = NULL;
    return 0;
}

Cercare e liberare insieme

Un ciclo di vita completo: si costruisce l'albero, lo si cerca e infine lo si libera. Eseguire tutte e tre le operazioni mantiene i programmi corretti e privi di perdite di memoria.

Strumenti come Valgrind possono verificare che ogni chiamata a malloc abbia una corrispondente chiamata a free.

/* lifecycle
 * 1. insert values     (allocate)
 * 2. search as needed   (read-only)
 * 3. free_tree(root)    (deallocate)
 * 4. root = NULL        (avoid dangling)
 */

Verifica rapida

Ragionate sulla deallocazione sicura.

Riepilogo

La ricerca in un BST confronta il valore e scende in un solo sottoalbero a ogni passaggio, con un costo proporzionale all'altezza. Il minimo è il nodo più a sinistra, mentre il massimo è quello più a destra.

Liberate un albero in post-order, così i figli vengono rilasciati prima del padre, quindi impostate la radice su NULL per evitare un puntatore pendente.

Domande Frequenti

La lezione «Cercare e liberare» è gratuita?

Sì — il testo completo di «Cercare e liberare» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.

Cosa imparerò in «Cercare e liberare»?

Trovi i nodi e liberi la memoria. Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare C Academy?

Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.

Quanto tempo richiede la lezione «Cercare e liberare»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione C Academy?

Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a C Academy