Поиск слова в Trie?

У меня есть Trie на Java, и я хочу поиск, если совпадает слово.

Например: Trie: [casa-perro-animal], hogar = false; casa = true;

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

И три класса с узлом:

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

Есть помощь? Я испанец. Большое спасибо.

1 ответ

  1. Вы смотрите на реализацию дерева двойной цепи Трие:

    изображение и описание из статьи Википедии на Trie

    Двойная цепная реализация дерева Trie

    Вертикальные стрелки являются дочерними указателями, пунктирные горизонтальные стрелки-следующими указателями. Набор строк, хранящихся в этом trie{baby, bad, bank, box, dad, dance}. Списки сортируются для прохождения в лексикографическом порядке

    Как искать его

    Ваш поиск должен потреблять символы по одному из искомых wordи перемещаться по три.

    Возьмите первый символ и проверьте, содержит ли его ваш корень. Если да, то вы можете перейти к следующему символу В wordи вниз по сплошной стрелке к следующему узлу текущего списка — в вашей реализации это nextузел типа Info. Таким образом, вы проходите по одному и тому же списку вниз (согласно приведенной выше схеме).

    Если текущий узел не содержит символ, который вы ищете, вы перемещаетесь по горизонтали к следующему альтернативному списку (вдоль пунктирных линий). В вашем случае это представлено alt Infoузлом. И вы повторяете тест для той же буквы там. Если не удается, перейдите к следующему альтернативному списку снова.

    Если вы проверили все альтернативные списки на данном уровне без какого-либо соответствия, и столкнулись с тупиком (где alt == null), вы можете сделать вывод, что wordне содержится в вашей трие .

    И наоборот, если вы потребили все символы из wordи находятся на последнем узле в списке (т. е.next == null), то вы можете сделать вывод, что wordхранится в trie .