Arbres

Un arbre convient quand une donnée contient des sous-parties, qui contiennent elles-mêmes des sous-parties. Il exprime une hiérarchie, là où une liste exprime surtout une suite.

Pensez à un système de fichiers, un menu, des catégories de produits ou des commentaires imbriqués. Chaque élément peut porter une valeur et mener vers plusieurs éléments placés en dessous. Il n'existe pas forcément d'index utile pour atteindre « le troisième élément » : le chemin dans la hiérarchie donne le sens.

Le vocabulaire décrit une position ou une relation. Comptez toujours des arêtes, pas des nœuds, pour la profondeur et la hauteur.

Dans un arbre général, chaque nœud possède une liste d'enfants. Cette liste peut être vide ou contenir autant d'éléments que le domaine le demande.

1. Le cas local est simple

   Affichez la valeur du nœud courant. Une opération sur un arbre commence souvent par ce petit travail local.

2. Chaque enfant pose le même problème

   Demandez ensuite à chaque enfant de s'afficher avec une indentation supplémentaire. Le sous-arbre a exactement la même forme que l'arbre entier.

3. La liste vide arrête naturellement

   Une feuille n'a aucun enfant. La boucle ne lance donc aucun nouvel appel et la descente s'arrête.

Chaque enfant est la racine d'un sous-arbre. Chercher dans l'arbre revient donc à chercher de la même façon dans chacun de ces arbres plus petits. Cette répétition du même problème est la récursivité.

1. Arrêtez une branche vide

   Si le nœud vaut null, il n'y a plus rien à chercher, compter ou additionner. C'est le cas de base.

2. Traitez le nœud courant

   Comparez sa valeur, comptez-la ou utilisez-la dans le résultat. Chaque appel ne s'occupe que de ce travail local.

3. Confiez les enfants à la même méthode

   Appelez la méthode sur chaque enfant. Ces appels appliquent exactement les mêmes trois étapes à des sous-arbres plus petits.

4. Combinez les réponses

   Une recherche s'arrête au premier enfant qui répond true. Un comptage ou une somme ajoute le résultat de chaque enfant.

Exemple 1 : chercher une valeur partout

Le nœud courant répond d'abord. Sinon, la même recherche part dans le sous-arbre de chaque enfant. Dès qu'une branche trouve la valeur, la méthode retourne true sans examiner les enfants restants.

Exemple 2 : compter les valeurs impaires

Chaque appel compte zéro ou un pour son propre nœud, puis ajoute le compte de chacun de ses enfants. Une branche vide contribue zéro.

Exemple 3 : additionner toutes les valeurs

Seule l'opération locale change. La structure récursive reste la même : cas de base, valeur du nœud courant, appel sur chaque enfant, combinaison des résultats.

Un arbre binaire remplace la liste d'enfants par deux références nommées : left et right. Chaque nœud a donc zéro, un ou deux enfants. C'est une contrainte de forme, rien de plus.

La boucle sur les enfants montrée plus haut devient ici deux liens nommés. Une recherche générale appelle la même méthode sur left puis right. Sans invariant d'ordre, aucun des deux côtés ne peut être éliminé.

Un arbre binaire de recherche est un arbre binaire auquel on ajoute une règle d'ordre : toutes les clés du sous-arbre gauche sont plus petites, toutes celles du sous-arbre droit sont plus grandes, et cette règle reste vraie dans chaque sous-arbre.

Cherchons 30 dans le BST précédent. La comparaison avec le nœud courant suffit à choisir le prochain lien. Avec des chaînes, compareTo donne cette décision : résultat négatif vers la gauche, positif vers la droite, zéro quand la clé est trouvée.

1. Comparez 30 à 40

   30 est plus petit. Descendez uniquement dans le sous-arbre gauche. Le sous-arbre droit de 40 ne peut pas contenir 30 si l'invariant est respecté.

2. Comparez 30 à 20

   30 est plus grand. Descendez uniquement à droite de 20.

3. Comparez 30 à 30

   Les valeurs sont égales. La recherche se termine après trois comparaisons.

L'invariant dit où chercher, mais la forme détermine combien de nœuds vous devrez comparer. L'ordre d'insertion peut produire deux arbres valides très différents.

Écrivez maintenant la méthode qui manque. Votre code doit exploiter l'invariant : après chaque comparaison, un seul appel récursif est nécessaire.

Vous corrigez le travail d'un étudiant qui prépare une remédiation Java 17. Évaluez d'abord son raisonnement, ses invariants et la cohérence de son brouillon. Un code incomplet mais bien expliqué mérite un retour utile. Signalez précisément les erreurs sans inventer d'exigences hors sujet.

La leçon porte sur l'invariant d'un arbre binaire de recherche. Vérifiez surtout le cas de base, le sens de compareTo, le fait qu'un seul sous-arbre est exploré et la cohérence de la trace. N'exigez aucune autre technique d'arbre.

Travail demandé:
Complétez contains(Node node, String target).

Votre méthode doit :
- retourner false quand le nœud est null ;
- utiliser target.compareTo(node.key) une seule fois par appel ;
- retourner true quand la comparaison vaut zéro ;
- descendre à gauche ou à droite, jamais des deux côtés ;
- expliquer en une phrase pourquoi cette direction est sûre.

Ajoutez ensuite une trace pour la recherche de "Lina" dans cet arbre : Mona à la racine, Hugo à gauche, Sara à droite, Lina à droite de Hugo.

Commencez par poser au plus deux questions si une intention reste ambiguë. Donnez ensuite les points corrects, les problèmes précis et la plus petite prochaine étape. Ne fournissez une solution complète que si l'étudiant la demande explicitement.

Réponse de l'étudiant:
[aucune réponse collée]

La table de hachage et le BST offrent tous deux un accès par clé, mais leur organisation et leurs cas défavorables diffèrent. Pour consolider le mécanisme qui revient dans presque toutes les opérations sur un arbre, poursuivez avec la leçon sur la récursivité.