Pregunta de implementación de árbol de prefijo básico

Question

He implementado un árbol de prefijo básico o "trie". El Trie consta de nodos como este:

// pseudo-code
struct node {
    char c;
    collection<node> childnodes;
};

Digamos que agrego las siguientes palabras a mi trie: "Apple", "Ark" y "Cat". Ahora, cuando busco prefijos como "AP" y "CA", el método de mi trie "Bool ContinsPrefix (String Prefix)" volverá correctamente.

Ahora estoy implementando el método "Bool ContenceSwholword (String Word)" que devolverá verdadero para "CAT" y "ARK" pero falso para "Aplicación" (en el ejemplo anterior).

¿Es común que los nodos en un trie tengan algún tipo de bandera de "endofword"? Esto ayudaría a determinar si la cuerda que se busca era en realidad una palabra completa ingresada en el Trie y no solo un prefijo.

¡Salud!

Answer 1

Si necesita almacenar tanto "aplicación" como "Apple", pero no "aplicación", entonces sí, necesita algo como un endOfWord bandera.

Alternativamente, puede colocarlo en su diseño (a veces) teniendo dos nodos con el mismo carácter. Entonces "AP" tiene los nodados de los niños: el nodo de la hoja "P" y un nodo interno "P" con un niño "L".

Answer 2

El final de la clave generalmente se indica a través de un nodo de hoja. O:

• Los nodos infantiles están vacíos; o
• Tienes una rama, con un prefijo de la llave, y algunos nodos para niños.

Su diseño no tiene una hoja/nodo vacío. Intente indicarlo con EG A NULL.