PROFDINFO.COM

Votre enseignant d'informatique en ligne

Un dictionnaire dans un arbre

Qu'ont en commun un dictionnaire et un arbre? Les deux, bien entendu, ont des feuilles en grande quantité.

(Voici une solution possible au problème, ainsi qu'un programme de correction.)

Un arbre devant un soleil couchantL'arbre comme structure de données

Un arbre est une structure de données construite avec des noeuds. Chaque noeud contient une information et peut avoir des enfants (peut pointer vers d'autres noeuds). Le premier noeud de l'arbre est nommé la racine. Un noeud qui n'a pas d'enfants est appelé une feuille. La hauteur d'une feuille est le nombre de noeuds à traverser pour atteindre la feuille en partant de la racine. La hauteur de l'arbre correspond à la hauteur de la feuille la plus élevée.

Un arbre binaire est un arbre dont les noeuds peuvent avoir au plus deux enfants, généralement appelés l'enfant de gauche et l'enfant de droite.Un arbre binaire

Un arbre binaire de recherche (souvent appelé BST pour binary search tree) est un arbre binaire dont les noeuds sont ordonnés de façon à accélérer la recherche d'informations à l'intérieur. Tout noeud d'unarbre binaire de recherche aura une valeur plus grande que celle de son enfant de gauche et plus petite que celle de son enfant de droite. L'égalité est un cas particulier qui peut être réglé de trois façons: l'interdire, décider que l'enfant de gauche sera plus petit ou égal à son parent, ou décider que l'enfant de droite sera plus grand ou égal à son parent. Choisir la première façon ou non dépend du design de l'application. Choisir entre la deuxième ou la troisième façon est totalement arbitraire.

Cette structure de données est fort efficace et une recherche dans un arbre binaire de recherche prendra un temps moyen de l'ordre du logarithme du nombre de noeuds (on dira que l'opération est O(log n) dans ce cas). Remarquez qu'il s'agit ici du temps moyen, puisque le pire temps est plutôt O(n), dans le cas où l'arbre est complètement déséquilibré (et devient finalement une liste chaînée).

Un arbre binaire de recherche équilibré est un arbre binaire de recherche pour lequel la règle suivante est respectée: la différence de hauteur entre deux feuilles quelconques n'est jamais plus que 1. Autrement dit, il est impossible de trouver deux feuilles qui ont une différence de hauteur de 2 ou plus. On s'assure ainsi dans ce cas que le pire cas de recherche sera O(log n), comme le temps moyen. Évidemment, les insertions et les suppressions dans un tel arbre seront plus complexes et plus longues.

L'arbre comme structure de données est utilisé couramment. Il est très efficace lorsque l'on veut stocker une grande quantité de données de façon ordonnée de sorte à minimiser les temps de recherche, par exemple un dictionnaire.

Les arbres et la récursivité

Il est possible de créer des arbres sans utiliser la récursivité, mais ça devient alors extrêmement complexe à gérer. Il est beaucoup plus simple de se servir de la récursivité lorsque l'on veut parcourir un arbre. Par exemple, pour afficher le contenu d'un arbre trié à l'écran, la procédure est simple:

Afficher(Noeud)
{
	Afficher(Noeud.Gauche)
	Ecrire(Noeud.Valeur)
	Afficher(Noeud.Droite)
}

Faire l'équivalent sans récursivité serait long et ardu alors qu'ici c'est tout simple! (Évidemment, pour vous faire paraître le tout encore plus simple, j'ai omis de m'assurer que les enfants Gauche et Droite existaient vraiment avant de leur demander de s'afficher - mais bon, ça ne rend pas le tout beaucoup plus compliqué).

Le même principe peut être appliqué à l'insertion: quand j'insère un nouveau noeud, je l'insère à la racine. Si la racine n'existe pas, le nouveau noeud devient la racine. Si elle existe, je compare les valeurs et j'insère le nouveau noeud à gauche ou à droite selon le résultat de la comparaison. Je rappelle donc la même procédure pour l'insertion, qui sera rappelée jusqu'à ce qu'un endroit vide au bout de l'arbre soit trouvé pour y loger le nouveau noeud.

Supprimer un noeud

Si le parcours d'un arbre binaire est trivial et l'insertion est simple, c'est dans la suppression que se trouve la difficulté. En effet, on ne peut pas simplement éliminer un noeud au beau milieu d'un arbre sans détruire du coup ses enfants et toute sa descendance. Si on veut supprimer un noeud au milieu de l'arbre, on devra lui trouver un remplaçant, un autre noeud plus bas dans l'arbre qui pourra prendre sa place afin de conserver la structure. Ce remplaçant adoptera les enfants du noeud à supprimer et l'arbre pourra continuer de vivre sans perdre de branches.

