Search word in Trie?

Question

I have a Trie in Java, and I want search if cointains a word.

For example: Trie: [casa-perro-animal], hogar = false; casa = true;

public boolean search (String word){
    /**Method to complete**/
}

And the class Trie with Node:

public class Trie {
/**
 * Clase auxiliar para guardar caracteres que forman parte de una palabra
 * @author zenon
 */
protected class Info {
    char c;    // Caracter actual
    Info alt;  // Caracter alternativo para la misma posición
    Info next; // Caracter que es la primera opción en la siguiente posición

    public Info(char c, Info alt, Info next) {
        this.c = c;
        this.alt = alt;
        this.next = next;
    }
}

protected Info root; // Referencia al punto de inicio de la estructura

Any help? I am spanish. Thank you very much.

Answer 1

You are looking at doubly chained tree implementation of Trie:
_{image and description from wikipedia's entry on Trie}

_{Vertical arrows are child pointers, dashed horizontal arrows are next pointers. The set of strings stored in this trie is {baby, bad, bank, box, dad, dance}. The lists are sorted to allow traversal in lexicographic order}

How to search it

Your search has to consume the characters one by one of the searched word and navigate the trie.

Take the first character and check whether your root contains it. If yes, you can move to next character in the word and down along the solid arrow to the next node of the current list - in your implementation it's the next node of type Info. This way you are traversing within the same list downwards (according to the diagram above).

If the current node does not contain the character you are searching for, you move horizontally across to the next alternative list (along the dotted lines). In your case this is represented by the alt Info node. And you repeat the test for the same letter there. If no luck, move to the next alternative list again.

If you have checked all alternative lists at a given level without any match, and are facing a dead end (where alt == null), you can conclude that the word is not contained within your trie.

Conversely if you have consumed all characters from the word and are at the last node within a list (i.e. next == null), then you can conclude that the word is stored within the trie.