El Pruebe la estructura de datos es una estructura de datos en forma de árbol que se utiliza para almacenar un conjunto dinámico de cadenas. Se utiliza comúnmente para eficiente recuperación y almacenamiento de claves en un gran conjunto de datos. La estructura soporta operaciones como inserción , buscar , y supresión de claves, lo que la convierte en una herramienta valiosa en campos como la informática y la recuperación de información. En este artículo vamos a explorar inserción y búsqueda operación en la estructura de datos Trie.
Pruebe la estructura de datos
Tabla de contenidos
- Representación del nodo Trie
- Representación del nodo Trie:
A Pruebe la estructura de datos Consta de nodos conectados por aristas. Cada nodo representa un carácter o una parte de una cadena. El nodo raíz, el punto de partida de Trie, representa una cadena vacía. Cada borde que emana de un nodo significa un carácter específico. La ruta desde la raíz hasta un nodo representa el prefijo de una cadena almacenada en Trie.
Una estructura sencilla para representar nodos del alfabeto inglés puede ser la siguiente.
regexp_like en mysql
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; } } };>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; } } }>Repasemos el proceso de insertar palabras en una estructura de datos Trie. Ya hemos cubierto los conceptos básicos de Trie y su estructura de nodos.
algoritmo knn
Aquí hay una representación visual de cómo insertar las palabras. y y en en una estructura de datos Trie:
Insertar operación en la estructura de datos Trie
Insertando y en la estructura de datos Trie:
tutorial ssis
- Comience en el nodo raíz: El nodo raíz no tiene ningún carácter asociado y su final de palabra el valor es 0 , lo que indica que no hay ninguna palabra completa que termine en este punto.
- Primer personaje a: Calcule el índice usando ' a'-'a' = 0 . Compruebe si el nodoniño[0] es nulo . Ya que es así, crea un nuevo TrieNode con el personaje. a , final de palabra ajustado a 0 y una matriz vacía de punteros. Muévete a este nuevo nodo.
- Segundo carácter n: Calcule el índice usando ‘n’ – ‘a’ = 13 . Comprobar si nodohijo[13] es nulo . Lo es, así que crea un nuevo TrieNode con el personaje. norte , final de palabra ajustado a 0 y una matriz vacía de punteros. Muévete a este nuevo nodo.
- Tercer carácter d: Calcule el índice usando ' d’ – ‘a’ = 3 . Comprobar si niñoNodo[3 ] es nulo . Lo es, así que crea un nuevo TrieNode con el personaje. d , final de palabra ajustado a 1 (indicando la palabra y termina aquí).
Insertando hormiga en la estructura de datos Trie:
- Comience en el nodo raíz: El nodo raíz no contiene ningún dato, pero realiza un seguimiento de cada primer carácter de cada cadena que se ha insertado.
- Primer personaje a: Calcule el índice usando ' a'-'a' = 0 . Compruebe si el nodoniño[0] es nulo . ya tenemos el a nodo creado a partir de la inserción anterior. así que pasa a lo existente a nodo.
- Primer carácter n: Calcule el índice usando ' n' – 'a' = 13 . Comprobar si nodoniño [13] es nulo . No lo es, así que pasa a lo existente. norte nodo.
- Segundo carácter t: Calcule el índice usando ‘t’ – ‘a’ = 19 . Comprobar si nodoniño [19] es nulo . Lo es, así que crea un nuevo TrieNode con el personaje. t , final de palabra ajustado a 1 (indicando que aquí termina la palabra hormiga).
A continuación se muestra la implementación de la inserción de cadenas en la estructura de datos 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 nodo para el carácter actual no existe // entonces crea un nuevo nodo TrieNode* newNode = new TrieNode(); // Mantenga la referencia para el // nodo recién creado. NodoActual->NodoNiño[c - 'a'] = NuevoNodo; } // Ahora, mueva el puntero del nodo actual al // nodo recién creado. NodoActual = NodoActual->NodoNiño[c - 'a']; } // Incrementa wordEndCount para el último // puntero currentNode, esto implica que hay una cadena que termina en // currentNode. nodoactual->findepalabra = 1; }>Complejidad del tiempo: O(número de palabras * maxLengthOfWord)
Espacio Auxiliar: O(número de palabras * maxLengthOfWord)Buscar una clave en la estructura de datos Trie es similar a su operación de inserción. Sin embargo, sólo compara los personajes y baja . La búsqueda puede finalizar debido al final de una cadena o falta de clave en el trie.
Enfoque paso a paso para buscar en la estructura Trie Data:
- Comience en el nodo raíz. Este es el punto de partida de todas las búsquedas dentro del Trie.
- Recorre el Trie según los caracteres de la palabra que estás buscando. Para cada personaje, sigue la rama correspondiente en el Trie. Si la rama no existe, la palabra no está presente en el Trie.
- Si llega al final de la palabra y el indicador wordEnd está establecido en 1, se ha encontrado la palabra.
- Si llega al final de la palabra y el indicador wordEnd es 0, la palabra no está presente en Trie, aunque comparta un prefijo con una palabra existente.
Aquí hay una representación visual de la palabra de búsqueda. papá en la estructura de datos Trie:
declaración if-else java
Supongamos que hemos insertado correctamente las palabras y , en , y papá en nuestro Trie, y tenemos que buscar palabras específicas dentro de la estructura de datos de Trie. Intentemos buscar la palabra. papá :
Operación de búsqueda en la estructura de datos Trie
- Comenzamos en el nodo raíz.
- Seguimos la rama correspondiente al carácter 'd'.
- Seguimos la rama correspondiente al carácter a’.
- Seguimos la rama correspondiente al carácter 'd'.
- Llegamos al final de la palabra y final de palabra la bandera es 1 . Esto significa que papá está presente en el Trie.
A continuación se muestra la implementación de la búsqueda de cadenas en 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 palabra dada no existe en Trie return false; } // Mueve el puntero del NodoActual al // nodo ya existente para el carácter actual. NodoActual = NodoActual->NodoNiño[c - 'a']; } return (currentNode->wordEnd == verdadero); }>Complejidad del tiempo: O(número de palabras * maxLengthOfWord)
Espacio Auxiliar: O(número de palabras * maxLengthOfWord)entero a cadena java
Cree un nodo raíz con la ayuda de TrieNodo() constructor.
- Almacene una colección de cadenas que deben insertarse en el trie en un vector de cadenas, digamos, llegar .
- Insertando todas las cadenas en Trie con la ayuda del insertar_clave() función,
- Buscar cadenas con la ayuda de clave de búsqueda() función.
A continuación se muestra la implementación del enfoque anterior:
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 nodo para el carácter actual no existe // entonces crea un nuevo nodo TrieNode* newNode = new TrieNode(); // Mantenga la referencia para el // nodo recién creado. NodoActual->NodoNiño[c - 'a'] = NuevoNodo; } // Ahora, mueva el puntero del nodo actual al // nodo recién creado. NodoActual = NodoActual->NodoNiño[c - 'a']; } // Incrementa wordEndCount para el último // puntero currentNode, esto implica que hay una cadena que termina en // currentNode. nodoactual->findepalabra = 1; } bool search_key(TrieNode* root, string& key) { // Inicializa el puntero del nodo actual // con el nodo raíz TrieNode* currentNode = root; // Iterar a lo largo de la longitud de la cadena for (auto c: key) { // Comprobar si el nodo existe para el // carácter actual en Trie. if (currentNode->childNode[c - 'a'] == NULL) { // La palabra dada no existe en Trie return false; } // Mueve el puntero del NodoActual al // nodo ya existente para el carácter actual. NodoActual = NodoActual->NodoNiño[c - 'a']; } return (currentNode->wordEnd == verdadero); } // Código del controlador int main() { // Crea un nodo raíz para Trie TrieNode* root = new TrieNode(); // Almacena las cadenas que queremos insertar en el // vector TrieinputStrings = { 'y', 'hormiga', 'hacer', 'geek', 'papá', 'bola' }; // número de operaciones de inserción en Trie int n = inputStrings.size(); para (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' }; // número de operaciones de búsqueda en Trie int searchQueries = searchQueryStrings.size(); para (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'); } } } }> Pitón 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(cadena)); const searchQueryStrings = ['do', 'geek', 'bat']; // Busca cada cadena e imprime si se encuentra en el Trie searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('La cadena de consulta está presente en el Trie'); } else { console.log('La cadena de consulta no está presente en el Trie');> Producción
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>
Intenta eliminar
Problemas de práctica:
- Salto mínimo de palabra
- Filas únicas en una matriz binaria
- Recuento de subcadenas distintas
- Palabra alucinante
- Ordenar una matriz de cadenas (o palabras) usando Trie