De Prøv datastruktur er en trelignende datastruktur som brukes til å lagre et dynamisk sett med strenger. Det er ofte brukt for effektiv henting og Oppbevaring av nøkler i et stort datasett. Strukturen støtter operasjoner som f.eks innsetting , Søk , og sletting av nøkler, noe som gjør det til et verdifullt verktøy innen felt som informatikk og informasjonsinnhenting. I denne artikkelen skal vi utforske innsetting og søk operasjon i Trie Data Structure.

Prøv datastruktur

Innholdsfortegnelse

• Representasjon av av Trie Node
• Representasjon av Trie Node:

  EN Prøv datastruktur består av noder forbundet med kanter. Hver node representerer et tegn eller en del av en streng. Rotnoden, startpunktet til Trie, representerer en tom streng. Hver kant som kommer fra en node betyr en spesifikk karakter. Banen fra roten til en node representerer prefikset til en streng lagret i Trie.

  En enkel struktur for å representere noder i det engelske alfabetet kan være som følger.

  
  
  
  

  gyldige identifikatorer i java

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

  La oss gå gjennom prosessen med å sette inn ordene i en Trie-datastruktur. Vi har allerede dekket det grunnleggende om Trie og nodestrukturen.

  deterministiske endelige automater

  Her er en visuell representasjon av å sette inn ordene og og på inn i en Trie-datastruktur:

  
  

  
  

  
  

  Sett inn operasjon i Trie Data Structure

  
  

  Setter inn og i Trie datastruktur:

  mac-operativsystemer

  • Start ved rotnoden: Rotnoden har ingen tegn knyttet til seg og dens ordslutt verdien er 0 , som indikerer at ingen komplette ord slutter på dette tidspunktet.
  • Første tegn a: Beregn indeksen ved å bruke ' a' – 'a' = 0 . Sjekk om childNode[0] er null . Siden det er, lag en ny TrieNode med tegnet en , ordslutt satt til 0 , og et tomt utvalg av pekere. Flytt til denne nye noden.
  • Andre tegn n: Beregn indeksen ved hjelp av ‘n’ – ‘a’ = 13 . Sjekk om childNode[13] er null . Det er det, så lag en ny TrieNode med tegnet n , ordslutt satt til 0 , og et tomt utvalg av pekere. Flytt til denne nye noden.
  • Tredje tegn d: Beregn indeksen ved å bruke ' d’ – ‘a’ = 3 . Sjekk om childNode[3 ] er null . Det er det, så lag en ny TrieNode med tegnet d , ordslutt satt til 1 (som indikerer ordet og slutter her).

  Setter inn maur i Trie-datastrukturen:

  • Start ved rotnoden: Rotnoden inneholder ingen data, men den holder styr på hvert første tegn i hver streng som er satt inn.
  • Første tegn a: Beregn indeksen ved å bruke ' a' – 'a' = 0 . Sjekk om childNode[0] er null . Vi har allerede en node opprettet fra forrige innsetting. så flytt til det eksisterende en node.
  • Første tegn n: Beregn indeksen ved å bruke ' n' – 'a' = 13 . Sjekk om barnNode [13] er null . Det er det ikke, så flytt til det eksisterende n node.
  • Andre tegn t: Beregn indeksen ved hjelp av 't' – 'a' = 19 . Sjekk om barnNode [19] er null . Det er det, så lag en ny TrieNode med karakteren t , ordslutt satt til 1 (som indikerer at ordet maur slutter her).

  Nedenfor er implementeringen av innsetting av strenger 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) { // Hvis node for gjeldende karakter ikke eksisterer // så lag en ny node TrieNode* newNode = new TrieNode();  // Behold referansen for den nyopprettede //-noden.  currentNode->childNode[c - 'a'] = nyNode;  } // Flytt nå gjeldende nodepeker til den nyopprettede noden.  currentNode = currentNode->childNode[c - 'a'];  } // Øk wordEndCount for den siste gjeldendeNode //-pekeren dette antyder at det er en streng som slutter på // currentNode.  gjeldendeNode->wordEnd = 1; }>

  Tidskompleksitet: O(antall ord * maxLengthOfWord)
  Hjelpeplass: O(antall ord * maxLengthOfWord)

  Å søke etter en nøkkel i Trie-datastrukturen ligner på innsettingsoperasjonen. Imidlertid bare det sammenligner karakterene og beveger seg nedover . Søket kan avsluttes på grunn av slutten av en streng eller mangel på nøkkel i forsøket.

  Trinn for trinn tilnærming for søk i Trie Data-struktur:

  freddie mercury

  • Start ved rotnoden. Dette er utgangspunktet for alle søk i Trie.
  • Gå gjennom prøven basert på tegnene i ordet du søker etter. For hver karakter følger du den tilsvarende grenen i prøven. Hvis grenen ikke eksisterer, finnes ikke ordet i Trie.
  • Hvis du kommer til slutten av ordet og ordet End-flagget er satt til 1, er ordet funnet.
  • Hvis du kommer til slutten av ordet og ordsluttflagget er 0, er ordet ikke til stede i prøven, selv om det deler et prefiks med et eksisterende ord.

  Her er en visuell representasjon av søkeord pappa i Trie datastruktur:

  La oss anta at vi har satt inn ordene og , på , og pappa inn i vår Trie, og vi må søke etter spesifikke ord i Trie-datastrukturen. La oss prøve å søke etter ordet pappa :

  
  

  

  Søkeoperasjon i Trie Data Structure

  
  

  • Vi starter ved rotnoden.
  • Vi følger grenen som tilsvarer tegnet 'd'.
  • Vi følger grenen som tilsvarer tegnet a'.
  • Vi følger grenen som tilsvarer tegnet 'd'.
  • Vi når slutten av ordet og ordslutt flagget er 1 . Dette betyr at pappa er til stede i Trie.

  Nedenfor er implementeringen av søkestrenger 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) { // Gitt ord eksisterer ikke i Trie return false;  } // Flytt den gjeldende nodepekeren til den allerede // eksisterende noden for gjeldende tegn.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); }>

  Tidskompleksitet: O(antall ord * maxLengthOfWord)
  Hjelpeplass: O(antall ord * maxLengthOfWord)

  heltall til streng java

  Lag en rotnode ved hjelp av TrieNode() konstruktør.

• Lagre en samling av strenger som må settes inn i prøven i en vektor av strenger, si, arr .
• Setter inn alle strenger i Trie ved hjelp av insert_key() funksjon,
• Søkestrenger ved hjelp av søkenøkkel() funksjon.

Nedenfor er implementeringen av tilnærmingen ovenfor:

#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) { // Hvis node for gjeldende karakter ikke eksisterer // så lag en ny node TrieNode* newNode = new TrieNode();  // Behold referansen for den nyopprettede //-noden.  currentNode->childNode[c - 'a'] = nyNode;  } // Flytt nå gjeldende nodepeker til den nyopprettede noden.  currentNode = currentNode->childNode[c - 'a'];  } // Øk wordEndCount for den siste gjeldendeNode //-pekeren dette antyder at det er en streng som slutter på // currentNode.  gjeldendeNode->wordEnd = 1; } bool search_key(TrieNode* root, string& key) { // Initialiser currentNode-pekeren // med rotnoden TrieNode* currentNode = root;  // Iterer over lengden på strengen for (auto c : key) { // Sjekk om noden eksisterer for gjeldende //-tegnet i prøven.  if (currentNode->childNode[c - 'a'] == NULL) { // Gitt ord finnes ikke i Trie return false;  } // Flytt den gjeldende nodepekeren til den allerede // eksisterende noden for gjeldende tegn.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); } // Driverkode int main() { // Lag en rotnode for Trie TrieNode* root = new TrieNode();  // Lagrer strengene som vi ønsker å sette inn i // Prøv vektoreninputStrings = { 'og', 'ant', 'do', 'geek', 'pappa', 'ball' };  // antall innsettingsoperasjoner i Trie int n = inputStrings.size();  for (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' };  // antall søkeoperasjoner i Trie int searchQueries = searchQueryStrings.size();  for (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; }>

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']; // Søk etter hver streng og skriv ut om den finnes i Prøve searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('Spørringsstrengen er tilstede i 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>

Prøv å slette

Viser innhold av Trie

Autofullfør funksjon ved å bruke Prøv

Mønstersøk med en prøve av alle suffikser

Øvingsproblemer:

• Minimum Word Break
• Unike rader i en binær matrise
• Antall distinkte understrenger
• Ordet Boggle
• Sortering av strenger (eller ord) ved hjelp av Trie