Estoy usando trie por primera vez. Quería saber cuál es la mejor estructura de datos para usar durante un tiempo mientras decido cuál es la siguiente rama que se supone que atraviesa. Estaba buscando entre una matriz, un hashmap y una lista vinculada.Qué estructura de datos de nodo usar para un trie
Cada una de estas opciones tiene sus ventajas y desventajas.
Si almacena los nodos secundarios en una matriz, puede buscar qué niño visitar de manera extremadamente eficiente indexando la matriz. Sin embargo, el uso de espacio por nodo será alto: O (| Σ |), donde Σ es el conjunto de letras con el que pueden formarse sus palabras, incluso si la mayoría de esos elementos secundarios son nulos.
Si almacena los nodos secundarios en una lista vinculada, entonces el tiempo requerido para encontrar un hijo será O (| Σ |), ya que es posible que necesite escanear todos los nodos de la lista vinculada para encontrar el niño que quieres. Por otro lado, la eficiencia del espacio será bastante buena, ya que solo almacenas los niños que estás usando. También podría considerar el uso de una matriz de tamaño fijo aquí, que tiene un uso de espacio aún mejor pero conduce a inserciones y eliminaciones muy costosas.
Si almacena los nodos secundarios en una tabla hash, el tiempo (esperado) para encontrar un hijo será O (1) y el uso de memoria será proporcional (aproximadamente) al número de hijos que tenga. Curiosamente, como usted sabe de antemano qué valores va a ser hashing, podría considerar usar un dynamic perfect hash table para garantizar las búsquedas O (1) en el peor de los casos, a expensas de alguna precomputación.
Otra opción sería almacenar los nodos secundarios en un árbol de búsqueda binario. Esto da lugar a la estructura de datos ternary search tree. Esta opción se encuentra entre las opciones de tabla vinculada y hash: el uso del espacio es bajo y puede realizar consultas predecesoras y sucesoras de manera eficiente, pero hay un ligero aumento en el costo de realizar una búsqueda debido al costo de búsqueda en la BST. Si tiene un trie estático donde las inserciones nunca ocurren, puede considerar usar weight-balanced trees como las BST en cada punto; esto proporciona un tiempo de ejecución excelente para las búsquedas (O (n + log k), donde n es la longitud de la cadena que se busca yk es el número total de palabras en el trie).
En resumen, las búsquedas de matriz son más rápidas pero su uso de espacio en el peor de los casos es el peor. Una matriz de tamaño estático tiene el mejor uso de memoria pero inserciones y eliminaciones costosas. La tabla hash tiene búsquedas decentemente rápidas y un buen uso de memoria (en promedio). Los árboles binarios de búsqueda están en algún lugar en el medio. Yo sugeriría usar la tabla hash aquí, aunque si le da más espacio y no le importan los tiempos de búsqueda, la lista enlazada podría ser mejor. Además, si su alfabeto es pequeño (digamos que está haciendo un trie binario), la sobrecarga de la matriz no será tan mala y es posible que desee usar eso.
Espero que esto ayude!
Si está intentando construir trie solo para alfabetos, le sugiero que use array y luego use el árbol de particia (espacio optimizado trie). http://en.wikipedia.org/wiki/Radix_tree
Esto le permitirá realizar búsquedas rápidas con arreglo y no perder demasiado espacio si el factor de bifurcación de determinado nodo es bajo.
para intentos binarios que en realidad puede hacer (mucho) mejor que arrays de 2 elementos – harold
@ harold- Buen punto. En un lenguaje como C o C++ no hay diferencia de espacio entre una matriz de dos elementos y solo tiene dos punteros, aunque en lenguajes como Java o Python tienes toda la razón. – templatetypedef
Bueno, eso es todo, pero puedes hacerlo mejor que eso, con algunos trucos que te permiten omitir los ceros a la izquierda de la tecla y saltar directamente al nodo correspondiente a cero cero muchos – harold