algorithm - 从路径列表创建树的算法

Question

任务是从排序路径列表中创建一棵树。每个节点都是一个文件系统对象(文件或文件夹)。
目前我正在使用这个(伪代码):

foreach(string path in pathList)
{
    INode currentNode = rootNode;
    StringCollection pathTokens = path.split(pathSplitter);
    foreach(pathToken in pathTokens)
    {
        if (currentNode.Children.contains(pathToken ))
        {
            currentNode = currentNode.Children.find(pathToken);
        }
        else 
        {
            currentNode  = currentNode.Children.Add(pathToken);
        }
    }
 }

pathSplitter 对于 win 是 \，对于 *nix 是 /。
有没有更有效的方法来解决该任务？

Answer 1

输入数据的关键质量是路径列表已排序。因此，您可以非常有效地使用当前节点和先前节点之间的公共(public)前缀。您可以做的是维护树数据结构中从根到叶文件夹节点的最后跟踪。然后，对于当前路径，您只需遍历之前的跟踪(即相对于最后一条路径处理当前路径)，而不是一次又一次地在树中查找正确的位置。

比较上一个路径和当前路径时，可能会发生三种情况:

1)相同的路径

\path\to\folder\file1.txt
\path\to\folder\file2.txt

跟踪仍然存在，file2.txt 的节点已添加。

2) 新路径是子路径

\path\to\folder\file1.txt
\path\to\folder\subfolder\file2.txt

添加了子文件夹和file2.txt的节点。

3)新路径不同

\path\to\folder\file1.txt
\path\to\another_folder\subfolder\file2.txt

首先，您需要回溯跟踪来表示 \path\to\。然后，添加 another_path、subfolder 和 file2.txt 的节点。 (请注意，another_folder\subfolder\ 部分可能完全丢失 - 我希望它是清楚的。)

根据整体特征和数据量，这种算法可能会执行得更快。您可以使用一些正式的 Big-O 估计，但我认为测试它会更快。