module · arbres binaires de recherche · 12 min
Un arbre où chaque comparaison divise l'espace de recherche en deux.
Insère, parcours, recherche : trois angles d'une même structure. Observe comment l'ordre d'insertion change la forme — et donc le coût des recherches futures.
taille
7
hauteur
3 (min 3)
équilibre
bon
insérer une clé
raccourcis
Cet arbre est compact : une recherche y coûtera au pire 3 comparaisons.
défi · la forme et son coût
palier 1 / 3
Pose ces clés dans un ORDRE qui garde l'arbre compact : hauteur ≤ 4. La banque contient un doublon — observe ce qu'il devient.
≤ 4 niveauxclés posées · 0 / 8
hauteur 0 / ≤ 4poser :
à retenir
- Un BST respecte l'invariant : pour chaque nœud, gauche < nœud < droite.
- L'ordre infixe d'un BST produit la séquence triée des clés.
- Recherche, insertion, suppression coûtent toutes O(h) où h est la hauteur.
- L'ordre d'insertion détermine la forme. Insérer en ordre trié donne un peigne (pire cas). Insérer des médianes donne un arbre équilibré.
- Les vrais BST de production (Red-Black, AVL) se rééquilibrent à chaque insertion pour rester en O(log n).