Arbre Binaire de Recherche (ABR)
Insertion, recherche, tri par parcours infixe
Enonce
Implémenter :
- inserer(racine, val) — insère val dans l'ABR, retourne la nouvelle racine
- rechercher(racine, val) — True si val est dans l'ABR
- tri_par_abr(T) — trie T en construisant un ABR puis en faisant un parcours infixe
⚠ Question : Quelle est la complexité de tri_par_abr dans le pire cas ? Quand est-ce qu'il est atteint ?
Signature attendue
class Noeud:
def inserer(racine, val):
def rechercher(racine, val) -> bool:
def tri_par_abr(T: list) -> list:Exemples
tri_par_abr([5, 3, 8, 1, 4, 7, 9])→[1, 3, 4, 5, 7, 8, 9]tri_par_abr([3, 3, 3])→[3] (pas de doublons dans l'ABR)
📖 Rappel de cours
Un arbre binaire de recherche (ABR) est un arbre binaire qui respecte la propriété :
Propriété d'un ABR :
Pour tout nœud $n$ de valeur $v$ :
- toutes les valeurs du sous-arbre gauche sont $< v$,
- toutes les valeurs du sous-arbre droit sont $> v$.
Conséquence magique : le parcours infixe d'un ABR donne les valeurs dans l'ordre croissant.
Complexités : $O(h)$ pour insertion et recherche. $h = O(\log n)$ si l'arbre reste équilibré, $h = O(n)$ dans le pire cas (insertions triées = arbre dégénéré en liste).
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Plus Longue Sous-séquence Commune (LCS)
- Détection de Cycle (Floyd)
- Arbres Binaires — Parcours et Hauteur
- Tri par Tas (Heap Sort)
- Algorithme de Kadane
- Chemins dans une Grille
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.