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)前缀。您可以做的是维护树数据结构的最后一个trace，从它的根叶文件夹节点开始。然后对于当前路径你只是遍历之前的轨迹(即相对于最后一条路径处理当前路径)而不是一次又一次地在树中找到正确的位置。

比较上次路径和当前路径时，可能会出现三种情况:

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

添加了subfolder 和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 估计，但我认为只测试它会更快。