DATENSTRUKTUR TESTEN | EINFÜGEN UND SUCHEN - TECHCODEVIEW.COM

Der Versuchen Sie es mit der Datenstruktur ist eine baumartige Datenstruktur, die zum Speichern eines dynamischen Satzes von Zeichenfolgen verwendet wird. Es wird häufig für effiziente Zwecke verwendet Abruf Und Lagerung von Schlüsseln in einem großen Datensatz. Die Struktur unterstützt Vorgänge wie Einfügen , suchen , Und Streichung von Schlüsseln, was es zu einem wertvollen Werkzeug in Bereichen wie Informatik und Informationsbeschaffung macht. In diesem Artikel werden wir es untersuchen Einfügen und Suchen Operation in der Trie-Datenstruktur.

Versuchen Sie es mit der Datenstruktur

Inhaltsverzeichnis

Darstellung des Trie-Knotens
Darstellung des Trie-Knotens:
A Versuchen Sie es mit der Datenstruktur besteht aus Knoten, die durch Kanten verbunden sind. Jeder Knoten repräsentiert ein Zeichen oder einen Teil einer Zeichenfolge. Der Wurzelknoten, der Ausgangspunkt des Trie, stellt eine leere Zeichenfolge dar. Jede von einem Knoten ausgehende Kante bedeutet ein bestimmtes Zeichen. Der Pfad von der Wurzel zu einem Knoten stellt das Präfix einer im Trie gespeicherten Zeichenfolge dar.

Eine einfache Struktur zur Darstellung von Knoten des englischen Alphabets kann wie folgt aussehen.

