De Probeer de datastructuur is een boomachtige datastructuur die wordt gebruikt voor het opslaan van een dynamische set strings. Het wordt vaak gebruikt voor efficiënt ophalen En opslag van sleutels in een grote dataset. De structuur ondersteunt operaties zoals plaatsing , zoekopdracht , En verwijdering van sleutels, waardoor het een waardevol hulpmiddel is op gebieden als informatica en het ophalen van informatie. In dit artikel gaan we op onderzoek uit invoegen en zoeken bewerking in Trie Data Structure.

Probeer de datastructuur

Inhoudsopgave

• Vertegenwoordiging van Trie Node
• Vertegenwoordiging van Trie Node:

  A Probeer de datastructuur bestaat uit knooppunten verbonden door randen. Elk knooppunt vertegenwoordigt een teken of een deel van een string. Het hoofdknooppunt, het startpunt van de Trie, vertegenwoordigt een lege string. Elke rand die uit een knooppunt voortkomt, duidt een specifiek karakter aan. Het pad van de root naar een knooppunt vertegenwoordigt het voorvoegsel van een tekenreeks die is opgeslagen in de Trie.

  Een eenvoudige structuur om knooppunten van het Engelse alfabet weer te geven kan als volgt zijn.

  
  
  
  

  Java-datum naar tekenreeks

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

  Java

  public 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;  }  } }>

  Laten we het proces doorlopen van het invoegen van de woorden in een Trie-datastructuur. We hebben de basisprincipes van Trie en zijn knooppuntstructuur al besproken.

  webbrowserinstellingen

  Hier is een visuele weergave van het invoegen van de woorden En En op in een Trie-datastructuur:

  
  

  
  

  
  

  Bewerking invoegen in de gegevensstructuur

  
  

  Invoegen en in Trie-datastructuur:

  uit

  • Begin bij het hoofdknooppunt: Aan het hoofdknooppunt is geen karakter gekoppeld wordEnd waarde is 0 , wat aangeeft dat er op dit punt geen volledig woord eindigt.
  • Eerste teken a: Bereken de index met ‘ een’ – ‘een’ = 0 . Controleer of de kindNode[0] is nul . Omdat dit zo is, maak je een nieuwe TrieNode met het personage A , wordEnd ingesteld op 0 en een lege reeks verwijzingen. Ga naar dit nieuwe knooppunt.
  • Tweede teken n: Bereken de index met behulp van ‘n’ – ‘een’ = 13 . Controleer of kindNode[13] is nul . Dat is zo, dus maak een nieuwe TrieNode met het personage N , wordEnd ingesteld op 0 en een lege reeks verwijzingen. Ga naar dit nieuwe knooppunt.
  • Derde teken d: Bereken de index met ‘ d’ – ‘een’ = 3 . Controleer of kindknooppunt[3 ] is nul . Dat is zo, dus maak een nieuwe TrieNode met het personage D , wordEnd ingesteld op 1 (waarbij het woord wordt aangegeven En eindigt hier).

  Ant invoegen in de Trie-datastructuur:

  • Begin bij het hoofdknooppunt: Het rootknooppunt bevat geen gegevens, maar houdt elk eerste teken bij van elke string die is ingevoegd.
  • Eerste teken a: Bereken de index met ‘ een’ – ‘een’ = 0 . Controleer of de kindNode[0] is nul . Wij hebben al de A knooppunt gemaakt op basis van de vorige invoeging. dus ga naar het bestaande A knooppunt.
  • Eerste teken n: Bereken de index met ‘ n’ – ‘een’ = 13 . Controleer of kindNode [13] is nul . Dat is het niet, dus ga naar het bestaande N knooppunt.
  • Tweede teken t: Bereken de index met behulp van ‘t’ – ‘een’ = 19 . Controleer of kindNode [19] is nul . Dat is zo, dus maak een nieuwe TrieNode met het personage T , wordEnd ingesteld op 1 (wat aangeeft dat het woord mier hier eindigt).

  Hieronder ziet u de implementatie van het invoegen van strings in de Trie-datastructuur:

  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) { // Als het knooppunt voor het huidige teken niet bestaat // maak dan een nieuw knooppunt TrieNode* newNode = new TrieNode();  // Bewaar de referentie voor het nieuw gemaakte // knooppunt.  currentNode->childNode[c - 'a'] = newNode;  } // Verplaats nu de huidige knooppuntaanwijzer naar het nieuw // gemaakte knooppunt.  currentNode = currentNode->childNode[c - 'a'];  } // Verhoog de wordEndCount voor de laatste currentNode // pointer, dit impliceert dat er een string is die eindigt op // currentNode.  currentNode->wordEnd = 1; }>

  Tijdcomplexiteit: O(aantal woorden * maxLengthOfWord)
  Hulpruimte: O(aantal woorden * maxLengthOfWord)

  Het zoeken naar een sleutel in de Trie-datastructuur is vergelijkbaar met de invoegbewerking. Het is echter alleen vergelijkt de karakters en gaat naar beneden . De zoekopdracht kan worden beëindigd vanwege het einde van een tekenreeks of het ontbreken van een sleutel in de tri.

  Stapsgewijze aanpak voor zoeken in de Trie-gegevensstructuur:

  • Begin bij het hoofdknooppunt. Dit is het startpunt voor alle zoekopdrachten binnen de Trie.
  • Doorkruis de Trie op basis van de karakters van het woord waarnaar je zoekt. Volg voor elk personage de overeenkomstige tak in de Trie. Als de tak niet bestaat, is het woord niet aanwezig in de Trie.
  • Als u het einde van het woord bereikt en de vlag wordEnd is ingesteld op 1, is het woord gevonden.
  • Als u het einde van het woord bereikt en de vlag wordEnd is 0, is het woord niet aanwezig in de Trie, ook al deelt het een voorvoegsel met een bestaand woord.

  Hier is een visuele weergave van het zoekwoord pa in Trie-datastructuur:

  Laten we aannemen dat we de woorden met succes hebben ingevoegd En , op , En pa in onze Trie, en we moeten zoeken naar specifieke woorden binnen de Trie-datastructuur. Laten we proberen het woord te zoeken pa :

  
  

  

  Zoekbewerking in de drie gegevensstructuur

  sdlc-levenscyclus

  
  

  • We beginnen bij het rootknooppunt.
  • We volgen de tak die overeenkomt met het teken ‘d’.
  • We volgen de tak die overeenkomt met het teken a’.
  • We volgen de tak die overeenkomt met het teken ‘d’.
  • We bereiken het einde van het woord en wordEnd vlag is 1 . Dit betekent dat pa is aanwezig in de Trie.

  Hieronder vindt u de implementatie van zoekreeksen in Trie Data Structure:

  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) {// Opgegeven woord bestaat niet in Trie return false;  } // Verplaats de currentNode-aanwijzer naar het reeds // bestaande knooppunt voor het huidige teken.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == waar); }>

  Tijdcomplexiteit: O(aantal woorden * maxLengthOfWord)
  Hulpruimte: O(aantal woorden * maxLengthOfWord)

  geheel getal naar tekenreeks Java

  Maak een rootknooppunt met behulp van TrieNode() bouwer.

• Bewaar een verzameling strings die in de tri moeten worden ingevoegd in een vector van strings, bijvoorbeeld: arr .
• Alle strings in Trie invoegen met behulp van de insert_key() functie,
• Zoek strings met behulp van zoeksleutel() functie.

Hieronder vindt u de implementatie van de bovenstaande aanpak:

#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) { // Als het knooppunt voor het huidige teken niet bestaat // maak dan een nieuw knooppunt TrieNode* newNode = new TrieNode();  // Bewaar de referentie voor het nieuw gemaakte // knooppunt.  currentNode->childNode[c - 'a'] = newNode;  } // Verplaats nu de huidige knooppuntaanwijzer naar het nieuw // gemaakte knooppunt.  currentNode = currentNode->childNode[c - 'a'];  } // Verhoog de wordEndCount voor de laatste currentNode // pointer, dit impliceert dat er een string is die eindigt op // currentNode.  currentNode->wordEnd = 1; } bool search_key(TrieNode* root, string& key) {// Initialiseer de currentNode-aanwijzer // met het rootknooppunt TrieNode* currentNode = root;  // Herhaal over de lengte van de tekenreeks voor (auto c: key) {// Controleer of het knooppunt bestaat voor het huidige // teken in de Trie.  if (currentNode->childNode[c - 'a'] == NULL) {// Opgegeven woord bestaat niet in Trie return false;  } // Verplaats de currentNode-aanwijzer naar het reeds // bestaande knooppunt voor het huidige teken.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == waar); } // Stuurprogrammacode int main() {// Maak een rootknooppunt voor de Trie TrieNode* root = new TrieNode();  // Slaat de tekenreeksen op die we willen invoegen in de // Trie-vectorinputStrings = { 'en', 'ant', 'do', 'geek', 'papa', 'bal' };  // aantal invoegbewerkingen in de Trie int n = inputStrings.size();  voor (int i = 0; ik< n; i++) {  insert_key(root, inputStrings[i]);  }  // Stores the strings that we want to search in the Trie  vectorsearchQueryStrings = { 'do', 'geek', 'bat' };  // aantal zoekbewerkingen in de Trie int searchQueries = searchQueryStrings.size();  voor (int i = 0; ik< 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; }>

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

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

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']; // Zoek naar elke string en druk af of deze gevonden is in de Trie searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('De queryreeks is aanwezig in de Trie'); else { console.log('De queryreeks is niet aanwezig in de Trie');>

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>

Probeer verwijderen

Inhoud van Trie weergeven

Functie voor automatisch aanvullen met Trie

Patroon zoeken met behulp van een combinatie van alle achtervoegsels

Oefenproblemen:

• Minimale woordonderbreking
• Unieke rijen in een binaire matrix
• Aantal verschillende subtekenreeksen
• Woord Boggle
• Sortering van een reeks tekenreeksen (of woorden) met behulp van Trie