Overview
Les structures de données représentent un atout crucial dans la programmation informatique, et savoir quand et pourquoi les utiliser est très important.
Cet article est une brève introduction à la structure de données trie (prononcé « try »), son implémentation et son analyse de complexité.
Trie
Une trie est une structure de données discrète qui n’est pas tout à fait connue ou largement mentionnée dans les cours d’algorithme typiques, mais néanmoins une structure importante.
Une trie (également connue sous le nom d’arbre numérique) et parfois même d’arbre radix ou d’arbre préfixe (car ils peuvent être recherchés par des préfixes), est une structure d’arbre ordonnée, qui tire profit des clés qu’elle stocke – généralement des chaînes de caractères.
La position d’un nœud dans l’arbre définit la clé à laquelle ce nœud est associé, ce qui rend les essais différents par rapport aux arbres de recherche binaires, dans lesquels un nœud stocke une clé qui correspond uniquement à ce nœud.
Tous les descendants d’un nœud ont un préfixe commun d’une Chaîne associée à ce nœud, alors que la racine est associée à une Chaîne vide.
Voici un aperçu de TrieNode que nous utiliserons dans notre implémentation du Trie:
public class TrieNode { private HashMap<Character, TrieNode> children; private String content; private boolean isWord; // ...}Il peut y avoir des cas où un trie est un arbre de recherche binaire, mais en général, ceux-ci sont différents. Les arbres de recherche binaire et les tries sont tous deux des arbres, mais chaque nœud des arbres de recherche binaire a toujours deux enfants, alors que les nœuds des tries, par contre, peuvent en avoir plus.
Dans une trie, chaque nœud (sauf le nœud racine) stocke un caractère ou un chiffre. En parcourant la trie vers le bas depuis le nœud racine jusqu’à un nœud particulier n, on peut former un préfixe commun de caractères ou de chiffres qui est partagé par d’autres branches de la trie également.
En parcourant la trie vers le haut depuis un nœud feuille jusqu’au nœud racine, on peut former une Chaîne ou une séquence de chiffres.
Voici la classe Trie, qui représente une implémentation de la structure de données trie:
public class Trie { private TrieNode root; //...}Opérations courantes
Maintenant, voyons comment implémenter les opérations de base.
3.1. Insertion d’éléments
La première opération que nous allons décrire est l’insertion de nouveaux nœuds.
Avant de commencer l’implémentation, il est important de comprendre l’algorithme :
- Définir un nœud actuel comme nœud racine
- Définir la lettre actuelle comme la première lettre du mot
- Si le nœud actuel a déjà une référence existante à la lettre actuelle (à travers un des éléments du champ « children »), alors définir le nœud actuel à ce nœud référencé. Sinon, créer un nouveau nœud, définir la lettre égale à la lettre actuelle, et également initialiser le nœud actuel à ce nouveau nœud
- Répéter l’étape 3 jusqu’à ce que la clé soit traversée
La complexité de cette opération est O(n), où n représente la taille de la clé.
Voici l’implémentation de cet algorithme:
public void insert(String word) { TrieNode current = root; for (char l: word.toCharArray()) { current = current.getChildren().computeIfAbsent(l, c -> new TrieNode()); } current.setEndOfWord(true);}Voyons maintenant comment nous pouvons utiliser cette méthode pour insérer de nouveaux éléments dans un trie:
private Trie createExampleTrie() { Trie trie = new Trie(); trie.insert("Programming"); trie.insert("is"); trie.insert("a"); trie.insert("way"); trie.insert("of"); trie.insert("life"); return trie;}Nous pouvons tester que le trie a déjà été peuplé de nouveaux nœuds à partir du test suivant:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}3.2. Trouver des éléments
Ajoutons maintenant une méthode pour vérifier si un élément particulier est déjà présent dans un trie:
- Retrouver les enfants de la racine
- Itérer sur chaque caractère de la chaîne
- Vérifier si ce caractère fait déjà partie d’un sous-trie. S’il n’est présent nulle part dans le trie, alors arrêtez la recherche et renvoyez false
- Répétez la deuxième et la troisième étape jusqu’à ce qu’il n’y ait plus aucun caractère dans la Chaîne. Si la fin de la Chaîne est atteinte, retournez true
La complexité de cet algorithme est O(n), où n représente la longueur de la clé.
L’implémentation Java peut ressembler à :
public boolean find(String word) { TrieNode current = root; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } current = node; } return current.isEndOfWord();}Et en action :
@Testpublic void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life"));}3.3. Suppression d’un élément
A part l’insertion et la recherche d’un élément, il est évident que nous devons aussi pouvoir supprimer des éléments.
Pour le processus de suppression, nous devons suivre les étapes suivantes :
- Vérifier si cet élément fait déjà partie de la trie
- Si l’élément est trouvé, alors le supprimer de la trie
La complexité de cet algorithme est O(n), où n représente la longueur de la clé.
Regardons rapidement l’implémentation:
public void delete(String word) { delete(root, word, 0);}private boolean delete(TrieNode current, String word, int index) { if (index == word.length()) { if (!current.isEndOfWord()) { return false; } current.setEndOfWord(false); return current.getChildren().isEmpty(); } char ch = word.charAt(index); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord(); if (shouldDeleteCurrentNode) { current.getChildren().remove(ch); return current.getChildren().isEmpty(); } return false;}Et en action:
@Testvoid whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming"));}Conclusion
Dans cet article, nous avons vu une brève introduction à la structure de données trie et ses opérations les plus courantes et leur implémentation.