The Preizkusite strukturo podatkov je drevesna podatkovna struktura, ki se uporablja za shranjevanje dinamičnega nabora nizov. Običajno se uporablja za učinkovito iskanje in shranjevanje ključev v velikem naboru podatkov. Struktura podpira operacije, kot je npr vstavljanje , Iskanje , in izbris ključev, zaradi česar je dragoceno orodje na področjih, kot sta računalništvo in iskanje informacij. V tem članku bomo raziskali vstavljanje in iskanje delovanje v Trie Data Structure.

Preizkusite strukturo podatkov

Kazalo

• Predstavitev vozlišča Trie
• Predstavitev vozlišča Trie:

  A Preizkusite strukturo podatkov sestoji iz vozlišč, povezanih z robovi. Vsako vozlišče predstavlja znak ali del niza. Korensko vozlišče, začetna točka Trie, predstavlja prazen niz. Vsak rob, ki izhaja iz vozlišča, pomeni določen znak. Pot od korena do vozlišča predstavlja predpono niza, shranjenega v Trie.

  Preprosta struktura za predstavitev vozlišč angleške abecede je lahko naslednja.

  
  
  
  

  Neena Gupta

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

  Sprehodimo se skozi postopek vstavljanja besed v podatkovno strukturo Trie. Osnove Trie in njegove strukture vozlišč smo že obravnavali.

  algoritem za razvrščanje vstavljanja

  Tukaj je vizualna predstavitev vstavljanja besed in in na v podatkovno strukturo Trie:

  
  

  
  

  
  

  Vstavi operacijo v podatkovno strukturo Trie

  
  

  Vstavljanje in v strukturo podatkov Trie:

  tokenizer nizov java

  • Začnite pri korenskem vozlišču: Korensko vozlišče nima znaka, povezanega z njim in njegovim wordEnd vrednost je 0 , kar pomeni, da se na tej točki ne konča nobena popolna beseda.
  • Prvi znak a: Izračunajte indeks z uporabo a’ – ‘a’ = 0 . Preverite, ali je otrokovo vozlišče[0] je nič . Ker je, ustvarite nov TrieNode z znakom a , wordEnd nastavljena 0 in prazen niz kazalcev. Premakni se na to novo vozlišče.
  • Drugi znak n: Izračunajte indeks z uporabo 'n' – 'a' = 13 . Preverite, če childNode [13] je nič . Je, zato ustvarite nov TrieNode z likom n , wordEnd nastavljena 0 in prazen niz kazalcev. Premakni se na to novo vozlišče.
  • Tretji znak d: Izračunajte indeks z uporabo d’ – ‘a’ = 3 . Preverite, če otrokovo vozlišče [3 ] je nič . Je, zato ustvarite nov TrieNode z likom d , wordEnd nastavljena 1 (označuje besedo in konča tukaj).

  Vstavljanje mravelj v podatkovno strukturo Trie:

  • Začnite pri korenskem vozlišču: Korensko vozlišče ne vsebuje nobenih podatkov, vendar spremlja vsak prvi znak vsakega niza, ki je bil vstavljen.
  • Prvi znak a: Izračunajte indeks z uporabo a’ – ‘a’ = 0 . Preverite, ali je otrokovo vozlišče[0] je nič . Že imamo a vozlišče, ustvarjeno iz prejšnjega vstavljanja. torej premakniti na obstoječe a vozlišče.
  • Prvi znak n: Izračunajte indeks z uporabo n’ – ‘a’ = 13 . Preverite, če childNode [13] je nič . Ni, zato se premaknite na obstoječe n vozlišče.
  • Drugi znak t: Izračunajte indeks z uporabo 't' – 'a' = 19 . Preverite, če childNode [19] je nič . Je, zato ustvarite nov TrieNode z likom t , wordEnd nastavljena 1 (kar pomeni, da se beseda mravlja tukaj konča).

  Spodaj je implementacija vstavljanja nizov v podatkovno strukturo Trie:

  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) { // Če vozlišče za trenutni znak ne obstaja // naredi novo vozlišče TrieNode* newNode = new TrieNode();  // Ohrani referenco za novo ustvarjeno // vozlišče.  currentNode->childNode[c - 'a'] = newNode;  } // Zdaj premaknite kazalec trenutnega vozlišča na novo // ustvarjeno vozlišče.  currentNode = currentNode->childNode[c - 'a'];  } // Povečaj wordEndCount za zadnji kazalec currentNode // to pomeni, da obstaja niz, ki se konča na // currentNode.  currentNode->wordEnd = 1; }>

  Časovna zapletenost: O(število besed * maxLengthOfWord)
  Pomožni prostor: O(število besed * maxLengthOfWord)

  Iskanje ključa v podatkovni strukturi Trie je podobno operaciji vstavljanja. Vendar pa samo primerja like in se premika navzdol . Iskanje se lahko prekine zaradi konca niza ali pomanjkanja ključa v poskusu.

  Pristop po korakih za iskanje v strukturi Trie Data:

  • Začnite pri korenskem vozlišču. To je izhodišče za vsa iskanja znotraj Trie.
  • Prečkajte Trie glede na znake besede, ki jo iščete. Za vsak znak sledite ustrezni veji v Trie. Če veja ne obstaja, besede ni v Trie.
  • Če pridete do konca besede in je zastavica wordEnd nastavljena na 1, je bila beseda najdena.
  • Če pridete do konca besede in je zastavica wordEnd 0, besede ni v Trie, čeprav ima predpono z obstoječo besedo.

  Tukaj je vizualna predstavitev iskane besede oče v podatkovni strukturi Trie:

  java datum zdaj

  Predpostavimo, da smo besede uspešno vstavili in , na , in oče v naš Trie in moramo iskati določene besede znotraj podatkovne strukture Trie. Poskusimo poiskati besedo oče :

  
  

  

  Operacija iskanja v podatkovni strukturi Trie

  
  

  • Začnemo pri korenskem vozlišču.
  • Sledimo veji, ki ustreza znaku 'd'.
  • Sledimo veji, ki ustreza znaku a’.
  • Sledimo veji, ki ustreza znaku 'd'.
  • Pridemo do konca besede in wordEnd zastava je 1 . To pomeni da oče je prisoten v Trie.

  Spodaj je implementacija iskalnih nizov v 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) { // Dana beseda ne obstaja v Trie return false;  } // Premakni kazalec currentNode na že // obstoječe vozlišče za trenutni znak.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); }>

  Časovna zapletenost: O(število besed * maxLengthOfWord)
  Pomožni prostor: O(število besed * maxLengthOfWord)

  celo število v niz java

  Ustvarite korensko vozlišče s pomočjo TrieNode() konstruktor.

• Shranite zbirko nizov, ki jih je treba vstaviti v trie v vektorju nizov, recimo, prir .
• Vstavljanje vseh nizov v Trie s pomočjo vstavi_ključ() funkcija,
• Iskanje nizov s pomočjo search_key() funkcijo.

Spodaj je izvedba zgornjega pristopa:

#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) { // Če vozlišče za trenutni znak ne obstaja // naredi novo vozlišče TrieNode* newNode = new TrieNode();  // Ohrani referenco za novo ustvarjeno // vozlišče.  currentNode->childNode[c - 'a'] = newNode;  } // Zdaj premaknite kazalec trenutnega vozlišča na novo // ustvarjeno vozlišče.  currentNode = currentNode->childNode[c - 'a'];  } // Povečaj wordEndCount za zadnji kazalec currentNode // to pomeni, da obstaja niz, ki se konča na // currentNode.  currentNode->wordEnd = 1; } bool search_key(TrieNode* root, string& key) { // Inicializiraj kazalec currentNode // s korenskim vozliščem TrieNode* currentNode = root;  // Iteracija po dolžini niza za (auto c : key) { // Preverite, ali obstaja vozlišče za trenutni // znak v Trie.  if (currentNode->childNode[c - 'a'] == NULL) { // Dana beseda ne obstaja v Trie return false;  } // Premakni kazalec currentNode na že // obstoječe vozlišče za trenutni znak.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); } // Koda gonilnika int main() { // Ustvarite korensko vozlišče za Trie TrieNode* root = new TrieNode();  // Shrani nize, ki jih želimo vstaviti v vektor // TrieinputStrings = { 'in', 'mravljica', 'do', 'geek', 'oče', 'žoga' };  // število operacij vstavljanja v Trie int n = inputStrings.size();  za (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' };  // število iskalnih operacij v Trie int searchQueries = searchQueryStrings.size();  za (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']; // Poišči vsak niz in izpiši, ali je najden v Trie searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('Poizvedbeni niz je prisoten v Trie'); else { console.log('Poizvedbeni niz ni prisoten v 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>

Poskusite izbrisati

Prikaz vsebine Trie

Funkcija samodokončanja z uporabo Trie

Iskanje vzorcev z uporabo poskusa vseh pripon

Vadbene težave:

• Minimalni prelom besed
• Edinstvene vrstice v binarni matriki
• Število različnih podnizov
• Beseda Boggle
• Razvrščanje niza nizov (ali besed) z uporabo Trie