Le tout est de choisir le bon remplaçant. En effet, dans le cas d'un arbre trié, on ne peut pas commencer à changer des noeuds de place sans mettre en péril nos recherches futures. Comment trouver le bon remplaçant? Deux façons:

Si le noeud à effacer a deux enfants, on peut choisir la méthode qu'on veut entre les deux premières. Il est toutefois recommandé de ne pas toujours prendre la même afin d'éviter de déséquilibrer l'arbre.

Garder un arbre équilibré

Il existe plusieurs façons de garder un arbre équilibré. Une des plus efficaces consiste à vérifier l'indice d'équilibrage d'un noeud après l'insertion ou la suppression, puis de faire des rotations de noeuds pour corriger les déséquilibres. De cette façon, l'insertion et la suppression sont plus lentes, mais le pire cas de recherche est égal au cas moyen, ce qui augmente grandement l'efficacité.

Votre travail

Vous devrez produire une classe Arbre qui permettra de créer un arbre binaire de recherche pour un dictionnaire. On pourra donc insérer des mots avec leur définition dans l'arbre, faire des recherches, supprimer des mots et afficher le contenu complet du dictionnaire.

Votre classe Arbre devra contenir une classe Noeud (donc la classe Noeud devra être imbriquée dans la classe Arbre). Pensez à protéger vos classes correctement - ne déclarez public que ce qui doit être public. Le reste sera privé et accessible par des propriétés (et pas nécessairement toujours en lecture et écriture!).

Un Noeud devrait contenir au minimum:

Un Arbre devrait contenir au minimum:

Respectez scrupuleusement ces spécifications (orthographe (et casse) des noms, ordre et types des paramètres, type de la valeur de retour, imbrication de classes) puisque je testerai votre classe avec mon propre programme et que tout ce qui ne fonctionnera pas ne méritera pas de points, peu importe la raison. Je ne modifierai pas votre code ni le mien pendant la correction.

Testez à fond votre classe et pensez à tous les cas d'exceptions possibles, car votre professeur lui y pensera certainement.

L'équilibrage: un bonus pour les Kings et Queens

Pour mériter un 10% de bonus, vous pouvez faire en sorte que votre arbre soit toujours équilibré. Vous devrez pour cela trouver un algorithme puis l'implémenter dans votre classe Arbre. Il est permis de modifier la classe Noeud pour y ajouter des trucs nécessaires afin de vous simplifier la vie.

En plus de votre code, vous devrez me remettre une description claire de l'algorithme que vous avez choisi d'utiliser. Ne vous gênez pas pour chercher sur Internet afin de trouver des pistes de solution.

Un exemple de Main

Voici un exemple d'utilisation de la classe Arbre. Vous pouvez l'utiliser pour tester votre classe, mais n'allez surtout par croire que tous les cas de tests y sont présents. Cela vous permet au moins de vérifier que votre classe respecte les spécifications.

Arbre monArbre = new Arbre();

monArbre.Inserer("milieu", "Être au centre");
monArbre.Inserer("gauche", "Côté opposé à la droite");
monArbre.Inserer("droite", "Côté opposé à la gauche");
monArbre.Inserer("zèbre", "Cheval en pyjama");
monArbre.Inserer("québécois", "Habitant du Québec");
monArbre.Inserer("abeille", "Insecte butineur");
monArbre.Inserer("futile", "La résistance l'est");
monArbre.Inserer("hache", "Arme de Nain");
monArbre.Inserer("epsilon", "E-grec");
monArbre.Afficher();
Console.ReadLine();

Console.WriteLine("EPSILON:  " + monArbre.Trouver("epsilon"));
monArbre.Supprimer("québécois");
Console.WriteLine();
monArbre.Afficher();
Console.ReadLine();

monArbre.Supprimer("gauche");
Console.WriteLine();
monArbre.Afficher();
Console.ReadLine();

La remise

Comme ce travail est plus compliqué que ce qu'on a fait jusqu'à présent, vous aurez deux semaines pour y travailler. Vous devrez donc remettre par courriel à votre charmant professeur un fichier .cs contenant votre classe Arbre (et donc votre classe Noeud), sans Main. On oublie les copier/coller de texte. Pour avoir le bonus, n'oubliez pas de décrire clairement votre algorithme d'équilibrage dans votre courriel. Si vous êtes rapide et que vous avez terminé en une semaine, vous aurez vraiment l'air paresseux si vous ne tentez pas d'aller chercher le bonus. Votre courriel doit me parvenir au plus tard vendredi le 28 septembre à 13h30. La période de laboratoire du 21 septembre sera également consacrée à ce travail.

Et maintenant: ingénieurs forestiers, à vos claviers!