Sur cette page
Un exemple concret
Avec la racine 50, un fils gauche 30 et un fils droit 70, chercher 65 demande deux comparaisons : 65 > 50, on va à droite ; 65 < 70, on va à gauche, où le sous-arbre est vide. On conclut que 65 est absent sans avoir regardé 30.
Le piège à éviter
Il ne suffit pas que chaque nœud soit plus grand que son fils gauche et plus petit que son fils droit. La condition porte sur tout le sous-arbre : un petit-fils mal placé suffit à casser la propriété.
Pour aller plus loin
Un arbre binaire est composé de nœuds ; chacun possède au plus deux fils, gauche et droit. Le vocabulaire à maîtriser comprend la racine, les feuilles, la taille (nombre de nœuds) et la hauteur (longueur du plus long chemin de la racine à une feuille, selon la convention choisie par le sujet). L'ABR ajoute une contrainte d'ordre sur les clés, ce qui le rend utile pour stocker des données qu'on veut retrouver vite.
La recherche est naturellement récursive : si l'arbre est vide, la clé est absente ; si la clé est égale à celle de la racine, on l'a trouvée ; sinon, on relance la recherche à gauche ou à droite. L'insertion suit le même chemin et place la nouvelle clé dans une feuille. Le coût dépend de la hauteur h : il est proportionnel à h. Pour un arbre équilibré de n nœuds, h est de l'ordre de log2(n), soit environ 20 comparaisons pour un million de clés.
Le danger vient de l'ordre d'insertion. Si l'on insère des clés déjà triées, par exemple 1, 2, 3, 4, 5, chaque nouvelle clé se place à droite de la précédente : l'arbre devient un « peigne » de hauteur n et la recherche redevient linéaire, comme dans une liste. Au bac, les exercices portent souvent sur la construction d'un ABR à partir d'une suite de clés, l'écriture de la fonction de recherche ou d'insertion, et le calcul de la taille et de la hauteur.
Ne pas confondre
- Arbre binaire : Tout arbre binaire n'est pas un ABR : l'ABR impose en plus un ordre entre les clés des sous-arbres gauche et droit.
- Recherche dichotomique : La dichotomie travaille sur un tableau trié. L'ABR applique une idée voisine sur une structure chaînée, qui accepte aussi des insertions.
- Tas : Dans un tas, chaque nœud est seulement comparé à ses fils, pas aux sous-arbres entiers ; il sert à trouver vite le minimum ou le maximum.
Dans ta copie
Un arbre binaire de recherche est un arbre binaire dans lequel, pour chaque nœud, les clés du sous-arbre gauche sont inférieures à la clé du nœud et celles du sous-arbre droit lui sont supérieures. Cette organisation permet de chercher une clé en éliminant à chaque étape un sous-arbre entier. Le coût d'une recherche dépend donc de la hauteur de l'arbre : il est logarithmique si l'arbre est équilibré, mais linéaire s'il est dégénéré, par exemple après l'insertion de clés déjà triées.
À retenir
- Dans un ABR, gauche contient les clés plus petites et droite les clés plus grandes.
- Rechercher ou insérer coûte un temps proportionnel à la hauteur.
- Un ABR équilibré a une hauteur de l'ordre de log2(n).
- Le parcours infixe d'un ABR donne les clés triées.
Teste-toi
NSI · question corrigée
Quel parcours d'un arbre binaire de recherche affiche ses clés dans l'ordre croissant ?
Voir la réponse
Réponse A. Le parcours infixe visite le sous-arbre gauche, puis le nœud, puis le sous-arbre droit : il donne les clés triées.
NSI · question corrigée
On insère successivement 10, 20, 30, 40 dans un ABR vide. Quelle forme obtient-on ?
Voir la réponse
Réponse D. Chaque clé est plus grande que la précédente, donc elle se place toujours à droite : l'arbre est dégénéré.
Questions fréquentes
Que faire si deux clés sont égales ?
Le programme suppose en général des clés distinctes. Sinon, il faut fixer une convention, par exemple placer les doublons à gauche, et la respecter partout.
Pourquoi utiliser la récursivité pour les arbres ?
Un arbre est une structure récursive : chaque sous-arbre est lui-même un arbre. Les fonctions de taille, de hauteur ou de recherche s'écrivent donc très naturellement en se rappelant sur les sous-arbres.
Notions liées
Pour réviser tout le chapitre, va sur la page NSI, ou retrouve toutes les définitions dans le lexique du bac. Dans l'application, les quiz reprennent ces notions sur le programme de ta série.