基于数组的 Trie 实现。子数组中的非空值

Question

我试图从 http://www.programcreek.com/2014/05/leetcode-implement-trie-prefix-tree-java/ 中了解 Trie 的基于数组的实现（参见 Java 解决方案 2 - 使用数组提高性能）。

public void insert(String word) {
    TrieNode p = root;
    for(int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        int index = c - 'a';
        if(p.arr[index] == null) {
            TrieNode temp = new TrieNode();
            p.arr[index] = temp;
            p = temp;
        } else {
            p = p.arr[index];
        }
    }
    p.isEnd = true;
}

我不确定是否执行过 else 分支。我错过了什么？

更新 1

给定的单词只包含小写英文字母

Answer 1

在我看来这很像一个错误。如果 c-'a'>26 那么 p.arr[index] 不会为 null 但会引发 ArrayIndexOutOfBounds 异常。

Answer 2

第一次调用这个函数，else分支确实不会执行。但是，随着 Trie 的填充，p.arr[index] 很可能不为空。

例如，调用 insert("i") 将导致在 root.arr['i' - 'a'] 处添加一个新的 TrieNode。第二次调用该函数，例如使用 insert("it")，将导致检查 p.arr[index] == null 返回 false，因为第一次插入已经在根节点为 i 添加了 TrieNode .

您可以使用以下主要函数对此进行测试（并在 else 分支中放置一个断点或 println 语句）

public static void main (String[] args)
{
    Trie t = new Trie();
    t.insert("i");
    t.insert("it");
}

基于数组的 Trie 实现。子数组中的非空值

Array-based Trie Implementation. Non-null value in the child array

java

trie

data-structures