Arbres et graphes visualisés

La recherche est rapide - à chaque nœud, on sait s'il faut aller à gauche ou à droite :

Find 6 in the BST above:
  Start at 8 → 6 < 8, go left
  At 3 → 6 > 3, go right
  At 6 → Found it!

Complexité : O(log n) pour un arbre équilibré - la même magie logarithmique que la recherche binaire sur un tableau trié.

Graphes - Tout est connecté

Un graphe généralise les arbres en supprimant la contrainte hiérarchique. Il se compose de nœuds (ou sommets) et d'arêtes (connexions entre nœuds). Les arêtes peuvent être :

• Orientées (sens unique : A → B) ou non orientées (bidirectionnelles : A ↔ B)
• Pondérées (chaque arête a un coût/distance) ou non pondérées

Social network (undirected):
  Alice - Bob - Charlie
    \       |
     Diana - Eve

Road map (weighted, directed):
  London →(2h)→ Birmingham →(1.5h)→ Manchester

Les graphes sont partout

• Réseaux sociaux : les personnes sont des nœuds ; les amitiés sont des arêtes.
• Internet : les pages web sont des nœuds ; les hyperliens sont des arêtes.
• Cartes routières : les intersections sont des nœuds ; les routes sont des arêtes pondérées.
• Systèmes de recommandation : utilisateurs et produits sont des nœuds ; les interactions sont des arêtes.

Comment l'IA utilise les arbres

Arbres de décision

L'un des modèles d'IA les plus interprétables est l'arbre de décision. Il pose une série de questions oui/non pour classifier les données :

Is temperature > 30°C?
├── Yes: Is humidity > 70%?
│   ├── Yes: "Don't play tennis"
│   └── No: "Play tennis"
└── No: Is it windy?
    ├── Yes: "Don't play tennis"
    └── No: "Play tennis"

Les arbres de décision sont populaires car les humains peuvent les lire - crucial en santé, finance et droit où l'explicabilité compte.

Forêts aléatoires (Random Forests)

Une forêt aléatoire construit des centaines d'arbres de décision, chacun entraîné sur un sous-ensemble légèrement différent, puis fait un vote. Cette approche d'ensemble est plus précise et robuste qu'un seul arbre.

Comment l'IA utilise les graphes

Graphes de connaissances

Un graphe de connaissances stocke des faits sous forme de relations : (London) --[capital_of]--> (United Kingdom). Le Knowledge Graph de Google alimente les panneaux d'information dans les résultats de recherche.

Graphes de recommandation

Netflix, Spotify et Amazon modélisent utilisateurs et produits comme un graphe. Si A et B ont aimé X et Y, et que A a aussi aimé Z, le graphe suggère Z à B - c'est le filtrage collaboratif.

Parcours - Explorer les arbres et graphes

Parcours en profondeur (DFS)

Le DFS explore aussi loin que possible le long d'un chemin avant de revenir en arrière.

    A → B → D → E → C → F

Le DFS utilise une pile (via la récursion ou explicitement). Idéal pour : résoudre des labyrinthes, détecter des cycles, tri topologique.

Parcours en largeur (BFS)

Le BFS explore tous les voisins au niveau courant avant d'aller plus profond - comme des ondulations dans l'eau.

    A → B → C → D → E → F

Le BFS utilise une file d'attente. Idéal pour : plus court chemin (graphe non pondéré), degrés de séparation, crawling web.

Points clés à retenir

• Les arbres modélisent les données hiérarchiques - systèmes de fichiers, HTML et arbres de décision IA.
• Les BST permettent des recherches en O(log n) en maintenant une hiérarchie triée.
• Les graphes modélisent les données interconnectées - réseaux sociaux, bases de connaissances, moteurs de recommandation.
• DFS (avec pile) va en profondeur ; BFS (avec file) va en largeur - les deux alimentent des algorithmes IA fondamentaux comme PageRank.