La structure de données Trie en Java

1. Vue d'ensemble

Les structures de données représentent un atout crucial dans la programmation informatique, et il est très important de savoir quand et pourquoi les utiliser.

Cet article est une brève introduction à la structure de données trie (prononcé «try»), sa mise en œuvre et son analyse de complexité.

2. Trie

Un trie est une structure de données discrète qui n'est pas tout à fait connue ou largement mentionnée dans les cours d'algorithmes typiques, mais néanmoins importante.

Un trie (également connu sous le nom d'arbre numérique) et parfois même un arbre de base ou un arbre de préfixes (car ils peuvent être recherchés par préfixes), est une structure arborescente ordonnée, qui tire parti des clés qu'elle stocke - généralement des chaînes.

La position d'un nœud dans l'arborescence 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, tandis que la racine est associée à une chaîne vide .

Ici, nous avons un aperçu de TrieNode que nous utiliserons dans notre implémentation du Trie:

public class TrieNode { private HashMap 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, ils sont différents. Les arbres de recherche binaire et les essais sont des arbres, mais chaque nœud dans les arbres de recherche binaire a toujours deux enfants, tandis que les nœuds des essais, en revanche, peuvent en avoir plus.

Dans un trie, chaque nœud (sauf le nœud racine) stocke un caractère ou un chiffre. En parcourant le trie du nœud racine à un nœud n particulier , un préfixe commun de caractères ou de chiffres peut être formé, qui est également partagé par d'autres branches du trie.

En parcourant le trie d'un nœud feuille au nœud racine, une chaîne ou une séquence de chiffres peut être formée.

Voici la classe Trie , qui représente une implémentation de la structure de données trie:

public class Trie { private TrieNode root; //... }

3. Opérations communes

Voyons maintenant 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:

  1. Définir un nœud actuel comme nœud racine
  2. Définir la lettre actuelle comme première lettre du mot
  3. Si le nœud actuel a déjà une référence existante à la lettre actuelle (via l'un des éléments du champ «enfants»), définissez le nœud actuel sur ce nœud référencé. Sinon, créez un nouveau nœud, définissez la lettre égale à la lettre actuelle et initialisez également le nœud actuel sur ce nouveau nœud
  4. Répétez 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é rempli avec de nouveaux nœuds à partir du test suivant:

@Test public void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty()); }

3.2. Recherche d'éléments

Ajoutons maintenant une méthode pour vérifier si un élément particulier est déjà présent dans un trie:

  1. Obtenez des enfants de la racine
  2. Itérer à travers chaque caractère de la chaîne
  3. Vérifiez si ce personnage fait déjà partie d'un sous-trie. S'il n'est présent nulle part dans le trie, arrêtez la recherche et renvoyez false
  4. Répétez la deuxième et la troisième étape jusqu'à ce qu'il ne reste plus de caractère dans la chaîne. Si la fin de la chaîne est atteinte, renvoie 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:

@Test public void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life")); }

3.3. Supprimer un élément

Outre l'insertion et la recherche d'un élément, il est évident que nous devons également pouvoir supprimer des éléments.

Pour le processus de suppression, nous devons suivre les étapes:

  1. Vérifiez si cet élément fait déjà partie du trie
  2. Si l'élément est trouvé, retirez-le du trie

La complexité de cet algorithme est O (n) , où n représente la longueur de la clé.

Jetons un coup d'œil à 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:

@Test void whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming")); }

4. 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.

Le code source complet des exemples présentés dans cet article se trouve à l'adresse over sur GitHub.