Versuchen Sie die Datenstruktur in Java

  2. How-To's
  3. Java-Howtos
  4. Versuchen Sie die Datenstruktur in Java
Sheeraz Gul 15 Februar 2024
Java Java Data Structure
  1. Versuchen Sie die Datenstruktur in Java
  2. Grundoperationen der Trie-Datenstruktur
  3. Java-Implementierung der Trie-Datenstruktur
Versuchen Sie die Datenstruktur in Java

Dieses Tutorial demonstriert die Trie-Datenstruktur in Java.

Versuchen Sie die Datenstruktur in Java

Das Wort Trie wird aus dem Wort Retrieval extrahiert, bei dem es sich um eine sortierte Datenstruktur handelt, die zum Speichern des Satzes von Zeichenfolgen verwendet wird. Trie kann als Datenstruktur definiert werden, bei der die Anzahl der Zeiger gleich der Anzahl der Zeichen in jedem Knoten ist.

Mit Hilfe des Präfixes des Wortes kann die Trie-Datenstruktur verwendet werden, um ein Wort aus einem Wörterbuch zu suchen. Wenn in diesem Szenario alle Wörter im Wörterbuch aus den 26 englischen Alphabeten bestehen, hat jeder Trie-Knoten 26 Punkte.

Die Trie-Datenstruktur ist auch als Präfixbaum oder digitaler Baum bekannt, wobei die Position des Knotens den Schlüssel bestimmt, mit dem der Knoten verbunden wird. Versuchen wir anhand der folgenden Abbildung zu verstehen, wie ein Trie funktioniert:

Trie Data Structure Java

Das obige Bild enthält die Baumstruktur für die Wörter deal, delft und delete.

Eigenschaften der Trie-Datenstruktur

Hier sind die Haupteigenschaften für den Trie-Satz von Saiten:

  1. Der Root-Knoten ist immer der Null-Knoten.
  2. Jeder untergeordnete Knoten wird alphabetisch sortiert.
  3. Aufgrund des englischen Alphabets kann jeder Knoten nicht mehr als 26 Kinder haben.
  4. Jeder Knoten kann einen Buchstaben aus dem Alphabet speichern.

Anwendung der Trie-Datenstruktur

Sehen wir uns einige Hauptanwendungen für die Trie-Datenstruktur an:

  1. Der Trie kann verwendet werden, wenn angenommen werden muss, dass alle Buchstaben Kleinbuchstaben sind.
  2. Wenn wir nur die Buchstaben von a-z verwenden müssen, ohne Bindestrich, ohne Satzzeichen usw.
  3. Wenn die Wörter eine begrenzte Länge haben. Wenn wir beispielsweise an einem 2x2-Board arbeiten, darf die Wortlänge nicht mehr als 4 betragen, sodass diese Wörter verworfen werden können.
  4. Viele Wörter im Wörterbuch haben denselben Wortstamm, zum Beispiel Rasen und Rasenmäher. Der Trie kann für diese gebeugten Wörter verwendet werden.

Grundoperationen der Trie-Datenstruktur

Der Trie hat drei grundlegende Operationen:

Vorgang einfügen

Die erste Operation besteht darin, einen Knoten in den Trie einzufügen. Dazu müssen wir die folgenden Punkte verstehen:

  1. Jeder Buchstabe des eingegebenen Wortes wird einzeln in einen Trie-Knoten eingefügt.
  2. Die Zeichenlänge bestimmt die Länge des Trie.
  3. Das Schlüsselzeichen-Array dient als Kinderindex.
  4. Wenn der aktuelle Knoten einen Verweis auf den aktuellen Buchstaben hat, legen Sie den aktuellen Knoten fest, der auf den Knoten verwiesen hat. Andernfalls sollte ein neuer Knoten erstellt werden.

Suchvorgang

Die zweite grundlegende Operation für Trie ist das Suchen eines Knotens. Auch dieser Vorgang ähnelt dem Einfügen.

Wir müssen nur einen Knoten mit dem gleichen Ansatz suchen.

Vorgang löschen

Die dritte Operation besteht darin, einen Knoten zu löschen. Auch dies ist eine einfache Bedienung.

Wir müssen zwei Punkte berücksichtigen, bevor wir mit dem Löschen beginnen:

  1. Wenn der Knotenschlüssel während der Suche nicht gefunden wird, wird der Löschvorgang angehalten und beendet.
  2. Wenn der Knotenschlüssel beim Durchsuchen des Trie gefunden wird, löscht die Löschoperation den Schlüssel.

Java-Implementierung der Trie-Datenstruktur

Lassen Sie uns versuchen, die Trie-Datenstruktur zu implementieren, die nur kleine englische a-z-Zeichen unterstützt. Siehe Beispiel:

