Могу ли я использовать trie, в котором на каждом узле есть целое слово?

Я хочу реализовать попытку проверки правильности путей, поэтому я бы построил дерево, содержащее все возможные конструкции путей, разбив их по каталогам. Таким образом, что-то вроде /guest/friendsList/search будет идти от корневого узла к его дочернему элементу guest, затем к дочернему элементу гостя friendsList, а затем к дочернему элементу списка друзей search. Если поиск является конечным узлом, моя строка /guest/friendsList/search будет считаться действительной.

Это то, для чего было бы полезно попробовать. Все реализации try, которые я видел, имеют дело с отдельными буквами в каждом узле, но могут ли они быть целыми строками? Является ли trie специфичным для такого рода реализации, и то, что я пытаюсь сделать, это просто базовое дерево?

Спасибо!


algorithm tree trie graph-algorithm prefix-tree
person zulusam    schedule 22.07.2017    source источник
comment
С отдельными буквами у вас есть массив дочерних указателей фиксированного размера. С произвольными строками в качестве дочерних элементов вы получаете связанные списки, в которых каждый узел имеет ссылку на одноранговый узел, и связанный список дочерних элементов. Это похоже на trie, но не совсем на trie.   -  person user3386109    schedule 22.07.2017
comment
Разве это не просто то, что большинство людей назвало бы деревом каталогов?   -  person biziclop    schedule 22.07.2017
comment
@user3386109 user3386109 разве это не раздражающая реализация? Я бы просто поместил хэш-карту в каждый узел   -  person harold    schedule 22.07.2017

Ответы (2)


arrow_upward
2
arrow_downward

Вы можете сделать это абсолютно точно, хотя я обычно называю это деревом каталогов, а не тройкой, поскольку вы, по сути, моделируете файловую систему как древовидную структуру, а не храните множество префиксов разных строк. Фактически, ОС, вероятно, имеет аналогичную структуру данных на диске для представления файловой системы!

person templatetypedef    schedule 22.07.2017

arrow_upward
0
arrow_downward

Дерево каталогов определенно может это сделать. Сначала создайте корневой узел, а затем добавьте оставшиеся записи каталога в корневой узел в качестве дочерних элементов и т. д. Таким образом, проверка правильности имени пути — это просто анализ всей строки и просмотр дерева каталогов.

Если вы хотите сделать это быстрее, вы можете использовать словарь для хранения уровня узлов, а поиск имени выполняется линейно на одном уровне. Таким образом, поиск имени пути в дереве каталогов занимает O(h), а h — это высота дерева каталогов. Кроме того, для предотвращения избыточного поиска отслеживание высоты дерева каталогов может оптимизировать время поиска; когда длина проанализированного имени пути превышает высоту, мы знаем, что нам не нужно искать дерево каталогов.

person sereneL    schedule 23.07.2017