Presentamos y discutimos una implementación en la publicación a continuación.
prueba | (Insertar y buscar) – GeeksforGeeks
La implementación utilizada en la publicación anterior utiliza una array de tamaño alfabético con cada Node. Se puede hacer eficiente en memoria. Una forma de implementar Trie es un conjunto de Nodes vinculados, donde cada Node contiene una array de punteros secundarios, uno para cada símbolo del alfabeto. Esto no es eficiente en términos de tiempo ya que no podemos encontrar rápidamente a un niño en particular.
La forma eficiente es una implementación en la que usamos un mapa hash para almacenar elementos secundarios de un Node. Ahora asignamos memoria solo para alfabetos en uso y no desperdiciamos espacio almacenando punteros nulos.
// A memory optimized CPP implementation of trie
// using unordered_map
#include <iostream>
#include <unordered_map>
using namespace std;
struct Trie {
// isEndOfWord is true if the node
// represents end of a word
bool isEndOfWord;
/* nodes store a map to child node */
unordered_map<char, Trie*> map;
};
/*function to make a new trie*/
Trie* getNewTrieNode()
{
Trie* node = new Trie;
node->isEndOfWord = false;
return node;
}
/*function to insert in trie*/
void insert(Trie*& root, const string& str)
{
if (root == nullptr)
root = getNewTrieNode();
Trie* temp = root;
for (int i = 0; i < str.length(); i++) {
char x = str[i];
/* make a new node if there is no path */
if (temp->map.find(x) == temp->map.end())
temp->map[x] = getNewTrieNode();
temp = temp->map[x];
}
temp->isEndOfWord = true;
}
/*function to search in trie*/
bool search(Trie* root, const string& str)
{
/*return false if Trie is empty*/
if (root == nullptr)
return false;
Trie* temp = root;
for (int i = 0; i < str.length(); i++) {
/* go to next node*/
temp = temp->map[str[i]];
if (temp == nullptr)
return false;
}
return temp->isEndOfWord;
}
/*Driver function*/
int main()
{
Trie* root = nullptr;
insert(root, "geeks");
cout << search(root, "geeks") << " ";
insert(root, "for");
cout << search(root, "for") << " ";
cout << search(root, "geekk") << " ";
insert(root, "gee");
cout << search(root, "gee") << " ";
insert(root, "science");
cout << search(root, "science") << endl;
return 0;
}
Producción:
1 1 0 1 1
El espacio utilizado aquí con cada Node aquí es proporcional al número de niños, lo cual es mucho mejor que proporcional al tamaño del alfabeto, especialmente si el alfabeto es grande.
Este artículo es una contribución de Pranav . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA