Estructura de datos de prueba con implementación

¿Ha visto palabras de AutoSuggestions / Auto Complete mientras buscaba según el prefijo de la cadena? Como a continuación:


Estas sugerencias también son realmente rápidas y eficientes .

¿Sabes cómo surgieron estas sugerencias? ¿Con qué estructura de datos podemos hacerlo eficiente y rápido?

La mayoría de nosotros creemos que indexar la columna / clave resolverá este problema. Los grandes sistemas con grandes conjuntos de datos no solo pueden confiar en esto.

La mejor estructura de datos que se puede utilizar para este problema es 0000-Trie”

¿Qué es la estructura de datos de Trie?

¿Cuál será el número máximo de nodos desde la raíz?

Si con s identificamos solo caracteres alfabéticos, entonces el máximo de nodos secundarios desde la raíz solo es 26 (a-z).

Si también consideramos los números, podemos pensar que el número será 36 (a-z + 0–9) – No se usa generalmente.

¿Por qué considerar Trie si ya tenemos conjuntos y HashMaps?

Con conjuntos y mapas hash, la complejidad del tiempo no es eficiente. Además, con Hash Maps también debemos considerar las colisiones hash. En comparación, para buscar / insertar Trie , la complejidad de tiempo es O (P) donde P es la longitud de la cadena de prefijo.

Implementación de Trie:

Hasta ahora hemos pasado solo por la parte teórica. Creemos una estructura de prueba de muestra y podremos digerir todo lo que discutimos:

Tome un sistema de empleados con una lista de nombres que contenga: [“rahul”, “raju”, “rishabh”, “radhe”, “rockey”].

Representación del conjunto de datos anterior con Trie:

En la instantánea anterior, podemos ver que r está en el nodo raíz y todas las rutas posteriores que hemos dibujado.

Ahora intente encontrar todas las palabras que comiencen con el prefijo “ra”. Vea cómo funciona:

Ahora considere establecer un prefijo con diferentes palabras como [“rahul”, “raju”, “rishabh”, “radhe”, “rockey”, “javascript”, “trie”].

De acuerdo con nuestro enfoque, necesitamos crear Trie separado para cada prefijo. Entonces ese enfoque no es completamente correcto.

El enfoque correcto es tener un elemento nulo en la raíz y luego agregar elementos posteriores en el árbol. Si no existe, cree uno nuevo y adjúntelo a la raíz.

Pruebe el código para insertar, sugerir automáticamente y comprobar si existe una palabra:

Nota: algunas aplicaciones utilizan Trie con algunas modificaciones, como clasificar las palabras más buscadas. Según la clasificación, devolveremos las sugerencias de búsqueda más comunes en caso de algunas sugerencias limitadas.

Aplicaciones de Trie:

El código está disponible en: https://github.com/rishabhjj/Datastructure_Algorithm/blob/master/LinkedList/Geeks/Trie.js

En caso de cualquier consulta o sugerencia, por favor conéctese conmigo o envíe un correo electrónico a @ rishabh171192 @ gmail.com