Структура данных Trie: как предотвратить ложные срабатывания при поиске слова?

class Node{  
 Map<Character,Node> childMap = new HashMap<>();
 boolean isWord;
}

Узел данных trie обычно представлен в виде вышеуказанного класса. Предположим, что мы вставили

  • "Плохо"
  • "родитель"

в trie.
Если в trie выполняется поиск "pad", не будет ли он возвращать "true", что неверно?


data-structures trie recursive-datastructures
person user1422163    schedule 02.10.2017    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Нет, это не вернет true. Если да, то либо в вашем коде есть ошибка, либо вы не понимаете концепцию trie.

Если вы вставите «плохой» и «родительский», то дерево будет выглядеть так:

(root)->b->a->d
  |  
  +---->p->a->r->e->n->t

"подушка" не будет найдена

person user31264    schedule 02.10.2017

arrow_upward
0
arrow_downward

Не совсем. Trie обычно реализуется с использованием рекурсивной структуры (составной шаблон), как вы правильно указали. Однако именно это помешало бы ему вернуть true для «pad», поскольку после вставки «parent» структура будет выглядеть так:

root
    b
        a
            d
    p
        a
            r
                e
                    n
                        t

Таким образом, следуя за Trie, все, что начинается с «p», никогда не будет и на «d».

Однако в реализациях Trie часто возникает еще одна проблема, которая требует последнего шага, чтобы выяснить, действительно ли вы нашли полное слово или только префикс. Именно для этого в вашем примере предназначена переменная isWord. Итак, после повторения узлов вы должны проверить это свойство.

person dnickless    schedule 02.10.2017