Trier la structure des données en Java

L'article suivant fournit un aperçu de la structure de données Trie en Java. Fondamentalement, la structure des données joue un rôle très important dans la programmation informatique et nous devons également savoir quand et pourquoi nous utilisons différents types de structure de données dans la programmation informatique. Normalement, le trie est une structure de données discrète, et ce n'est pas familier, ou nous pouvons dire que ce n'est pas une structure de données largement utilisée mais utilisée dans l'algorithme typique, un trie est également connu sous le nom d'arbre numérique ; il a aussi un autre nom qui est base ou préfixe.

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

En utilisant une structure de données trie, nous recherchons l'élément par préfixes dans un arbre bien structuré avec une clé, et il est avantageux de stocker les chaînes. De plus, nous pouvons effectuer différentes opérations sur la structure des données telles que l'insertion, la suppression et la recherche.

Syntaxe de la structure de données Trie en Java

Vous trouverez ci-dessous la syntaxe mentionnée :

public void insert_node(specified string of word){
TrieNode present = rootNode;
For (char i: word.toCharArray()){
Present = present.getChildren().computeIfAbsent(I, c->new TrieNode());
}
Present.setEndOfWord(true)
}

Explication :

En utilisant la syntaxe ci-dessus, nous essayons d'insérer des éléments dans la structure de données trie ; pour cela, nous devons suivre les étapes suivantes :

• Tout d'abord, nous devons définir le nœud actuel comme nœud racine pour l'opération d'insertion.
• Après cela, nous devons définir le caractère présent comme premier caractère du mot.
• Si un nœud présent existe dans l'arbre numérique, alors référence au caractère présent, et si un nœud présent n'existe pas, nous devons créer le nouveau nœud.
• Enfin, nous pouvons utiliser la clé Trie pour le parcours numérique.

De même, nous pouvons écrire une syntaxe pour les opérations de suppression et de recherche.

Comment fonctionne la structure de données Trie en Java ?

Ce qui suit montre comment fonctionne la structure de données trie en Java :

Normalement, nous pouvons effectuer 3 opérations différentes dans une structure de données trie comme suit :

1. Insérer une opération d'élément

Nous expliquons déjà comment fonctionne l'opération d'insertion en java sur le point ci-dessus. La complexité de l'opération d'insertion est O (n), où n représente la taille de la clé.

2. Recherche d'opération d'élément

Après l'opération d'insertion, nous pouvons effectuer l'opération de recherche ou de recherche sur la structure de données trie en utilisant l'algorithme suivant comme suit.

Code :

public void find_node(specified string of word){
TrieNode present = rootNode;
For (char j = 0; j < word.length(); j++){
char c = word.charAt(j);
TrieNode node = present.getChildren().get(c);
If (node = = null){
return false;
}
Present = node;
}
return present.isEndOfWord();
}

Explication :

Suivez maintenant les étapes suivantes pour l'élément de recherche dans une structure de données trie comme suit :

• Tout d'abord, récupérez le nœud enfant à partir de la racine.
• Après, nous devons parcourir chaque caractère de la chaîne.
• Vérifiez maintenant si ce caractère spécifié est présent, ou nous pouvons dire qu'il fait partie du sous-trie ; si le caractère spécifié ne fait pas partie du sub trie, renvoyez false et quittez.
• Répétez les deuxième et troisième étapes jusqu'à ce qu'il n'y ait plus de caractère présent dans la chaîne.
• La complexité de l'opération d'insertion est O (n), où n représente la taille de la clé.

3. Supprimer l'opération d'élément

En plus de l'opération d'insertion et trouver l'élément ; évidemment, nous devrions également avoir la possibilité de supprimer l'opération, nous devons donc suivre les étapes suivantes comme suit.

• Vérifiez si l'élément spécifié fait désormais partie du trie.
• Dans le cas où l'élément est trouvé, éliminez-le du trie.
• La complexité de ce calcul est O(n), où n correspond à la longueur de la clé.

Exemple de structure de données Trie en Java

Vous trouverez ci-dessous un exemple de structure de données Trie en Java :

Code :

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// created class to store node into the trie data structure
class trie_data
{
// Define the size of alphabet size
private static final int CHAR_AlPHA_SIZE = 26;
private boolean isLeaf;
private List<trie_data> child = null;
// Created Constructor of class
trie_data()
{
isLeaf = false;
child = new ArrayList<>(Collections.nCopies(CHAR_AlPHA_SIZE, null));
}
// function for insertion operation
public void trie_insert(String id)
{
System.out.println("We inserted new element into the data structure \"" + id + "\"");
// Staritng from the parent node that is root node
trie_data present = this;
for (char ch: id.toCharArray())
{
// if node is not exist then create new node in trie
if (present.child.get(ch - 'a') == null) {
present.child.set(ch - 'a', new trie_data());
}
// visit next node
present = present.child.get(ch - 'a');
}
// mark present as leaf node
present.isLeaf = true;
}
// search function to search element into trie data structure
// if key value is not present then it return the false
public boolean trie_search(String id)
{
System.out.print("We searched element\"" + id + "\" : ");
trie_data present = this;
for (char ch: id.toCharArray())
{
// visit next node
present = present.child.get(ch - 'a');
if (present == null) {
return false;
}
}
return present.isLeaf;
}
}
class Main
{
public static void main (String[] args)
{
// construct a new Trie node
trie_data head = new trie_data();
head.trie_insert("the");
head.trie_insert("they");
head.trie_insert("final");
System.out.println(head.trie_search("the")); // true
System.out.println(head.trie_search("they")); // true
System.out.println(head.trie_search("final")); // true
System.out.println(head.trie_search("Sample")); // false
head.trie_insert("Sample");
System.out.println(head.trie_search("the")); // true
System.out.println(head.trie_search("they")); // true
System.out.println(head.trie_search("final")); // true
System.out.println(head.trie_search("Sample")); // true
}
}

Explication :

• Dans l'exemple ci-dessus, nous essayons d'implémenter la structure de données trie en Java, ici nous avons d'abord créé une classe pour stocker le nœud dans la structure de données trie. Ensuite, nous avons défini la taille de l'alphabet en utilisant CHAR_AlPHA_SIZE. Ensuite, nous avons créé un constructeur pour la classe.
• Il existe une fonction pour l'opération d'insertion 'trie_insert' () ainsi que pour rechercher des éléments de la structure de données trie comme indiqué dans le programme ci-dessus. À la fin du programme, nous appelons simplement la fonction d'insertion et de recherche avec différentes valeurs que nous devons insérer et rechercher dans la structure de données trie.

Sortie :

Conclusion

Dans l'article ci-dessus, nous avons vu la syntaxe de base de la structure de données Trie, et nous avons également vu différents exemples de structure de données Trie. À partir de cet article, nous avons vu comment et quand utiliser la structure de données Trie en Java.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!