Notebook associé — ABR
Ouvrez le cours interactif au format Jupyter (.ipynb) pour exécuter le code pas à pas.
Télécharger le .ipynb
Voir la version HTML
Ouvrez le cours interactif au format Jupyter (.ipynb) pour exécuter le code pas à pas.
1. Définitions
Un arbre binaire de recherche (ABR) est un arbre binaire étiqueté : chaque nœud contient une clé
qui correspond à la valeur (la donnée) associée à ce nœud.
La nouveauté par rapport à un arbre binaire général est que les clés sont comparables et respectent une
propriété d’ordre.
Ainsi, un ABR vérifie :
- toutes les clés du sous-arbre gauche d’un nœud sont strictement inférieures (ou égales) à la clé du nœud ;
- toutes les clés du sous-arbre droit d’un nœud sont strictement supérieures (ou égales) à la clé du nœud.
2. Implantation chaînée (Python)
Dans le notebook, on code un ABR avec une classe Noeud contenant une clé et deux références
vers les sous-arbres gauche et droit. Les méthodes (recherche, insertion, min, max)
traduisent directement les algorithmes ci-dessus.
À retenir
- Un ABR est un arbre binaire ordonné.
- Pour rechercher / insérer, on suit un chemin guidé par des comparaisons.
- Minimum : descendre à gauche. Maximum : descendre à droite.