TP - Binary Search Tree

Une première tentative pour représenter un nœud en Rust est

1. Essayez de compiler le type suivant avec Rust. Expliquez l’erreur obtenue.

Dans l’erreur retournée, le compilateur nous suggère d’introduire une indirection. Les champs left et right vont contenir des références indirectes vers d’autres nœuds.

Parce que nous souhaitons allouer l’ABR sur le tas, nous allons utiliser une référence Box<> en introduisant un type Box<Node>.

Ce nouveau code compile ! Malheureusement il ne nous permet pas de représenter des arbres vides. Cela est indispensable, en effet les feuilles de l’arbre possèdent des sous-arbre gauche et droit vides.

Dans un langage comme C ou C++, nous pourrions utiliser un pointeur nul pour représenter le cas de l’arbre vide. Néanmoins dans Rust les références nulles sont interdites pour éviter des erreurs à l’exécution. À la place Rust préconise l’utilisation d’un type Option<> qui représente une valeur optionelle.

Notre structure devient donc

et de manière à permettre de manipuler un arbre vide directement, nous allons la réecrire de la manière suivante,

Les macros [derive(Debug)] permettent d’obtenir des routines d’affichage pour le debug automatiquement. En les utilisants il est possible d’afficher un objet arbre avec la syntaxe println!("{:?}", mon_arbre).

Pour représenter un arbre composé d’un unique nœud racine avec la valeur 12 nous écririons,

2. Modifiez l’exemple précédent pour rajouter un fils gauche (8) et un fils droit (27). Vérifiez que l’arbre s’affiche correctement.

Comme nous venons de le voir, il est pour l’instant fastidieux de manipuler nos structures. Pour faciliter l’utilisation nous allons rajouter quelques constructeurs.

1. Implémentez le constructeur pub fn new() → Self pour la structure Tree, cette méthode retournera un arbre vide.

2. Implémentez le constructeur pub fn leaf(value: i32) → Self qui retournera un nœud de valeur value sans enfants.

3. Rajoutez des tests pour ces deux méthodes.

Pour tester si une valeur appartient à l’ABR il suffit de parcourir l’arbre en partant de la racine. Pour chaque nœud l’on compare la valeur cherchée à la valeur courante. Si elle sont identiques alors nous retournons true. Si ce n’est pas le cas nous recursivons soit sur l’arbre gauche lorsque la valeur est inférieure ou l’arbre droit lorsque la valeur est supérieure.

1. Implémentez dans Tree la méthode pub fn contains(&self, value: i32) → bool qui retourne vrai si et seulement si value est présente dans un des nœuds de l’arbre.

Pour rajouter une nouvelle valeur à l’ABR on utilise une méthode similaire. Nous parcourons l’arbre: - si la racine est vide, nous le remplaçons par une feuille avec la nouvelle valeur; - si la racine est pleine, nous vérifions que la valeur n’est pas déjà présente (en effet il n’y a pas de doublons dans un ABR) puis nous recursivons sur le sous-arbre gauche ou le sous-arbre droit de manière à préserver l’invariant d’ordre.

2. Implémentez la méthode pub fn insert(&mut self, value: i32) → bool qui insère value dans l’ABR. La méthode retourne true lorsque l’insertion est possible et false lorsque la valeur est déjà présente dans l’arbre.

3. Rajoutez des tests unitaires pour les méthodes contains et insert.

La supression d’une valeur est un peu plus compliquée. Une méthode de supression efficace est expliquée sur l’article français de Wikipedia.

1. Implémentez la méthode pub fn delete(&mut self, value: i32) en suivant l’algorithme précédent. La méthode retourne true lorsque la supression est possible et retourne false lorsque la valeur n’est pas trouvée dans l’ABR.

1. Pour l’instant notre ABR utilise des entiers signés 32 bits (i32); néanmoins il est facile en utilisant un type générique de l’étendre à tout type possédant un ordre total. Pour spécifier que votre type générique possède un ordre total vous pouvez utiliser le trait Ord.

2. Plutôt que de retourner un booleen pour vérifier que les opérations insert et delete se sont bien déroulées il est aussi possible de retourner une erreur à l’aide d’un objet de type Result<>. Cela vous permettra d’explorer un autre mécanisme de gestion d’erreurs dans Rust.

Crédits