logo

TechCodeview

Amazon

Trie Structura datelor | Inserați și căutați

Trie Structura datelor | Inserați și căutați

The Încercați structura de date este o structură de date arborescent utilizată pentru stocarea unui set dinamic de șiruri. Este folosit în mod obișnuit pentru eficient regăsire și depozitare de chei dintr-un set mare de date. Structura suportă operațiuni precum inserare , căutare , și stergere de chei, făcându-l un instrument valoros în domenii precum informatica și regăsirea informațiilor. În acest articol vom explora inserare și căutare operare în Trie Data Structure.

Încercați structura de date

Încercați structura de date

Cuprins

Mai jos este implementarea abordării de mai sus:

C++ childNode[c - 'a'] = newNode; } // Acum, mutați indicatorul nodului curent la nodul nou // creat. currentNode = currentNode->childNode[c - 'a']; } // Incrementează wordEndCount pentru ultimul indicator // currentNode, aceasta implică faptul că există un șir care se termină la // currentNode. currentNode->wordEnd = 1; } bool search_key(TrieNode* root, string& key) { // Inițializează indicatorul currentNode // cu nodul rădăcină TrieNode* currentNode = root; // Iterați pe lungimea șirului pentru (auto c : key) { // Verificați dacă nodul există pentru caracterul curent // din Trie. if (currentNode->childNode[c - 'a'] == NULL) { // Cuvântul dat nu există în Trie return false; } // Mută ​​indicatorul currentNode către nodul deja // existent pentru caracterul curent. currentNode = currentNode->childNode[c - 'a']; } return (currentNode->wordEnd == true); } // Cod driver int main() { // Faceți un nod rădăcină pentru rădăcina Trie TrieNode* = new TrieNode(); // Stochează șirurile pe care vrem să le inserăm în // vectorul Trie inputStrings = { 'and', 'ant', 'do', 'geek', 'tata', 'ball'}; // numărul de operații de inserare în Trie int n = inputStrings.size(); pentru (int i = 0; i < n; i++) { insert_key(root, inputStrings[i]); } // Stores the strings that we want to search in the Trie vector searchQueryStrings = { 'do', 'geek', 'bat'}; // numărul de operații de căutare în Trie int searchQueries = searchQueryStrings.size(); pentru (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');  }  }  } }
Piton 
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']; // Căutați fiecare șir și imprimați dacă acesta este găsit în Trie searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('Șirul de interogare este prezent în Trie' } else { console.log('Șirul de interogare nu este prezent în Trie');>>>   
  Ieșire       Articole similare:        
  
     
  •    Încercați Ștergeți    
  •       Se afișează conținutul Trie    
    •  
  •       Funcție de completare automată folosind Trie    
    •  
  •    Căutarea modelelor folosind o încercare a tuturor sufixelor    
    •  
         Probleme de practică:      
       
       
    •   Pauza minimă de cuvânt   
      •  
    •   Rânduri unice într-o matrice binară   
      •  
    •   Număr de subșiruri distincte   
      •  
    •   Word Boggle   
      •  
    •   Sortarea matricei de șiruri (sau cuvinte) folosind Trie      
      •

Distribuie

S-Ar Putea Să Vă Placă

MySQL DESCRIERE TABEL

MySQL DESCRIERE TABEL

Liste de dart

Liste de dart

Top Articole

Categorie

Blog Conversie Java Matematica Colecții Java Diferențele Șir Java

Articole Interesante