Основной вопрос реализации дерева префиксов

Question

Я реализовал базовое дерево префиксов или "Trie". Три состоит из таких узлов:

// pseudo-code
struct node {
    char c;
    collection<node> childnodes;
};

Скажите, что я добавил следующие слова в свой список: "Яблоко", "Ковчег" и "Кошка". Теперь, когда я смотрю префиксы типа «Ap» и «Ca», мой метод «bool containsPrefix (string prefix)» моего trie корректно вернет true.

Теперь я реализую метод "bool containsWholeWord (string word)", который будет возвращать true для "Cat" и "Ark", но false для "App" (в приведенном выше примере).

Обычно узлы в дереве имеют какой-то флаг "endOfWord"? Это поможет определить, была ли искомая строка целым словом, введенным в дерево, а не просто префикс.

Ура!

Answer 1

Конец ключа обычно указывается через листовой узел.Либо:

• дочерние узлы пусты;или
• у вас есть ветвь с одним префиксом ключа и несколькими дочерними узлами.

В вашем дизайне нет листа / пустого узла.Попробуйте указать это, например, нулевым.

Answer 2

Если вам нужно хранить «App» и «Apple», но не «Appl», тогда да, вам нужно что-то вроде endOfWord flag.

В качестве альтернативы, вы можете встроить его в свой дизайн (иногда), имея два узла с одинаковым символом. Таким образом, «Ap» имеет дочерние узлы: конечный узел «p» и внутренний узел «p» с дочерним узлом «l».