Inserire in un BST
Costruisca un albero binario di ricerca.
Inserire in un BST è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 2 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.
La regola d'ordinamento dei BST
Un Binary Search Tree (BST) è un albero binario con una regola aggiuntiva: per ogni nodo, tutti i valori del sottoalbero sinistro sono minori e tutti quelli del sottoalbero destro sono maggiori.
Questo ordinamento consente di cercare, inserire ed eliminare elementi in un tempo proporzionale all'altezza dell'albero.
Dove inserire un valore
Per inserire un valore, partiamo dalla radice e facciamo un confronto. Se il nuovo valore è minore, andiamo a sinistra; se è maggiore, andiamo a destra.
Ripetiamo l'operazione finché raggiungiamo uno spazio vuoto (NULL), che è esattamente il punto in cui inserire il nuovo nodo.
/* insert 7 into:
* 10
* / \
* 5 15
* 7 < 10 -> left; 7 > 5 -> right of 5
*/L'helper create_node
L'inserimento crea nuovi nodi foglia, quindi riutilizziamo un costruttore che alloca e inizializza un nodo.
Entrambi i figli iniziano come NULL, perché un nodo appena inserito è sempre una foglia.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (!n) return NULL;
n->value = value;
n->left = n->right = NULL;
return n;
}Inserimento ricorsivo
La forma più semplice dell'inserimento è ricorsiva e restituisce la radice del sottoalbero, eventualmente nuova.
Se il sottoalbero è vuoto, restituiamo un nodo nuovo. Altrimenti ricorriamo a sinistra o a destra, ricolleghiamo il risultato e restituiamo la radice invariata.
Node *insert(Node *root, int value) {
if (root == NULL)
return create_node(value);
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
return root; /* equal: ignore duplicate */
}Perché restituire la radice
Restituire la radice del sottoalbero consente al genitore di ricollegare il riferimento con una sola riga: root->left = insert(root->left, v).
Quando il sottoalbero era vuoto, il nuovo nodo restituito diventa il figlio. Quando non lo era, viene restituita la stessa radice e il collegamento rimane invariato.
/* The assignment does double duty:
* - empty case: stores the new node
* - non-empty: stores the same pointer back (no-op)
*/
root->left = insert(root->left, value);Gestione dei duplicati
I BST reali devono stabilire come gestire i valori uguali. Una scelta comune consiste nell'ignorare i duplicati, come fa il nostro insert, che non prevede un ramo per il caso di uguaglianza.
Tra le alternative vi sono mantenere un conteggio per nodo oppure inviare sempre i duplicati da un lato specifico.
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
/* value == root->value -> do nothing */Creare un BST
L'inserimento di una sequenza di valori produce un albero la cui forma dipende dall'ordine di inserimento.
Qui inseriamo diversi numeri e stampiamo i figli immediati della radice per verificare che la regola d'ordinamento sia rispettata.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *create_node(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 create_node(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 main(void){
Node *root = NULL;
int data[] = {10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,data[i]);
printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
return 0;
}Un inserimento iterativo
È possibile inserire elementi anche senza ricorrere alla ricorsione. Scendiamo nell'albero con un puntatore, memorizzando il genitore, finché troviamo uno spazio vuoto.
Poi colleghiamo il nuovo nodo al lato corretto del genitore.
void insert_iter(Node **rootp, int value) {
Node *cur = *rootp, *parent = NULL;
while (cur) {
parent = cur;
cur = (value < cur->value) ? cur->left : cur->right;
}
Node *n = create_node(value);
if (!parent) *rootp = n;
else if (value < parent->value) parent->left = n;
else parent->right = n;
}L'ordine di inserimento determina la forma dell'albero
Inserire 1,2,3,4,5 in ordine crescente crea un albero degenerato simile a una lista concatenata, con un'altezza pari al numero di elementi.
Inserire i valori in un ordine bilanciato mantiene l'altezza vicina a log(n). Il bilanciamento influisce direttamente sulla velocità di ricerca.
/* sorted insert 1..5 ->
* 1
* \
* 2
* \
* 3 (height = 4, like a list)
*/Costo dell'inserimento
Ogni inserimento percorre un unico cammino dalla radice a una foglia, quindi richiede un lavoro proporzionale all'altezza dell'albero.
In un albero bilanciato si tratta di circa log(n) confronti; in un albero degenerato può arrivare a n. Ecco perché esistono gli alberi autobilancianti.
Demo completo di inserimento
Questo programma inserisce dei valori, quindi conta i nodi per verificare che siano stati memorizzati cinque valori distinti e che un duplicato sia stato ignorato.
Il duplicato 10 non aumenta il conteggio perché insert scarta i valori uguali.
#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 count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int main(void){
Node *root=NULL;
int d[]={10,5,15,10,20};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("count=%d\n", count(root));
return 0;
}Verifica rapida
Ragionate sul comportamento dell'inserimento.
Riepilogo
L'inserimento in un BST confronta il nuovo valore con ciascun nodo: procede a sinistra per i valori minori e a destra per quelli maggiori, finché trova una posizione vuota.
La forma ricorsiva restituisce la radice del sottoalbero, così il nodo padre può ricollegare correttamente i riferimenti. Il costo dell'inserimento dipende dall'altezza dell'albero, quindi l'ordine di inserimento è importante.
Domande Frequenti
La lezione «Inserire in un BST» è gratuita?
Sì — il testo completo di «Inserire in un BST» è 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 «Inserire in un BST»?
Costruisca un albero binario di ricerca. 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 2 di 4.
Quanto tempo richiede la lezione «Inserire in un BST»?
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
- Nodi e struttura degli alberi
- Inserire in un BST
- Attraversamenti
- Cercare e liberare