logo

TechCodeview

Prova datastruktur | Infoga och sök

De Prova datastruktur är en trädliknande datastruktur som används för att lagra en dynamisk uppsättning strängar. Det används ofta för effektiv hämtning och lagring av nycklar i en stor datamängd. Strukturen stödjer verksamheter som t.ex införande , Sök , och radering av nycklar, vilket gör det till ett värdefullt verktyg inom områden som datavetenskap och informationssökning. I den här artikeln ska vi utforska infogning och sökning operation i Trie Data Structure.

Prova datastruktur

Prova datastruktur



Innehållsförteckning

  • Representation av av Trie Node
  • Representation av Trie Node:

    A Prova datastruktur består av noder förbundna med kanter. Varje nod representerar ett tecken eller en del av en sträng. Rotnoden, startpunkten för Trie, representerar en tom sträng. Varje kant som kommer från en nod betecknar en specifik karaktär. Sökvägen från roten till en nod representerar prefixet för en sträng lagrad i Trie.

    En enkel struktur för att representera noder i det engelska alfabetet kan vara följande.



    tcp och ip-modell
    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;  }  } }>

    Låt oss gå igenom processen att infoga orden i en Trie-datastruktur. Vi har redan täckt grunderna i Trie och dess nodstruktur.

    java lokaldatum

    Här är en visuell representation av att infoga orden och och på in i en Trie-datastruktur:




    Infoga operation i Trie Data Structure


    Infogar och i Trie datastruktur:

    java visualizer
    • Börja vid rotnoden: Rotnoden har inget tecken associerat med sig och dess ordslut värde är 0 , vilket indikerar att inget komplett ord slutar vid denna punkt.
    • Första tecknet a: Beräkna indexet med ' a' – 'a' = 0 . Kontrollera om childNode[0] är null . Eftersom det är, skapa en ny TrieNode med karaktären a , ordslut satt till 0 , och en tom uppsättning pekare. Flytta till den här nya noden.
    • Andra tecknet n: Beräkna indexet med hjälp av 'n' – 'a' = 13 . Kolla om childNode[13] är null . Det är det, så skapa en ny TrieNode med karaktären n , ordslut satt till 0 , och en tom uppsättning pekare. Flytta till den här nya noden.
    • Tredje tecken d: Beräkna indexet med ' d’ – ‘a’ = 3 . Kolla om childNode[3 ] är null . Det är det, så skapa en ny TrieNode med karaktären d , ordslut satt till 1 (som indikerar ordet och slutar här).

    Infogar myra i Trie-datastrukturen:

    • Börja vid rotnoden: Rotnoden innehåller ingen data men den håller reda på varje första tecken i varje sträng som har infogats.
    • Första tecknet a: Beräkna indexet med ' a' – 'a' = 0 . Kontrollera om childNode[0] är null . Vi har redan a nod skapad från föregående infogning. så flytta till det befintliga a nod.
    • Första tecknet n: Beräkna indexet med ' n' – 'a' = 13 . Kolla om barnnod [13] är null . Det är det inte, så flytta till det befintliga n nod.
    • Andra tecknet t: Beräkna indexet med hjälp av 't' – 'a' = 19 . Kolla om barnnod [19] är null . Det är det, så skapa en ny TrieNode med karaktären t , ordslut satt till 1 (som anger ordet myra slutar här).

    Nedan är implementeringen av infogning av strängar i Trie datastruktur:

    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) { // Om noden för nuvarande karaktär inte finns // gör sedan en ny nod TrieNode* newNode = new TrieNode();  // Behåll referensen för den nyskapade //-noden.  currentNode->childNode[c - 'a'] = nyNod;  } // Flytta nu den aktuella nodpekaren till den nyskapade // noden.  currentNode = currentNode->childNode[c - 'a'];  } // Öka wordEndCount för den sista currentNode //-pekaren detta innebär att det finns en sträng som slutar på // currentNode.  currentNode->wordEnd = 1; }>

    Tidskomplexitet: O(antal ord * maxLengthOfWord)
    Hjälputrymme: O(antal ord * maxLengthOfWord)

    Att söka efter en nyckel i Trie-datastrukturen liknar dess infogningsoperation. Dock bara det jämför karaktärerna och flyttar ner . Sökningen kan avslutas på grund av slutet på en sträng eller avsaknad av nyckel i försöket.

    Steg för steg tillvägagångssätt för sökning i Trie Data-struktur:

    • Börja vid rotnoden. Detta är utgångspunkten för alla sökningar inom Trie.
    • Gå igenom Trie baserat på tecknen i ordet du söker efter. För varje karaktär, följ motsvarande gren i Trie. Om grenen inte finns finns ordet inte närvarande i Trie.
    • Om du når slutet av ordet och wordEnd-flaggan är satt till 1, har ordet hittats.
    • Om du når slutet av ordet och ordslutflaggan är 0, finns ordet inte närvarande i Trie, även om det delar ett prefix med ett befintligt ord.

    Här är en visuell representation av sökord pappa i Trie datastruktur:

    Låt oss anta att vi framgångsrikt har infogat orden och , på , och pappa i vår Trie, och vi måste söka efter specifika ord inom Trie-datastrukturen. Låt oss försöka söka efter ordet pappa :


    Sökoperation i Trie Data Structure

    java kommentarer


    • Vi börjar vid rotnoden.
    • Vi följer grenen som motsvarar tecknet 'd'.
    • Vi följer grenen som motsvarar tecknet a'.
    • Vi följer grenen som motsvarar tecknet 'd'.
    • Vi når slutet av ordet och ordslut flaggan är 1 . Detta innebär att pappa är närvarande i Trie.

    Nedan är implementeringen av söksträngar i 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) { // Givet ord finns inte i Trie return false;  } // Flytta den aktuella nodpekaren till den redan // befintliga noden för aktuellt tecken.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); }>

    Tidskomplexitet: O(antal ord * maxLengthOfWord)
    Hjälputrymme: O(antal ord * maxLengthOfWord)

    heltal till sträng java

    Skapa en rotnod med hjälp av TrieNode() konstruktör.

  • Lagra en samling strängar som måste infogas i försöket i en vektor av strängar, säg, arr .
  • Infogar alla strängar i Trie med hjälp av insert_key() fungera,
  • Söksträngar med hjälp av söknyckel() fungera.

Nedan är implementeringen av ovanstående tillvägagångssätt:

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) { // Om noden för nuvarande karaktär inte finns // gör sedan en ny nod TrieNode* newNode = new TrieNode();  // Behåll referensen för den nyskapade //-noden.  currentNode->childNode[c - 'a'] = nyNod;  } // Flytta nu den aktuella nodpekaren till den nyskapade // noden.  currentNode = currentNode->childNode[c - 'a'];  } // Öka wordEndCount för den sista currentNode //-pekaren detta innebär att det finns en sträng som slutar på // currentNode.  currentNode->wordEnd = 1; } bool search_key(TrieNode* root, string& key) { // Initiera currentNode-pekaren // med rotnoden TrieNode* currentNode = root;  // Iterera över strängens längd för (auto c : nyckel) { // Kontrollera om noden finns för det aktuella tecknet // i försöket.  if (currentNode->childNode[c - 'a'] == NULL) { // Givet ord finns inte i Trie return false;  } // Flytta den aktuella nodpekaren till den redan // befintliga noden för aktuellt tecken.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); } // Drivrutinskod int main() { // Gör en rotnod för Trie TrieNode* root = new TrieNode();  // Lagrar strängarna som vi vill infoga i // Trie-vektorninputStrings = { 'and', 'ant', 'do', 'geek', 'pappa', 'ball' };  // antal infogningsoperationer i försöket 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' };  // antal sökoperationer i 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');  }  }  } }>
Pytonorm 
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']; // Sök efter varje sträng och skriv ut om den finns i Trie searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('Frågesträngen finns i Trie'); } else { console.log('Frågesträngen finns inte i Trie' } });>
Produktion 
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>

Försök radera
  • Visar innehåll från Trie
  • Automatisk kompletteringsfunktion med hjälp av Trie
  • Mönstersökning med ett försök med alla suffix

    • Övningsproblem:

    • Minsta ordavbrott
    • Unika rader i en binär matris
    • Antal distinkta delsträngar
    • Ordet Boggle
    • Sortering av strängar (eller ord) med hjälp av Trie