Arbres binaires et BST 🌳

Imagine un organigramme d'entreprise : le PDG est en haut, les directeurs en dessous, les managers encore en dessous, et chaque employé a un supérieur. C'est exactement comme ça que fonctionne un arbre !

1. Qu'est-ce qu'un arbre ? 🌲

Un arbre est une structure de données hiérarchique composée de nœuds reliés par des arêtes.

Exécution pas à pas
pseudo
1/6
▶️STRUCTURE Noeud
STRUCTURE NoeudLe programme exécute cette action, puis passe à la suivante.
Le programme exécute cette instruction, puis passe à la suivante.

Vocabulaire important

Terme	Définition	Exemple
Racine	Nœud principal (sans parent)	Le PDG
Feuille	Nœud sans enfant	Un employé sans subordonné
Hauteur	Distance max entre racine et feuille	3 niveaux hiérarchiques
Profondeur	Distance entre la racine et un nœud	Un manager est à profondeur 2

Exemple d'arbre binaire

📐 Dans cet arbre :

Racine = 50

Feuilles = 20, 40, 60, 80 (aucun enfant)

Hauteur = 3 (50 → 30 → 20 : 3 niveaux)

Profondeur de 40 = 2 (50 → 30 → 40)

2. Arbre Binaire de Recherche (BST) 🔍

Propriété fondamentale d'un BST :

💡 Pour chaque nœud :

Gauche → valeurs plus petites que le nœud

Droit → valeurs plus grandes que le nœud

Cette règle s'applique récursivement à tous les sous-arbres

C'est ce qui rend la recherche si rapide : à chaque étape, on élimine la moitié des possibilités (comme une recherche dichotomique) !

3. Insertion dans un BST ➕

Exécution pas à pas
pseudo
1/14
🧩FONCTION inserer(racine, valeur)
FONCTION inserer(racine, valeur)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "inserer(racine, valeur)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.


def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

Pas à pas : insérer 25 dans [20, 30, 40, 50] :

Racine = 50. 25 < 50 → on va à gauche

Nœud = 30. 25 < 30 → on va à gauche

Nœud = 20. 25 > 20 → on va à droite

20.droit est vide → on crée le nœud 25 ici ! → Résultat : [20 → 25 → 30 → 40 → 50] ✅

4. Recherche dans un BST 🔎

Exécution pas à pas
pseudo
1/12
🧩FONCTION rechercher(racine, valeur)
FONCTION rechercher(racine, valeur)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "rechercher(racine, valeur)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.


def search(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return search(root.left, val)
    return search(root.right, val)

Exemple : Chercher 40 dans [50, 30, 70, 20, 40, 60, 80]

40 < 50 → gauche

40 > 30 → droite

40 == 40 → Trouvé ! (seulement 3 étapes au lieu de 7 !)

Dans un tableau, on aurait dû parcourir 4 éléments en moyenne. Ici on a fait 3 étapes. Pour 1 million de données, BST ≈ 20 étapes (O(log n)) contre 500 000 (O(n)) pour un tableau.

5. Parcours d'arbres 🚶

Il y a 3 façons de parcourir un arbre binaire, selon l'ordre dans lequel on visite les nœuds.

In-order : Gauche → Racine → Droite

Exécution pas à pas
pseudo
1/8
🧩FONCTION parcours_infixe(racine)
FONCTION parcours_infixe(racine)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "parcours_infixe(racine)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

Résultat avec [50, 30, 70, 20, 40, 60, 80] : 20 30 40 50 60 70 80 → Les valeurs sont triées ! C'est la magie du BST.

Pre-order : Racine → Gauche → Droite

Exécution pas à pas
pseudo
1/8
🧩FONCTION parcours_préfixe(racine)
FONCTION parcours_préfixe(racine)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "parcours_préfixe(racine)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

Résultat : 50 30 20 40 70 60 80 → Utile pour copier un arbre (on crée la racine, puis les enfants).

Post-order : Gauche → Droite → Racine

Exécution pas à pas
pseudo
1/8
🧩FONCTION parcours_postfixe(racine)
FONCTION parcours_postfixe(racine)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "parcours_postfixe(racine)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

Résultat : 20 40 30 60 80 70 50 → Utile pour supprimer un arbre (on supprime les feuilles d'abord).

Code complet en Python


def inorder(root):      # Gauche → Racine → Droite
    if root:
        inorder(root.left)
        print(root.val, end=" ")
        inorder(root.right)

def preorder(root):     # Racine → Gauche → Droite
    if root:
        print(root.val, end=" ")
        preorder(root.left)
        preorder(root.right)

def postorder(root):    # Gauche → Droite → Racine
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val, end=" ")

# Utilisation
root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)

inorder(root)    # 20 30 40 50 60 70 80   ← trié !
print()
preorder(root)   # 50 30 20 40 70 60 80
print()
postorder(root)  # 20 40 30 60 80 70 50

6. Complexités ⚡

Opération	Moyen (arbre équilibré)	Pire cas (déséquilibré)
Recherche	O(log n)	O(n)
Insertion	O(log n)	O(n)
Suppression	O(log n)	O(n)

⚠️ Le pire cas arrive quand on insère des valeurs déjà triées : [1, 2, 3, 4, 5] → l'arbre devient une liste chaînée déguisée (que des fils droits) !

Les arbres AVL ou rouge-noir corrigent ce problème en se rééquilibrant automatiquement.

Exercices pour toi 🎯

1. Hauteur d'un arbre 📏

Exécution pas à pas
pseudo
1/9
🧩FONCTION hauteur(racine)
FONCTION hauteur(racine)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "hauteur(racine)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

2. Arbre équilibré ? ⚖️

Un arbre équilibré a une différence de hauteur ≤ 1 entre ses sous-arbres gauche et droit, pour tous les nœuds.

Exécution pas à pas
pseudo
1/8
🧩FONCTION est_équilibré(racine)
FONCTION est_équilibré(racine)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "est_équilibré(racine)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

3. Plus proche ancêtre commun (LCA) 👨‍👦

Trouver le nœud le plus profond qui est ancêtre de deux valeurs données.


def lca(root, v1, v2):
    if not root:
        return None
    if v1 < root.val and v2 < root.val:
        return lca(root.left, v1, v2)   # Les deux sont à gauche
    if v1 > root.val and v2 > root.val:
        return lca(root.right, v1, v2)  # Les deux sont à droite
    return root  # L'un à gauche, l'autre à droite → je suis le LCA !

Teste ces exercices dans la Sandbox pour voir les arbres en action ! 🎮

⚡ Simulateur — Arbres binaires

Étape 1/16

📝 Pseudo-code

1# Arbre binaire de recherche

2class Noeud:

3 def __init__(self, valeur):

4 self.valeur = valeur

5 self.gauche = None

6 self.droit = None

8# Insertion BST

9def inserer(racine, valeur):

10 if not racine: return Noeud(valeur)

11 if valeur < racine.valeur:

12 racine.gauche = inserer(racine.gauche, valeur)

13 else:

14 racine.droit = inserer(racine.droit, valeur)

15 return racine

17# Parcours infixe (gauche, racine, droite)

18def infixe(noeud):

19 if noeud:

20 infixe(noeud.gauche)

21 print(noeud.valeur)

22 infixe(noeud.droit)

🌳 Arbre binaire

null (arbre vide)

💡 Propriétés BST

Gauche : valeurs plus petites
Droit : valeurs plus grandes
Insertion / Recherche : O(log n) en moyenne
Infixe → résultat trié

Arbre binaire : chaque nœud a 0, 1 ou 2 enfants.