2

我想实现一个 trie 来检查路径的有效性，所以我会通过按目录分解它来构建一个包含所有可能路径结构的树。所以类似的东西/guest/friendsList/search会从根节点到它的 child guest，然后是 guest 的 child friendsList，然后是 friendsList 的 child search。如果搜索是叶节点，那么我的字符串/guest/friendsList/search将被视为有效。

这是一个 trie 有用的东西吗？我见过的所有尝试的实现都处理每个节点上的单个字母，但它们可以是整个字符串吗？特定于这种实现的特里树以及我正在尝试做的只是一个基本树吗？

谢谢！

4

2 回答 2

2

您绝对可以这样做，尽管我通常将其称为目录树而不是 trie，因为您本质上是将文件系统建模为树结构，而不是存储大量不同字符串的前缀。事实上，操作系统在磁盘上可能有一个类似的数据结构来表示文件系统！

于 2017-07-22T17:23:49.123 回答
0

目录树绝对可以做到这一点。首先创建一个根节点，然后将剩余的目录条目作为子节点添加到根节点，依此类推。因此，检查路径名是否有效只是解析整个字符串并遍历目录树。

如果你想让它更快，你可以使用字典来存储一个级别的节点，并且在一个级别中搜索名称是线性的。所以在目录树中搜索路径名需要O(h)，h是目录树的高度。此外，为了防止冗余搜索，跟踪目录树的高度可以优化搜索时间；当解析路径名的长度超过高度时，我们知道我们不需要搜索目录树。

于 2017-07-23T00:34:33.490 回答