Insérer dans un BST
Construisez un arbre binaire de recherche.
Insérer dans un BST est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.
La règle de classement d'un BST
Un arbre binaire de recherche (BST) est un arbre binaire auquel s'ajoute une règle : pour chaque nœud, toutes les valeurs de son sous-arbre gauche sont plus petites et toutes celles de son sous-arbre droit sont plus grandes.
Ce classement permet d'effectuer les recherches, insertions et suppressions en un temps proportionnel à la hauteur de l'arbre.
Où placer une valeur
Pour insérer une valeur, nous partons de la racine et effectuons des comparaisons. Si la nouvelle valeur est plus petite, nous allons à gauche ; si elle est plus grande, nous allons à droite.
Nous répétons l'opération jusqu'à atteindre un emplacement vide (NULL), qui est précisément l'endroit où le nouveau nœud doit être placé.
/* insert 7 into:
* 10
* / \
* 5 15
* 7 < 10 -> left; 7 > 5 -> right of 5
*/L'assistant create_node
L'insertion crée de nouveaux nœuds feuilles ; nous réutilisons donc un constructeur qui alloue et initialise un nœud.
Les deux enfants commencent à NULL, car un nœud nouvellement inséré est toujours une feuille.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (!n) return NULL;
n->value = value;
n->left = n->right = NULL;
return n;
}Insertion récursive
La manière la plus claire d'insérer est d'utiliser la récursion et de renvoyer la racine du sous-arbre, éventuellement nouvelle.
Si le sous-arbre est vide, nous renvoyons un nœud neuf. Sinon, nous poursuivons récursivement à gauche ou à droite, rattachons le résultat, puis renvoyons la racine inchangée.
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 */
}Pourquoi renvoyer la racine
Renvoyer la racine du sous-arbre permet au parent de rétablir le lien en une seule ligne : root->left = insert(root->left, v).
Si le sous-arbre était vide, le nouveau nœud renvoyé devient l'enfant. Sinon, la même racine est renvoyée et le lien reste inchangé.
/* 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);Gérer les doublons
Les BST réels doivent décider quoi faire des valeurs égales. Un choix courant consiste à ignorer les doublons, comme le fait notre insert, qui ne prévoit aucun cas pour les valeurs égales.
On peut aussi conserver un compteur par nœud ou envoyer systématiquement les doublons du même côté.
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 */Construire un BST
Insérer une suite de valeurs produit un arbre dont la forme dépend de l'ordre d'insertion.
Nous insérons ici plusieurs nombres et affichons les enfants directs de la racine pour vérifier que la règle de classement est respectée.
#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;
}Une insertion itérative
Vous pouvez également insérer sans récursion. Nous descendons dans l'arbre avec un pointeur, en mémorisant le parent, jusqu'à trouver un emplacement vide.
Nous rattachons ensuite le nouveau nœud du côté approprié de ce parent.
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'ordre d'insertion façonne l'arbre
Insérer 1,2,3,4,5 dans l'ordre croissant produit un arbre dégénéré qui ressemble à une liste chaînée, avec une hauteur égale au nombre d'éléments.
Insérer les valeurs dans un ordre équilibré maintient la hauteur proche de log(n). L'équilibre influe directement sur la vitesse de recherche.
/* sorted insert 1..5 ->
* 1
* \
* 2
* \
* 3 (height = 4, like a list)
*/Coût de l'insertion
Chaque insertion parcourt un chemin allant de la racine à une feuille ; son travail est donc proportionnel à la hauteur de l'arbre.
Pour un arbre équilibré, cela représente environ log(n) comparaisons ; pour un arbre dégénéré, cela peut atteindre n. C'est pourquoi les arbres auto-équilibrés existent.
Démonstration complète de l’insertion
Ce programme insère des valeurs, puis compte les nœuds afin de confirmer que cinq valeurs distinctes ont été stockées et qu’un doublon a été ignoré.
Le doublon 10 n’augmente pas le compteur, car insert ignore les valeurs égales.
#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;
}Vérification rapide
Réfléchissez au comportement de l’insertion.
Récapitulatif
L’insertion dans un BST compare la nouvelle valeur à chaque nœud, se dirigeant vers la gauche pour une valeur plus petite et vers la droite pour une valeur plus grande, jusqu’à trouver un emplacement vide.
La forme récursive renvoie la racine du sous-arbre afin que le parent puisse rétablir proprement les liens. Le coût de l’insertion dépend de la hauteur de l’arbre : l’ordre d’insertion est donc important.
Questions Fréquemment Posées
La leçon « Insérer dans un BST » est-elle gratuite ?
Oui — le texte complet de « Insérer dans un BST » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Insérer dans un BST » ?
Construisez un arbre binaire de recherche. Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer C Academy ?
Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Insérer dans un BST » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon C Academy ?
Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Nœuds et structure d’un arbre
- Insérer dans un BST
- Parcours
- Rechercher et libérer