Madhuri sagte, komm schon
C++struct TrieNode { // pointer array for child nodes of each node TrieNode* childNode[26]; // Used for indicating ending of string bool wordEnd; TrieNode() { // constructor // initialize the wordEnd variable with false // initialize every index of childNode array with // NULL wordEnd = false; for (int i = 0; i < 26; i++) { childNode[i] = NULL; } } };>Javapublic class TrieNode { // Array for child nodes of each node TrieNode[] childNode; // Used for indicating the end of a string boolean wordEnd; // Constructor public TrieNode() { // Initialize the wordEnd variable with false wordEnd = false; // Initialize every index of the childNode array with null childNode = new TrieNode[26]; for (int i = 0; i < 26; i++) { childNode[i] = null; } } }>
Lassen Sie uns den Prozess des Einfügens der Wörter in eine Trie-Datenstruktur durchgehen. Wir haben bereits die Grundlagen von Trie und seiner Knotenstruktur behandelt.
Pyspark

Hier ist eine visuelle Darstellung des Einfügens der Wörter Und Und An in eine Trie-Datenstruktur:
Operation in Trie-Datenstruktur einfügen

Einfügen von und in die Trie-Datenstruktur:
Tests und Testarten
- Beginnen Sie am Wurzelknoten: Dem Wurzelknoten ist kein Zeichen zugeordnet wordEnd Wert ist 0 , was darauf hinweist, dass an dieser Stelle kein vollständiges Wort endet.
- Erstes Zeichen a: Berechnen Sie den Index mit „ a‘ – ‚a‘ = 0 . Überprüfen Sie, ob die childNode[0] Ist Null . Da dies der Fall ist, erstellen Sie einen neuen TrieNode mit dem Charakter A , wordEnd einstellen 0 und ein leeres Array von Zeigern. Wechseln Sie zu diesem neuen Knoten.
- Zweites Zeichen n: Berechnen Sie den Index mit „n“ – „a“ = 13 . Überprüfen Sie, ob childNode[13] Ist Null . Ja, also erstellen Sie einen neuen TrieNode mit dem Charakter N , wordEnd einstellen 0 und ein leeres Array von Zeigern. Wechseln Sie zu diesem neuen Knoten.
- Drittes Zeichen d: Berechnen Sie den Index mit „ d‘ – ‚a‘ = 3 . Überprüfen Sie, ob childNode[3 ] Ist Null . Ja, also erstellen Sie einen neuen TrieNode mit dem Charakter D , wordEnd einstellen 1 (zeigt das Wort an Und endet hier).
Einfügen einer Ameise in die Trie-Datenstruktur:
- Beginnen Sie am Wurzelknoten: Der Wurzelknoten enthält keine Daten, aber er verfolgt jedes erste Zeichen jeder eingefügten Zeichenfolge.
- Erstes Zeichen a: Berechnen Sie den Index mit „ a‘ – ‚a‘ = 0 . Überprüfen Sie, ob die childNode[0] Ist Null . Das haben wir schon A Knoten, der aus der vorherigen Einfügung erstellt wurde. Bewegen Sie sich also zum Bestehenden A Knoten.
- Erstes Zeichen n: Berechnen Sie den Index mit „ n‘ – ‚a‘ = 13 . Überprüfen Sie, ob childNode [13] ist Null . Das ist nicht der Fall, also gehen Sie zum Bestehenden über N Knoten.
- Zweites Zeichen t: Berechnen Sie den Index mit „t“ – „a“ = 19 . Überprüfen Sie, ob childNode [19] ist Null . Ja, also erstellen Sie einen neuen TrieNode mit dem Charakter T , wordEnd einstellen 1 (was darauf hinweist, dass das Wort Ameise hier endet).
Unten ist die Implementierung des Einfügens von Zeichenfolgen in die Trie-Datenstruktur:
C++#include using namespace std; struct TrieNode { // pointer array for child nodes of each node TrieNode* childNode[26]; // Used for indicating ending of string bool wordEnd; TrieNode() { // constructor // initialize the wordEnd variable with false // initialize every index of childNode array with // NULL wordEnd = false; for (int i = 0; i < 26; i++) { childNode[i] = NULL; } } }; void insert_key(TrieNode* root, string& key) { // Initialize the currentNode pointer // with the root node TrieNode* currentNode = root; // Iterate across the length of the string for (auto c : key) { // Check if the node exist for the current // character in the Trie. if (currentNode->childNode[c - 'a'] == NULL) { // Wenn der Knoten für das aktuelle Zeichen nicht existiert // dann einen neuen Knoten erstellen TrieNode* newNode = new TrieNode(); // Behalten Sie die Referenz für den neu erstellten // Knoten bei. currentNode->childNode[c - 'a'] = newNode; } // Verschieben Sie nun den aktuellen Knotenzeiger auf den neu // erstellten Knoten. currentNode = currentNode->childNode[c - 'a']; } // Erhöhe den WordEndCount für den letzten // CurrentNode-Zeiger. Dies impliziert, dass es eine Zeichenfolge gibt, die bei // currentNode endet. currentNode->wordEnd = 1; }>
Zeitkomplexität: O(Anzahl der Wörter * maxLengthOfWord)
Hilfsraum: O(Anzahl der Wörter * maxLengthOfWord)
Die Suche nach einem Schlüssel in der Trie-Datenstruktur ähnelt der Einfügeoperation. Allerdings nur vergleicht die Zeichen und bewegt sich nach unten . Die Suche kann aufgrund des Endes einer Zeichenfolge oder des Fehlens eines Schlüssels im Versuch abgebrochen werden.

Schrittweiser Ansatz für die Suche in der Trie-Datenstruktur:
- Beginnen Sie am Wurzelknoten. Dies ist der Ausgangspunkt für alle Suchen innerhalb des Trie.
- Durchqueren Sie den Trie basierend auf den Zeichen des gesuchten Wortes. Folgen Sie für jedes Zeichen dem entsprechenden Zweig im Trie. Wenn der Zweig nicht existiert, ist das Wort im Trie nicht vorhanden.
- Wenn Sie das Ende des Wortes erreichen und das WordEnd-Flag auf 1 gesetzt ist, wurde das Wort gefunden.
- Wenn Sie das Ende des Wortes erreichen und das WordEnd-Flag 0 ist, ist das Wort nicht im Trie vorhanden, obwohl es ein Präfix mit einem vorhandenen Wort teilt.
Hier ist eine visuelle Darstellung der Wortsuche Papa in der Trie-Datenstruktur:
Nehmen wir an, dass wir die Wörter erfolgreich eingefügt haben Und , An , Und Papa in unser Trie, und wir müssen nach bestimmten Wörtern innerhalb der Trie-Datenstruktur suchen. Versuchen wir, nach dem Wort zu suchen Papa :
Wie viele Nullen hat eine Milliarde?

Suchvorgang in der Trie-Datenstruktur
- Wir beginnen am Wurzelknoten.
- Wir folgen dem Zweig, der dem Zeichen „d“ entspricht.
- Wir folgen dem Zweig, der dem Zeichen a‘ entspricht.
- Wir folgen dem Zweig, der dem Zeichen „d“ entspricht.
- Wir erreichen das Ende des Wortes und wordEnd Flagge ist 1 . Das bedeutet, dass Papa ist im Trie vorhanden.
Nachfolgend finden Sie die Implementierung von Suchzeichenfolgen in der Trie-Datenstruktur:
C++#include using namespace std; struct TrieNode { // pointer array for child nodes of each node TrieNode* childNode[26]; // Used for indicating ending of string bool wordEnd; TrieNode() { // constructor // initialize the wordEnd variable with false // initialize every index of childNode array with // NULL wordEnd = false; for (int i = 0; i < 26; i++) { childNode[i] = NULL; } } }; bool search_key(TrieNode* root, string& key) { // Initialize the currentNode pointer // with the root node TrieNode* currentNode = root; // Iterate across the length of the string for (auto c : key) { // Check if the node exist for the current // character in the Trie. if (currentNode->childNode[c - 'a'] == NULL) { // Angegebenes Wort existiert nicht in Trie return false; } // Verschiebe den currentNode-Zeiger auf den bereits // vorhandenen Knoten für das aktuelle Zeichen. currentNode = currentNode->childNode[c - 'a']; } return (currentNode->wordEnd == true); }>
Zeitkomplexität: O(Anzahl der Wörter * maxLengthOfWord)
Hilfsraum: O(Anzahl der Wörter * maxLengthOfWord)
Ganzzahl in String-Java umwandeln
Erstellen Sie mit Hilfe von einen Wurzelknoten TrieNode() Konstrukteur.
Speichern Sie eine Sammlung von Zeichenfolgen, die in den Trie eingefügt werden müssen, in einem Vektor von Zeichenfolgen, sagen wir: arr .
Einfügen aller Zeichenfolgen in Trie mit Hilfe der insert_key() Funktion,
Durchsuchen Sie Zeichenfolgen mit Hilfe von search_key() Funktion.

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

C++

 #include  using namespace std; struct TrieNode {  // pointer array for child nodes of each node  TrieNode* childNode[26];  // Used for indicating ending of string  bool wordEnd;  TrieNode()  {  // constructor  // initialize the wordEnd variable with false  // initialize every index of childNode array with  // NULL  wordEnd = false;  for (int i = 0; i < 26; i++) {  childNode[i] = NULL;  }  } }; void insert_key(TrieNode* root, string& key) {  // Initialize the currentNode pointer  // with the root node  TrieNode* currentNode = root;  // Iterate across the length of the string  for (auto c : key) {  // Check if the node exist for the current  // character in the Trie.  if (currentNode->childNode[c - 'a'] == NULL) { // Wenn der Knoten für das aktuelle Zeichen nicht existiert // dann einen neuen Knoten erstellen TrieNode* newNode = new TrieNode();  // Behalten Sie die Referenz für den neu erstellten // Knoten bei.  currentNode->childNode[c - 'a'] = newNode;  } // Verschieben Sie nun den aktuellen Knotenzeiger auf den neu // erstellten Knoten.  currentNode = currentNode->childNode[c - 'a'];  } // Erhöhe den WordEndCount für den letzten // CurrentNode-Zeiger. Dies impliziert, dass es eine Zeichenfolge gibt, die bei // currentNode endet.  currentNode->wordEnd = 1; } bool search_key(TrieNode* root, string& key) { // Initialisiere den currentNode-Zeiger // mit dem Wurzelknoten TrieNode* currentNode = root;  // Iteriere über die Länge der Zeichenfolge for (auto c : key) { // Überprüfe, ob der Knoten für das aktuelle // Zeichen im Trie vorhanden ist.  if (currentNode->childNode[c - 'a'] == NULL) { // Das gegebene Wort existiert nicht in Trie return false;  } // Verschiebe den currentNode-Zeiger auf den bereits // vorhandenen Knoten für das aktuelle Zeichen.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); } // Treibercode int main() { // Einen Wurzelknoten für den Trie erstellen TrieNode* root = new TrieNode();  // Speichert die Zeichenfolgen, die wir in den // Trie-Vektor einfügen möchteninputStrings = { 'and', 'ant', 'do', 'geek', 'dad', 'ball' };  // Anzahl der Einfügeoperationen im Trie int n = inputStrings.size();  für (int i = 0; i< n; i++) {  insert_key(root, inputStrings[i]);  }  // Stores the strings that we want to search in the Trie  vectorsearchQueryStrings = { 'do', 'geek', 'bat' };  // Anzahl der Suchvorgänge im Trie int searchQueries = searchQueryStrings.size();  für (int i = 0; i< searchQueries; i++) {  cout << 'Query String: ' << searchQueryStrings[i]  << '
';  if (search_key(root, searchQueryStrings[i])) {  // the queryString is present in the Trie  cout << 'The query string is present in the '  'Trie
';  }  else {  // the queryString is not present in the Trie  cout << 'The query string is not present in '  'the Trie
';  }  }  return 0; }>

Java

 class TrieNode {  TrieNode[] childNode;  boolean wordEnd;  TrieNode()  {  childNode = new TrieNode[26];  wordEnd = false;  } } class Trie {  TrieNode root;  Trie() { root = new TrieNode(); }  // Function to insert a key into the Trie  void insert(String key)  {  TrieNode currentNode = root;  for (int i = 0; i < key.length(); i++) {  int index = key.charAt(i) - 'a';  if (currentNode.childNode[index] == null) {  currentNode.childNode[index]  = new TrieNode();  }  currentNode = currentNode.childNode[index];  }  currentNode.wordEnd = true;  }  // Function to search for a key in the Trie  boolean search(String key)  {  TrieNode currentNode = root;  for (int i = 0; i < key.length(); i++) {  int index = key.charAt(i) - 'a';  if (currentNode.childNode[index] == null) {  return false;  }  currentNode = currentNode.childNode[index];  }  return currentNode.wordEnd;  } } public class Main {  public static void main(String[] args)  {  Trie trie = new Trie();  String[] inputStrings  = { 'and', 'ant', 'do', 'geek', 'dad', 'ball' };  // Insert each string into the Trie  for (String str : inputStrings) {  trie.insert(str);  }  String[] searchQueryStrings  = { 'do', 'geek', 'bat' };  // Search for each string and print whether it is  // found in the Trie  for (String query : searchQueryStrings) {  System.out.println('Query String: ' + query);  if (trie.search(query)) {  System.out.println(  'The query string is present in the Trie');  }  else {  System.out.println(  'The query string is not present in the Trie');  }  }  } }>

Python

 class TrieNode: def __init__(self): self.childNode = [None] * 26 self.wordEnd = False class Trie: def __init__(self): self.root = TrieNode() # Function to insert a key into the Trie def insert(self, key): currentNode = self.root for char in key: index = ord(char) - ord('a') if not currentNode.childNode[index]: currentNode.childNode[index] = TrieNode() currentNode = currentNode.childNode[index] currentNode.wordEnd = True # Function to search for a key in the Trie def search(self, key): currentNode = self.root for char in key: index = ord(char) - ord('a') if not currentNode.childNode[index]: return False currentNode = currentNode.childNode[index] return currentNode.wordEnd if __name__ == '__main__': trie = Trie() inputStrings = ['and', 'ant', 'do', 'geek', 'dad', 'ball'] # Insert each string into the Trie for word in inputStrings: trie.insert(word) searchQueryStrings = ['do', 'geek', 'bat'] # Search for each string and print whether it is found in the Trie for query in searchQueryStrings: print('Query String:', query) if trie.search(query): print('The query string is present in the Trie') else: print('The query string is not present in the Trie')>

JavaScript

 class TrieNode {  constructor() {  // Initialize the childNode array with 26 nulls  this.childNode = Array(26).fill(null);  // Initialize wordEnd to the false indicating that no word ends here yet  this.wordEnd = false;  } } class Trie {  constructor() {  // Initialize the root node of the Trie  this.root = new TrieNode();  }  // Function to insert a key into the Trie  insert(key) {  // Start from the root node  let currentNode = this.root;  for (let i = 0; i < key.length; i++) {  const index = key.charCodeAt(i) - 'a'.charCodeAt(0);  if (currentNode.childNode[index] === null) {  currentNode.childNode[index] = new TrieNode();  }  // Move to the next node in the Trie  currentNode = currentNode.childNode[index];  }  // Mark the end of the word  currentNode.wordEnd = true;  }  // Function to search for a key in the Trie  search(key) {  // Start from the root node  let currentNode = this.root;  // Iterate through each character in the key  for (let i = 0; i < key.length; i++) {  const index = key.charCodeAt(i) - 'a'.charCodeAt(0);  if (currentNode.childNode[index] === null) {  return false;  }  // Move to the next node in the Trie  currentNode = currentNode.childNode[index];  }  // Return true if the end of the word is marked otherwise false  return currentNode.wordEnd;  } } // Driver code const trie = new Trie(); const inputStrings = ['and', 'ant', 'do', 'geek', 'dad', 'ball']; // Insert each string into the Trie inputStrings.forEach((str) =>trie.insert(str)); const searchQueryStrings = ['do', 'geek', 'bat']; // Nach jeder Zeichenfolge suchen und ausgeben, ob sie im Trie gefunden wird searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('Die Abfragezeichenfolge ist im Trie vorhanden'); else { console.log('Die Abfragezeichenfolge ist im Trie nicht vorhanden' });>

Ausgabe

Query String: do The query string is present in the Trie Query String: geek The query string is present in the Trie Query String: bat The query string is not present in the Trie>

Versuchen Sie es mit Löschen
Inhalte von Trie werden angezeigt
Autovervollständigungsfunktion mit Trie
Mustersuche mithilfe eines Versuchs aller Suffixe
Übungsprobleme:

Minimaler Wortumbruch
Eindeutige Zeilen in einer binären Matrix
Anzahl unterschiedlicher Teilzeichenfolgen
Wort-Boggle
Sortieren eines Arrays von Zeichenfolgen (oder Wörtern) mithilfe von Trie

TechCodeview

Datenstruktur testen | Einfügen und Suchen

Erstellen Sie mit Hilfe von einen Wurzelknoten TrieNode() Konstrukteur.