TRIE STRUCTURA DATELOR | INSERAȚI ȘI CĂUTAȚI - TECHCODEVIEW.COM

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

Cuprins

Reprezentarea lui Trie Node
Reprezentarea nodului Trie:
A Încercați structura de date este format din noduri conectate prin muchii. Fiecare nod reprezintă un caracter sau o parte dintr-un șir. Nodul rădăcină, punctul de plecare al Trie, reprezintă un șir gol. Fiecare margine care emană dintr-un nod semnifică un caracter specific. Calea de la rădăcină la un nod reprezintă prefixul unui șir stocat în Trie.

O structură simplă pentru a reprezenta nodurile alfabetului englez poate fi următoarea.

linie nouă python
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; } } };>Javapublic 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; } } }>
Să parcurgem procesul de inserare a cuvintelor într-o structură de date Trie. Am acoperit deja elementele de bază ale Trie și structura nodurilor sale.
stivă în java

Iată o reprezentare vizuală a inserării cuvintelor și și pe într-o structură de date Trie:
Inserați operația în Trie Data Structure

Inserarea și în structura datelor Trie:
caseta de alertă javascript
- Începeți de la nodul rădăcină: Nodul rădăcină nu are niciun caracter asociat cu el și cu acesta sfârşitul cuvântului valoarea este 0 , indicând nicio sfârșit de cuvânt complet în acest moment.
- Primul caracter a: Calculați indicele folosind „ a’ – ‘a’ = 0 . Verificați dacă childNode[0] este nul . Din moment ce este, creați un nou TrieNode cu personajul A , sfârşitul cuvântului setat la 0 , și o matrice goală de pointeri. Deplasați-vă la acest nou nod.
- Al doilea caracter n: Calculați indicele folosind „n” – „a” = 13 . Verifica daca childNode[13] este nul . Este, așa că creați un nou TrieNode cu personajul n , sfârşitul cuvântului setat la 0 , și o matrice goală de pointeri. Deplasați-vă la acest nou nod.
- Al treilea caracter d: Calculați indicele folosind „ d’ – ‘a’ = 3 . Verifica daca childNode[3 ] este nul . Este, așa că creați un nou TrieNode cu personajul d , sfârşitul cuvântului setat la 1 (indicând cuvântul și se termină aici).
Inserarea furnicii în structura de date Trie:
- Începeți de la nodul rădăcină: Nodul rădăcină nu conține date, dar ține evidența fiecărui prim caracter din fiecare șir care a fost inserat.
- Primul caracter a: Calculați indicele folosind „ a’ – ‘a’ = 0 . Verificați dacă childNode[0] este nul . Avem deja A nod creat din inserția anterioară. deci trece la existent A nodul.
- Primul caracter n: Calculați indicele folosind „ n’ – ‘a’ = 13 . Verifica daca childNode [13] este nul . Nu este, așa că treceți la existent n nodul.
- Al doilea caracter t: Calculați indicele folosind „t” – „a” = 19 . Verifica daca childNode [19] este nul . Este, așa că creați un nou TrieNode cu personajul t , sfârşitul cuvântului setat la 1 (indicarea cuvântului furnică se termină aici).
Mai jos este implementarea inserării șirurilor în structura de date 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) { // Dacă nodul pentru caracterul curent nu există // atunci faceți un nou nod TrieNode* newNode = new TrieNode(); // Păstrați referința pentru noul // nou creat. currentNode->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, ceea ce înseamnă că există un șir care se termină la // currentNode. currentNode->wordEnd = 1; }>>> Complexitatea timpului: O(număr de cuvinte * maxLengthOfWord) Spațiu auxiliar: O(număr de cuvinte * maxLengthOfWord)
Căutarea unei chei în structura de date Trie este similară cu operația de inserare. Cu toate acestea, numai compară personajele și se deplasează în jos . Căutarea se poate termina din cauza sfârșitului unui șir sau a lipsei cheii în încercare. Abordare pas cu pas pentru căutarea în structura Trie Data: Începeți de la nodul rădăcină. Acesta este punctul de plecare pentru toate căutările din cadrul Trie. Traversați Trie pe baza caracterelor cuvântului pe care îl căutați. Pentru fiecare personaj, urmați ramura corespunzătoare din Trie. Dacă ramura nu există, cuvântul nu este prezent în Trie. Dacă ajungeți la sfârșitul cuvântului și indicatorul wordEnd este setat la 1, cuvântul a fost găsit. Dacă ajungeți la sfârșitul cuvântului și indicatorul wordEnd este 0, cuvântul nu este prezent în Trie, chiar dacă are un prefix cu un cuvânt existent. Iată o reprezentare vizuală a cuvântului căutat tata în structura de date Trie: Să presupunem că am inserat cu succes cuvintele și , pe , și tata în Trie-ul nostru și trebuie să căutăm cuvinte specifice în structura de date Trie. Să încercăm să căutăm cuvântul tata : multiplexor doi la unul Operațiune de căutare în Trie Data Structure Începem de la nodul rădăcină. Urmăm ramura corespunzătoare caracterului „d”. Urmăm ramura corespunzătoare caracterului a’. Urmăm ramura corespunzătoare caracterului „d”. Ajungem la sfârșitul cuvântului și sfârşitul cuvântului steag este 1 . Aceasta înseamnă că tata este prezent în Trie. Mai jos este implementarea șirurilor de caractere în Trie Data Structure: C++childNode[c - 'a']; } return (currentNode->wordEnd == true); }>>> Complexitatea timpului: O(număr de cuvinte * maxLengthOfWord) Spațiu auxiliar: O(număr de cuvinte * maxLengthOfWord) întreg în șir java
Creați un nod rădăcină cu ajutorul lui TrieNode() constructor.
Stocați o colecție de șiruri care trebuie inserate în trie într-un vector de șiruri, de exemplu, arr .
Inserarea tuturor șirurilor în Trie cu ajutorul insert_key() funcţie,
Căutați șiruri cu ajutorul lui cheie_căutare() funcţie.

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 TrieinputStrings = { '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  vectorsearchQueryStrings = { '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

TechCodeview

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

`Creați un nod rădăcină cu ajutorul lui TrieNode() constructor.`