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

Я реализовал базовое дерево префиксов или "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"? Это поможет определить, является ли искомая строка фактически целым словом, введенным в три, а не просто префиксом.

Ура!

Источник

2 ответа

Решение

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

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

Источник

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

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

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

Источник
Другие вопросы по тегам