在 Trie 中搜索词？

Question

我在 Java 中有一个 Trie，我想搜索是否包含一个词。

例如：特里树：[casa-perro-animal]，hogar = false；卡萨=真；

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

还有 class 节点的 Trie：

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

有什么帮助吗？我是西班牙人。非常感谢。

Answer 1

您正在查看 Trie 的 doubly chained tree 实现：
_{image and description from wikipedia's entry on Trie}

_{垂直箭头是子指针，水平虚线箭头是下一个指针。此 trie 中存储的字符串集是 {baby, bad, bank, box, dad, dance}。列表已排序以允许按字典顺序遍历}

如何搜索

您的搜索必须一个接一个地使用搜索到的字符 word 并导航 trie。

取第一个字符并检查您的根是否包含它。如果是，您可以移动到 word 中的下一个字符，然后沿着实线箭头向下移动到当前 list 的下一个节点 - 在您的实现中它是 next 类型 Info 的节点。这样你就在同一个 list 中向下遍历（根据上图）。

如果当前节点不包含您要搜索的字符，则水平移动到下一个备选 list（沿着虚线）。在您的情况下，这由 alt Info 节点表示。然后你在那里重复测试同一个字母。如果运气不好，请再次转到下一个备选列表。

如果您检查了给定级别的所有替代列表，但没有任何匹配项，并且面临死胡同（其中 alt == null），您可以得出结论word 不包含在您的 trie 中。

相反，如果您已经使用了 word 中的所有字符并且位于 list 中的最后一个节点（即 next == null），那么您可以得出结论，word 存储在 trie.

中

在 Trie 中搜索词？

Search word in Trie?

java

trie

如何搜索