PROVA LA STRUTTURA DEI DATI | INSERISCI E CERCA - TECHCODEVIEW.COM

IL Prova la struttura dei dati è una struttura dati ad albero utilizzata per memorizzare un insieme dinamico di stringhe. È comunemente usato per efficiente recupero E magazzinaggio di chiavi in un set di dati di grandi dimensioni. La struttura supporta operazioni come inserimento , ricerca , E cancellazione di chiavi, rendendolo uno strumento prezioso in campi come l'informatica e il recupero delle informazioni. In questo articolo esploreremo inserimento e ricerca operazione nella struttura dati Trie.

Prova la struttura dei dati

Tabella dei contenuti

Rappresentazione del nodo Trie
Rappresentazione del Nodo Trie:
UN Prova la struttura dei dati è costituito da nodi collegati da bordi. Ogni nodo rappresenta un carattere o una parte di una stringa. Il nodo radice, punto iniziale del Trie, rappresenta una stringa vuota. Ogni bordo proveniente da un nodo indica un carattere specifico. Il percorso dalla radice a un nodo rappresenta il prefisso di una stringa memorizzata nel Trie.

Una struttura semplice per rappresentare i nodi dell'alfabeto inglese può essere la seguente.

espressione regolare Java per
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; } } };>Giavapublic 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; } } }>
Esaminiamo il processo di inserimento delle parole in una struttura dati Trie. Abbiamo già trattato le basi di Trie e della sua struttura a nodi.
data locale Java

Ecco una rappresentazione visiva dell'inserimento delle parole E E SU in una struttura dati Trie:
Inserisci operazione nella struttura dati Trie

