Versuchen Sie es mit der Datenstruktur in Java

Der folgende Artikel bietet einen Überblick über die Trie-Datenstruktur in Java. Grundsätzlich spielt die Datenstruktur eine sehr wichtige Rolle in der Computerprogrammierung und wir müssen auch wissen, wann und warum wir unterschiedliche Arten von Datenstrukturen in der Computerprogrammierung verwenden. Normalerweise ist Trie eine diskrete Datenstruktur, und das ist nicht bekannt, oder wir können sagen, dass es sich nicht um eine weit verbreitete Datenstruktur handelt, aber diese wird im typischen Algorithmus verwendet, ein Trie wird auch als digitaler Baum bezeichnet; Es gibt auch einen anderen Namen, der Radix oder Präfix ist.

Starten Sie Ihren kostenlosen Softwareentwicklungskurs

Webentwicklung, Programmiersprachen, Softwaretests und andere

Mithilfe einer Trie-Datenstruktur suchen wir das Element nach Präfixen in einem gut strukturierten Baum mit einem Schlüssel, und es ist vorteilhaft, die Zeichenfolgen zu speichern. Darüber hinaus können wir verschiedene Operationen in der Datenstruktur durchführen, z. B. Einfügen, Löschen und Suchen.

Syntax der Trie-Datenstruktur in Java

Nachstehend finden Sie die erwähnte Syntax:

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)
}

Erklärung:

Mithilfe der obigen Syntax versuchen wir, Elemente in die Trie-Datenstruktur einzufügen; Dazu müssen wir die folgenden Schritte wie folgt ausführen:

• Zuerst müssen wir den aktuellen Knoten als Wurzelknoten für den Einfügevorgang festlegen.
• Danach müssen wir das aktuelle Zeichen als erstes Zeichen des Wortes festlegen.
• Wenn ein aktueller Knoten im digitalen Baum vorhanden ist, dann ein Verweis auf das aktuelle Zeichen, und wenn kein aktueller Knoten vorhanden ist, müssen wir den neuen Knoten erstellen.
• Endlich können wir die Trie-Taste zum digitalen Verfahren verwenden.

Ähnlich können wir Syntax für Lösch- und Suchvorgänge schreiben.

Wie funktioniert die Trie-Datenstruktur in Java?

Das Folgende zeigt, wie die Trie-Datenstruktur in Java funktioniert:

Normalerweise können wir drei verschiedene Operationen in einer Trie-Datenstruktur wie folgt ausführen:

1. Vorgang „Element einfügen“

Wir haben bereits im obigen Punkt erklärt, wie der Einfügevorgang in Java funktioniert. Die Komplexität der Einfügungsoperation beträgt O (n), wobei n die Größe des Schlüssels darstellt.

2. Elementoperation finden

Nach dem Einfügevorgang können wir den Such- oder Suchvorgang für die Trie-Datenstruktur durchführen, indem wir den folgenden Algorithmus wie folgt verwenden.

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();
}

Erklärung:

Befolgen Sie nun die folgenden Schritte für das Suchelement in einer Trie-Datenstruktur wie folgt:

• Zuerst holen Sie sich den untergeordneten Knoten von der Wurzel.
• Danach müssen wir jedes einzelne Zeichen in der Zeichenfolge iterieren.
• Überprüfen Sie nun, ob das angegebene Zeichen vorhanden ist, oder wir können sagen, dass es Teil des Subtrie ist; Wenn das angegebene Zeichen nicht Teil des Unterversuchs ist, geben Sie „false“ zurück und beenden Sie den Vorgang.
• Wiederholen Sie den zweiten und dritten Schritt, bis kein Zeichen mehr in der Zeichenfolge vorhanden ist.
• Die Komplexität des Einfügevorgangs beträgt O (n), wobei n die Größe des Schlüssels darstellt.

3. Vorgang „Element löschen“

Neben dem Einfügevorgang und der Suche nach dem Element; Natürlich sollten wir auch die Möglichkeit haben, den Vorgang zu löschen, daher müssen wir die folgenden Schritte wie folgt ausführen.

• Überprüfen Sie, ob das angegebene Element ab sofort Teil des Versuchs ist.
• Falls das Element gefunden wird, entfernen Sie es aus dem Versuch.
• Die Komplexität dieser Berechnung liegt in O(n), wobei n die Länge des Schlüssels angibt.

Beispiel einer Trie-Datenstruktur in Java

Im Folgenden finden Sie ein Beispiel einer Trie-Datenstruktur in 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
}
}

Erklärung:

• Im obigen Beispiel versuchen wir, die Trie-Datenstruktur in Java zu implementieren. Hier haben wir zunächst eine Klasse erstellt, um den Knoten in der Trie-Datenstruktur zu speichern. Dann haben wir die Alphabetgröße mithilfe von CHAR_AlPHA_SIZE definiert. Dann haben wir einen Konstruktor für die Klasse erstellt.
• Es gibt eine Funktion für die Einfügeoperation „trie_insert“ () sowie für die Suche nach Elementen aus der Trie-Datenstruktur, wie im obigen Programm gezeigt. Am Ende des Programms rufen wir einfach die Einfüge- und Suchfunktion mit verschiedenen Werten auf, die wir einfügen und in der Trie-Datenstruktur suchen müssen.

Ausgabe:

Fazit

Aus dem obigen Artikel haben wir die grundlegende Syntax der Trie-Datenstruktur gesehen und auch verschiedene Beispiele der Trie-Datenstruktur gesehen. In diesem Artikel haben wir gesehen, wie und wann wir die Trie-Datenstruktur in Java verwenden.

Das obige ist der detaillierte Inhalt vonVersuchen Sie es mit der Datenstruktur in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!