3

I want to implement a trie to check for the validity of paths, so I would have a tree built that contains all the possible path constructions by breaking it down by directory. So something like /guest/friendsList/search would go from the root node to it's child guest, then guest's child friendsList, and then friendsList's child search. If search is a leaf node then my string /guest/friendsList/search would be considered valid.

Is this something a trie would be useful for. All the implementations of tries I've seen deal with individual letters at each node, but can they be whole strings instead? Is a trie specific to this kind of implementation and what I'm trying to do just a basic tree?

Thanks!

zulusam
  • 185
  • 1
  • 8
  • 1
    With individual letters, you have a fixed-size array of child pointers. With arbitrary strings as children, you end up with linked lists where each node has a link to a peer, and a linked list of children. That's similar to a trie, but not really a trie. – user3386109 Jul 22 '17 at 17:23
  • Isn't this simply what most people would call a directory tree? – biziclop Jul 22 '17 at 17:25
  • @user3386109 isn't that an annoying implementation though? I'd just put a hashmap in every node – harold Jul 22 '17 at 17:26

2 Answers2

2

You can absolutely do this, though I'd typically call this a directory tree rather than a trie since you're essentially modeling the file system as a tree structure rather than storing lots of prefixes of different strings. In fact, the OS probably has a similar data structure on disk for representing the file system!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
0

The directory tree can definitely do that. Creating a root node at first and then adding remaining directory entries to the root node as children, and so on. So checking if a path name is valid is just parsing the whole string and going through the directory tree.

If you want to make it faster, you can use a dictionary to store a level of nodes and searching a name is linear in one level. So searching a path name in the directory tree takes O(h), and h is the height of the directory tree. Further, to prevent redundant searching, keeping track of height of the directory tree can optimize the searching time; when the length of parsed path name exceeds the height, we know we do not need to search the directory tree.

sereneL
  • 15
  • 4