package delftstack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Trie_Node {
  // 26 characters for a – z
  private static final int CHARACTER_SIZE = 26;

  private boolean Is_Leaf;
  private List<Trie_Node> Trie_Children = null;

  // Constructor
  Trie_Node() {
    Is_Leaf = false;
    Trie_Children = new ArrayList<>(Collections.nCopies(CHARACTER_SIZE, null));
  }

  // function for insertion
  public void Insertion(String Node_Key) {
    System.out.println("Inserting the key \"" + Node_Key + "\"");

    // root node
    Trie_Node root_node = this;

    // repeat for every character of the key
    for (char character : Node_Key.toCharArray()) {
      // create a new Trie node if the path does not exist
      if (root_node.Trie_Children.get(character - 'a') == null) {
        root_node.Trie_Children.set(character - 'a', new Trie_Node());
      }

      // going to the next node
      root_node = root_node.Trie_Children.get(character - 'a');
    }

    // current node as a leaf
    root_node.Is_Leaf = true;
  }

  // Method for search
  public boolean Searching(String Node_Key) {
    System.out.print("Searching the key \"" + Node_Key + "\" : ");

    Trie_Node Current_Node = this;

    // repeat for the character of the key
    for (char character : Node_Key.toCharArray()) {
      // going to the next node
      Current_Node = Current_Node.Trie_Children.get(character - 'a');

      // reach out to the end of a path in the Trie if the string is invalid
      if (Current_Node == null) {
        return false;
      }
    }
    return Current_Node.Is_Leaf;
  }
}

public class Example {
  public static void main(String[] args) {
    // construct a new Trie node
    Trie_Node New_Trie = new Trie_Node();

    New_Trie.Insertion("delft");
    New_Trie.Insertion("delf");
    New_Trie.Insertion("del");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // false

    New_Trie.Insertion("delftstack");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // true
  }
}

Der obige Code implementiert die Einfüge- und Suchoperation der Trie-Datenstruktur. Siehe die Ausgabe:

Inserting the key "delft"
Inserting the key "delf"
Inserting the key "del"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : false
Inserting the key "delftstack"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : true

Nun ist die Raumkomplexität für die Trie-Datenstruktur O(N × M × C), wobei:

  1. N - die Anzahl der Saiten
  2. M - die maximale Länge der Saiten.
  3. C - die Größe des Alphabets

Das Speicherproblem kann also in Java mit der oben genannten Speicherplatzkomplexität auftreten.

Wir können auch die HashMap von Java verwenden, um Trie zu implementieren, um das Speicherproblem zu lösen. Versuchen wir den Trie mittels HashMap zu implementieren:

package delftstack;

import java.util.HashMap;
import java.util.Map;

class Trie_Node {
  private boolean Is_Leaf;
  private Map<Character, Trie_Node> Trie_Children;

  // Constructor
  Trie_Node() {
    Is_Leaf = false;
    Trie_Children = new HashMap<>();
  }

  // Insertion
  public void Insertion(String Node_Key) {
    System.out.println("Inserting the key \"" + Node_Key + "\"");

    // root node
    Trie_Node root_node = this;

    for (char character : Node_Key.toCharArray()) {
      // if the path doesn't exist, create a new node.
      root_node.Trie_Children.putIfAbsent(character, new Trie_Node());

      // going to the next node
      root_node = root_node.Trie_Children.get(character);
    }
    root_node.Is_Leaf = true;
  }
  // Searching
  public boolean Searching(String Node_key) {
    System.out.print("Searching the key \"" + Node_key + "\" : ");

    Trie_Node Current_Node = this;

    // repeat
    for (char character : Node_key.toCharArray()) {
      // going to the next node
      Current_Node = Current_Node.Trie_Children.get(character);

      if (Current_Node == null) {
        return false;
      }
    }

    return Current_Node.Is_Leaf;
  }
}

public class Example {
  public static void main(String[] args) {
    // construct a new Trie node
    Trie_Node New_Trie = new Trie_Node();

    New_Trie.Insertion("delft");
    New_Trie.Insertion("delf");
    New_Trie.Insertion("del");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // false

    New_Trie.Insertion("delftstack");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // true
  }
}

Der Code erledigt die gleiche Arbeit, jedoch auf speichereffizientere Weise. Sehen Sie sich die Ausgabe für Trie in Java an:

Inserting the key "delft"
Inserting the key "delf"
Inserting the key "del"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : false
Inserting the key "delftstack"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : true
Autor: Sheeraz Gul
Sheeraz Gul avatar Sheeraz Gul avatar

Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.

LinkedIn Facebook