Problem 2
Transféré par
choraichianassProblem 2
Transféré par
choraichianassUniversité Hassan 1er CI–ISIBD–S5
École Nationale des Sciences Appliquées 2025–2026
Département Génie Informatique & Mathématiques POO–JAVA
Problème
Arbre binaire de recherche
On appelle arbre binaire de recherche (Abr) sur un ensemble ordonné, un arbre binaire vérifiant
pour chaque noeud :
clé du fils gauche (si ∃) < clé du noeud < clé du fils droit (si ∃)
Exemple : Abr sur des entiers :
Pour insérer un nouvel élément dans un Abr, on parcoure l’arbre depuis la racine, en se dirigeant
◦ vers la gauche si x < clé du noeud courant,
◦ vers la droite si x > clé du noeud courant ;
et x est inséré à la première position libre ainsi atteinte. (Si x est déjà dans l’arbre l’opération
est sans effet).
Une implémentation des Abr peut être donnée sous la forme :
public class Abr {
public class Noeud {
Comparable cle;
Noeud fg, fd;
...
}
Noeud racine;
...
}
1
I) - 1) Compléter l’implémentation en définissant les méthodes permettant :
• d’ajouter un nouvel élément
• de tester si un élément figure dans l’arbre
- 2) Redéfinir les méthodes :
• toString() permettant d’obtenir les clés de l’arbre sous forme ordonnée
• clone()
II) On appelle rotation sur un noeud f de clé x, l’opération de transformation schématisée
par :
1) Vérifier qu’une rotation (Droite ou Gauche) conserve la propriété de l’arbre binaire
de recherche.
2) Définir dans Abr la méthode :
public Noeud versRacine(Comparable x)
qui place x, par une successions de rotations, à la racine de l’arbre
(si x existe déjà on le déplace vers la racine, sinon on l’ajoute à l’arbre puis on le
déplace vers la racine)