Recherche dans un ABR
Algorithmique classique
Enonce
Rechercher une valeur x dans un arbre binaire de recherche (ABR). Retourner True si présente.
Signature attendue
def recherche_abr(arbre: dict, x: int) -> bool:Exemple
recherche_abr(None, 1)→False
📖 Rappel de cours
On compare à la racine : si la valeur est plus petite on descend à gauche, plus grande à droite. La structure évite d'explorer l'autre moitié.
⚠ Le piège : Le coût est O(h) où h est la hauteur — soit O(log n) si l'arbre est équilibré, mais O(n) s'il dégénère en peigne.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Arbre Binaire — Hauteur
- Parcours Infixe (In-order)
- Nombre de Noeuds d'un Arbre
- Arbre Binaire Miroir
- Matrice d'Adjacence → Liste d'Adjacence
- Parcours en Profondeur (DFS)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.