Inserendo e nella struttura dati Trie:
metodo Java con sovrascrittura
- Inizia dal nodo radice: Il nodo radice non ha alcun carattere associato ad esso e al suo parolaFine il valore è 0 , indicando che nessuna parola completa termina a questo punto.
- Primo carattere a: Calcola l'indice utilizzando ' a’ – ‘a’ = 0 . Controlla se il nodofiglio[0] È nullo . Poiché lo è, crea un nuovo TrieNode con il personaggio UN , parolaFine impostato 0 e un array vuoto di puntatori. Passa a questo nuovo nodo.
- Secondo carattere n: Calcolare l'indice utilizzando ‘n’ – ‘a’ = 13 . Controlla se nodofiglio[13] È nullo . Lo è, quindi crea un nuovo TrieNode con il personaggio N , parolaFine impostato 0 e un array vuoto di puntatori. Passa a questo nuovo nodo.
- Terzo carattere d: Calcola l'indice utilizzando ' d’ – ‘a’ = 3 . Controlla se nodofiglio[3 ] È nullo . Lo è, quindi crea un nuovo TrieNode con il personaggio D , parolaFine impostato 1 (indicando la parola E finisce qui).
Inserimento di formica nella struttura dati Trie:
- Inizia dal nodo radice: Il nodo radice non contiene dati ma tiene traccia di ogni primo carattere di ogni stringa inserita.
- Primo carattere a: Calcola l'indice utilizzando ' a’ – ‘a’ = 0 . Controlla se il nodofiglio[0] È nullo . Abbiamo già il UN nodo creato dall'inserimento precedente. quindi passa all'esistente UN nodo.
- Primo carattere n: Calcola l'indice utilizzando ' n’ – ‘a’ = 13 . Controlla se childNode [13] lo è nullo . Non lo è, quindi passa all’esistente N nodo.
- Secondo carattere t: Calcolare l'indice utilizzando ‘t’ – ‘a’ = 19 . Controlla se childNode [19] è nullo . Lo è, quindi crea un nuovo TrieNode con il personaggio T , parolaFine impostato 1 (indicando la parola formica che termina qui).
Di seguito è riportata l'implementazione dell'inserimento di stringhe nella struttura dati 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) { // Se il nodo per il carattere corrente non esiste // crea un nuovo nodo TrieNode* newNode = new TrieNode(); // Conserva il riferimento per il // nodo appena creato. currentNode->childNode[c - 'a'] = newNode; } // Ora sposta il puntatore del nodo corrente sul nodo appena // creato. currentNode = currentNode->childNode[c - 'a']; } // Incrementa wordEndCount per l'ultimo puntatore currentNode // ciò implica che esiste una stringa che termina con // currentNode. currentNode->wordEnd = 1; }>
Complessità temporale: O(numero di parole * maxLengthOfWord)
Spazio ausiliario: O(numero di parole * maxLengthOfWord)
La ricerca di una chiave nella struttura dati Trie è simile alla sua operazione di inserimento. Tuttavia, solo confronta i personaggi e scende . La ricerca può terminare per la fine di una stringa o per la mancanza di una chiave nel trie.

Approccio passo passo per la ricerca nella struttura dei dati Trie:
cos'è F5 sulla tastiera?
- Inizia dal nodo radice. Questo è il punto di partenza per tutte le ricerche all'interno del Trie.
- Attraversa il Trie in base ai caratteri della parola che stai cercando. Per ogni carattere seguire il ramo corrispondente nel Trie. Se il ramo non esiste, la parola non è presente nel Trie.
- Se raggiungi la fine della parola e il flag wordEnd è impostato su 1, la parola è stata trovata.
- Se raggiungi la fine della parola e il flag wordEnd è 0, la parola non è presente nel Trie, anche se condivide un prefisso con una parola esistente.
Ecco una rappresentazione visiva della parola da cercare Papà nella struttura dati Trie:
Supponiamo di aver inserito correttamente le parole E , SU , E Papà nel nostro Trie e dobbiamo cercare parole specifiche all'interno della struttura dati Trie. Proviamo a cercare la parola Papà :

Operazione di ricerca nella struttura dati Trie
- Iniziamo dal nodo radice.
- Seguiamo il ramo corrispondente al carattere “d”.
- Seguiamo il ramo corrispondente al carattere a’.
- Seguiamo il ramo corrispondente al carattere “d”.
- Raggiungiamo la fine della parola e parolaFine la bandiera è 1 . Ciò significa che Papà è presente nel Trie.
Di seguito è riportata l'implementazione della ricerca di stringhe in 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) { // La parola data non esiste in Trie return false; } // Sposta il puntatore currentNode sul nodo già // esistente per il carattere corrente. currentNode = currentNode->childNode[c - 'a']; } return (currentNode->wordEnd == true); }>
Complessità temporale: O(numero di parole * maxLengthOfWord)
Spazio ausiliario: O(numero di parole * maxLengthOfWord)
intero in stringa java
Crea un nodo radice con l'aiuto di TrieNodo() costruttore.
Memorizza una raccolta di stringhe che devono essere inserite nel trie in un vettore di stringhe, ad esempio, arr .
Inserimento di tutte le stringhe in Trie con l'aiuto di inserisci_chiave() funzione,
Cerca stringhe con l'aiuto di chiave_ricerca() funzione.

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

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) { // Se il nodo per il carattere corrente non esiste // crea un nuovo nodo TrieNode* newNode = new TrieNode();  // Conserva il riferimento per il // nodo appena creato.  currentNode->childNode[c - 'a'] = newNode;  } // Ora sposta il puntatore del nodo corrente sul nodo appena // creato.  currentNode = currentNode->childNode[c - 'a'];  } // Incrementa wordEndCount per l'ultimo puntatore currentNode // ciò implica che esiste una stringa che termina con // currentNode.  currentNode->wordEnd = 1; } bool search_key(TrieNode* root, string& key) { // Inizializza il puntatore currentNode // con il nodo root TrieNode* currentNode = root;  // Itera lungo la lunghezza della stringa for (auto c: key) { // Controlla se il nodo esiste per il // carattere corrente nel Trie.  if (currentNode->childNode[c - 'a'] == NULL) { // La parola data non esiste in Trie return false;  } // Sposta il puntatore currentNode sul nodo già // esistente per il carattere corrente.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); } // Codice driver int main() { // Crea un nodo radice per Trie TrieNode* root = new TrieNode();  // Memorizza le stringhe che vogliamo inserire nel // vettore TrieinputStrings = { 'e', 'formica', 'fai', 'geek', 'papà', 'palla' };  // numero di operazioni di inserimento nel 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 = { 'fai', 'geek', 'bat' };  // numero di operazioni di ricerca nel 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; }>

Giava

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

Pitone

 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 = ['fai', 'geek', 'bat']; // Cerca ogni stringa e stampa se viene trovata nel Trie searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('La stringa di query è presente nel Trie'); else { console.log('La stringa di query non è presente nel Trie'} });>

Produzione

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>

Prova Elimina
Visualizzazione del contenuto di Trie
Funzionalità di completamento automatico utilizzando Trie
Ricerca di modelli utilizzando una prova di tutti i suffissi
Problemi pratici:

Interruzione minima di parole
Righe uniche in una matrice binaria
Conteggio di sottostringhe distinte
Parola Boggle
Ordinamento di array di stringhe (o parole) utilizzando Trie

TechCodeview

Prova la struttura dei dati | Inserisci e cerca

Crea un nodo radice con l'aiuto di TrieNodo() costruttore.