TRIE ESTRUCTURA DE DADES | INSEREIX I CERCA - TECHCODEVIEW.COM

El Proveu l'estructura de dades és una estructura de dades en forma d'arbre que s'utilitza per emmagatzemar un conjunt dinàmic de cadenes. S'utilitza habitualment per a eficient recuperació i emmagatzematge de claus en un conjunt de dades gran. L'estructura admet operacions com ara inserció , cerca , i supressió de claus, la qual cosa la converteix en una eina valuosa en camps com la informàtica i la recuperació d'informació. En aquest article anem a explorar inserció i cerca operació a Trie Data Structure.

Proveu l'estructura de dades

Taula de contingut

Representació de Trie Node
Representació del node Trie:
A Proveu l'estructura de dades consta de nodes connectats per arestes. Cada node representa un caràcter o una part d'una cadena. El node arrel, el punt de partida del Trie, representa una cadena buida. Cada vora que emana d'un node significa un caràcter específic. El camí des de l'arrel fins a un node representa el prefix d'una cadena emmagatzemada al Trie.

Una estructura senzilla per representar nodes de l'alfabet anglès pot ser la següent.

nbsp
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; } } }>
Passem pel procés d'inserció de les paraules en una estructura de dades de Trie. Ja hem cobert els conceptes bàsics de Trie i la seva estructura de nodes.
apilar en java

Aquí teniu una representació visual d'inserir les paraules i i activat en una estructura de dades Trie:
Operació d'inserció a l'estructura de dades Trie

Inserint i a l'estructura de dades de Trie:
Bubble sort python
- Comenceu al node arrel: El node arrel no té cap caràcter associat amb ell i el seu final de paraula el valor és 0 , indicant que no s'acabi cap paraula completa en aquest punt.
- Primer personatge a: Calcula l'índex amb ' a’ – ‘a’ = 0 . Comproveu si el childNode[0] és nul . Com que ho és, creeu un nou TrieNode amb el personatge a , final de paraula ajustat a 0 , i una matriu buida de punters. Mou-te a aquest nou node.
- Segon caràcter n: Calcula l'índex utilitzant ‘n’ – ‘a’ = 13 . Comproveu si childNode[13] és nul . Ho és, així que creeu un nou TrieNode amb el personatge n , final de paraula ajustat a 0 , i una matriu buida de punters. Mou-te a aquest nou node.
- Tercer caràcter d: Calcula l'índex amb ' d’ – ‘a’ = 3 . Comproveu si childNode[3 ] és nul . Ho és, així que creeu un nou TrieNode amb el personatge d , final de paraula ajustat a 1 (indicant la paraula i acaba aquí).
Inserció de formiga a l'estructura de dades de Trie:
- Comenceu al node arrel: El node arrel no conté cap dada, però fa un seguiment de cada primer caràcter de cada cadena que s'ha inserit.
- Primer personatge a: Calcula l'índex amb ' a’ – ‘a’ = 0 . Comproveu si el childNode[0] és nul . Ja tenim el a node creat a partir de la inserció anterior. així que passa a l'existent a node.
- Primer caràcter n: Calcula l'índex amb ' n’ – ‘a’ = 13 . Comproveu si childNode [13] és nul . No ho és, així que passa a l'existent n node.
- Segon caràcter t: Calcula l'índex utilitzant 't' - 'a' = 19 . Comproveu si childNode [19] és nul . Ho és, així que creeu un nou TrieNode amb el personatge t , final de paraula ajustat a 1 (indicant que la paraula formiga acaba aquí).
A continuació es mostra la implementació de la inserció de cadenes a l'estructura de dades de 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) { // Si el node per al caràcter actual no existeix // llavors feu un nou node TrieNode* newNode = nou TrieNode(); // Mantenir la referència per al // node acabat de crear. currentNode->childNode[c - 'a'] = nouNode; } // Ara, moveu el punter del node actual al // nou node creat. currentNode = currentNode->childNode[c - 'a']; } // Incrementa el wordEndCount per a l'últim punter currentNode // això implica que hi ha una cadena que acaba en // currentNode. currentNode->wordEnd = 1; }>>> Complexitat temporal: O(nombre de paraules * maxLengthOfWord) Espai auxiliar: O(nombre de paraules * maxLengthOfWord)
La cerca d'una clau a l'estructura de dades de Trie és similar a la seva operació d'inserció. No obstant això, només compara els personatges i es mou cap avall . La cerca pot finalitzar a causa del final d'una cadena o de la manca de clau a l'assaig. Enfocament pas a pas per a la cerca a l'estructura de dades de Trie: Comenceu al node arrel. Aquest és el punt de partida de totes les cerques dins del Trie. Travessa el Trie en funció dels caràcters de la paraula que cerques. Per a cada personatge, seguiu la branca corresponent al Trie. Si la branca no existeix, la paraula no està present al Trie. Si arribeu al final de la paraula i el senyalador wordEnd s'estableix en 1, la paraula s'ha trobat. Si arribeu al final de la paraula i el senyalador wordEnd és 0, la paraula no està present al Trie, tot i que comparteix un prefix amb una paraula existent. Aquí teniu una representació visual de la paraula cercada pare a l'estructura de dades de Trie: matriu afegint elements java Suposem que hem inserit correctament les paraules i , activat , i pare al nostre Trie, i hem de cercar paraules específiques dins de l'estructura de dades de Trie. Provem de buscar la paraula pare : Operació de cerca a l'estructura de dades de Trie Comencem pel node arrel. Seguim la branca corresponent al caràcter ‘d’. Seguim la branca corresponent al caràcter a’. Seguim la branca corresponent al caràcter ‘d’. Arribem al final de la paraula i final de paraula bandera és 1 . Això significa que pare està present al Trie. A continuació es mostra la implementació de les cadenes de cerca a Trie Data Structure: C++childNode[c - 'a']; } retorn (currentNode->wordEnd == true); }>>> Complexitat temporal: O(nombre de paraules * maxLengthOfWord) Espai auxiliar: O(nombre de paraules * maxLengthOfWord) enter a cadena java
Creeu un node arrel amb l'ajuda de TrieNode() constructor.
Emmagatzema una col·lecció de cadenes que s'han d'inserir a la prova en un vector de cadenes, per exemple, arr .
Inserint totes les cadenes a Trie amb l'ajuda de la insert_key() funció,
Cerca cadenes amb l'ajuda de clau_cerca() funció.

