Основной вопрос реализации дерева префикса
-
27-10-2019 - |
Вопрос
Я внедрил основное дерево префикса или «три». Три состоит из узлов, подобных этим:
// pseudo-code
struct node {
char c;
collection<node> childnodes;
};
Скажите, я добавляю следующие слова в свой Trie: «Apple», «Ark» и «Cat». Теперь, когда я просматриваю префиксы, такие как «AP» и «CA» My Trie's «Bool содержит Pprefix (String Prefix)», правильно вернет True.
Теперь я внедряю метод «Bool Canceswholeword (String Word)», который вернет True для «Cat» и «Ark», но False для «App» (в приведенном выше примере).
Обычно у узлов в Trie есть какой -то флаг «Endofword»? Это помогло бы определить, на самом деле было введено целое слово, введенное в Trie, а не просто префикс.
Ваше здоровье!
Решение
Если вам нужно хранить как «приложение», так и «Apple», но не «Appl», то да, вам нужно что -то вроде endOfWord
флаг.
В качестве альтернативы, вы можете вписать его в свой дизайн (иногда), имея два узла с одним и тем же символом. Таким образом, «AP» есть для детей: листовой узел «P» и внутренний узел «P» с ребенком «L».
Другие советы
Конец ключа обычно обозначается через листовой узел. Либо:
- Дочерние узлы пусты; или же
- У вас есть ветка, с одним префиксом ключа и некоторыми детскими узлами.
Ваш дизайн не имеет листового/пустого узла. Попробуйте указать это, например, NULL.