Développement 3.2
Arbres binaires de recherche
Lorsque l'on imagine une structure de données, il arrive fréquemment que les éléments appartiennent à un ensemble ordonné. En d'autres termes, les éléments de la structure peuvent être comparés entre eux. Dans ce cas, une problématique inévitable est le tri : comment présenter tous les éléments stockés par ordre croissant ?
Pour un tableau, la solution est le plus souvent de faire coïncider l'ordre dans le tableau et l'ordre naturel des éléments : cela devient un tableau trié. Malheureusement, il est coûteux en performances de maintenir cette propriété lors d'ajouts et de suppressions.
Pour un arbre, il y a un peu plus de marge de manœuvre, puisque les éléments ne sont pas organisés linéairement. On dit qu'il s'agit d'un arbre binaire de recherche s'il est binaire (aucun de ses nœuds n'a plus de deux enfants, nommés fils gauche et fils droit) et si l'étiquette de tout nœud est supérieure à celles de son sous-arbre gauche et inférieure à celles de son sous-arbre droit.
Remarque Pour une collection donnée d'éléments, il y a plusieurs formes d'arbres possibles qui satisfassent à la définition ci-dessus. Nous verrons que certaines formes (dites équilibrées) sont préférables à d'autres...
-
Tri. Écrivez une application qui prend sur la ligne de commande une liste de réels, et affiche ces réels à la console dans l'ordre croissant.
Pour cela, vous devrez utiliser un arbre binaire de recherche capable de recevoir un à un tous les réels, et dont la redéfinition de la méthode toString parcourt les nœuds dans l'ordre croissant de leurs étiquettes.
-
Authentification. Nous souhaitons écrire une simulation d'un serveur d'authentification qui supporte trois opérations :
- ajout d'un utilisateur (en donnant son identifiant et son mot de passe)
- suppression d'un utilisateur (en donnant son identifiant)
- authentification d'un utilisateur (en proposant un identifiant et un mot de passe)
Un dictionnaire est nécessaire pour mémoriser ces informations. Utilisez une classe de l'API Java dans un premier temps, et lorsque vous serez satisfait de votre application, remplacez le dictionnaire par une classe de votre invention basée sur un arbre binaire de recherche.
bob@box:~$ java Authentification > add bob p@ssword Utilisateur "bob" ajouté > auth bob password Utilisateur "bob" non reconnu > auth bob p@ssword Utilisateur "bob" reconnu > del bob Utilisateur "bob" retiré > auth bob p@ssword Utilisateur "bob" non reconnu > quit Au revoir
-
Rotation. Dans l'exercice précédent, le temps nécessaire pour authentifier un utilisateur dépend de la profondeur où se trouve son nœud. Comme chaque nouvel utilisateur est placé dans une feuille, il a donc les plus mauvaises performances possibles. Comme il y a plus de chances qu'un utilisateur ancien soit inactif et donc inutile, on préférerait donner la priorité aux utilisateurs récents en les insérant le plus haut possible : directement à la racine.
Pour cela on va avoir recours à une manipulation de l'arbre nommée rotation :
Vous pouvez constater que les deux versions contiennent les mêmes éléments, et satisfont toutes deux à la définition des arbres binaires de recherche. On ne perd donc rien en passant de l'une à l'autre.
Modifiez la méthode d'insertion dans l'arbre de l'exercice précédent pour que le nœud inséré en tant que feuille soit ensuite remonté par rotations successives jusqu'à la racine.