A continuació es mostra la implementació de l'enfocament anterior:

 C++childNode[c - 'a'] = nouNode;  } // Ara, moveu el punter del node actual al // nou node creat.  currentNode = currentNode->childNode[c - 'a'];  } // Incrementa el wordEndCount per a l'últim punter currentNode // això implica que hi ha una cadena que acaba en // currentNode.  currentNode->wordEnd = 1; } bool clau_cerca(TrieNode* arrel, cadena& clau) { // Inicialitzar el punter currentNode // amb el node arrel TrieNode* currentNode = arrel;  // Recorre la longitud de la cadena per a (clau automàtica c :) { // Comproveu si existeix el node per al // caràcter actual del Trie.  if (currentNode->childNode[c - 'a'] == NULL) { // La paraula donada no existeix a Trie retorna fals;  } // Mou el punter currentNode al // node ja existent per al caràcter actual.  currentNode = currentNode->childNode[c - 'a'];  } retorn (currentNode->wordEnd == true); } // Codi del controlador int main() { // Crea un node arrel per a l'arrel Trie TrieNode* = new TrieNode();  // Emmagatzema les cadenes que volem inserir al // vector TrieinputStrings = { 'and', 'ant', 'do', 'geek', 'pare', 'ball'};  // nombre d'operacions d'inserció al Trie int n = inputStrings.size();  per (int i = 0; i< n; i++) {  insert_key(root, inputStrings[i]);  }  // Stores the strings that we want to search in the Trie  vectorsearchQueryStrings = { 'fer', 'friki', 'bat'};  // nombre d'operacions de cerca al Trie int searchQueries = searchQueryStrings.size();  per (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');  }  }  } }>

Python

 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 = ['fer', 'friki', 'bat']; // Cerqueu cada cadena i imprimiu si es troba al Trie searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('La cadena de consulta està present al Trie' } else { console.log('La cadena de consulta no està present al Trie');>>>  
  Sortida      Articles relacionats:     
   Proveu de suprimir  
     Es mostra el contingut de Trie  
     Funció d'emplenament automàtic amb Trie  
  Cerca de patrons utilitzant una prova de tots els sufixos  
     Problemes de pràctica:     
   Descans de paraules mínim 
 Files úniques en una matriu binària 
 Recompte de subcadenes diferents 
 Word Boggle 
 Ordenació de matrius de cadenes (o paraules) amb Trie

TechCodeview

Trie Estructura de dades | Insereix i cerca

`Creeu un node arrel amb l'ajuda de TrieNode() constructor.`