Arbres binaires
Les arbres binaires sont une structure de données fondamentale pour représenter des relations hiérarchiques et organiser efficacement l’information. Cette fiche récapitule les notions de base, les parcours classiques et le cas important
Notions de base
Vocabulaire essentiel
Un arbre binaire organise des nœuds, chacun ayant au plus deux enfants.
- nœud : valeur stockée avec liens éventuels vers des enfants.
- racine : nœud sans parent.
Repères rapides
- Un nœud interne a au moins un enfant.
- Sous-arbre gauche et sous-arbre droit structurent l’arbre.
Schéma mental
Parcours
Ordres de visite
Préfixe
- racine
- gauche
- droite
Infixe et suffixe
- Infixe : gauche, racine, droite.
- Suffixe : gauche, droite, racine.
- Chaque nœud est visité une seule fois.
Mémo
Préfixe d’abord, infixe au milieu, suffixe à la fin. Le tri naturel apparaît surtout avec l’infixe.
Exemples de lecture
- Le parcours qui visite la racine en premier est le _________.
- Le parcours qui place la racine entre gauche et droite est l’_________.
Arbre de recherche
Propriété d’ordre
Dans un arbre binaire de recherche, les valeurs suivent l’ordre gauche < racine < droite.
- La propriété vaut pour chaque sous-arbre.
- Le parcours infixe donne des clés triées.
Comparaison utile
| Structure | Idée clé | Effet |
|---|---|---|
| Arbre binaire | Au plus deux enfants | Structure générale |
| ABR | Ordre gauche-racine-droite | Recherche ordonnée |
| Arbre équilibré | Forme régulière | Recherche plus rapide |
Mini-défi
On cherche 7 dans un ABR où chaque comparaison suit gauche < racine < droite. On suppose l’arbre correctement ordonné.
- On compare 7 à la racine.
- On descend à gauche ou à droite selon le résultat.
La recherche réussit si 7 est rencontré, sinon l’élément est absent.
Complexité
Coût et hauteur
La recherche, l’insertion et la suppression dépendent de la hauteur h de l’arbre.
Deux cas à retenir
Arbre équilibré
- hauteur proche de log n
- opérations rapides
Arbre dégénéré
- hauteur proche de n
- pire cas linéaire
Piège classique
Un ABR n’est pas toujours logarithmique. Sa performance dépend de sa forme.
Révision express
Vocabulaire
- nœud
- Élément de l’arbre portant une valeur.
- racine
- Nœud sans parent.
- feuille
- Nœud sans enfant.
Bilan
- Un arbre binaire a des nœuds, une racine et des feuilles.
- Le préfixe, l’infixe et le suffixe donnent trois lectures utiles.
- Un arbre de recherche ordonne les clés et accélère la recherche.
- La complexité dépend surtout de la hauteur de l’arbre.