时间戳

首页 > 解决方案 > 从 Vec 构建一个 UrlTree

algorithm - 从 Vec 构建一个 UrlTree

问题描述

我需要制作 url 树结构，如站点地图。输入：Vec - url 列表预期输出：具有嵌套层次结构的 url，从根到端点。

它已经存在板条箱还是我需要自己制作？

输入：

{
   "https://exapmle.com",
   "https://exapmle.com/aa",
   "https://exapmle.com/ab",
   "https://exapmle.com/v",
   "https://exapmle.com/zac",
   "https://exapmle.com/zac/acf",
   "https://exapmle.com/zac/acf/adr",
   "https://exapmle.com/zac/axx"
}

输出：

UrlTree {
    root: "https://exapmle.com",
    Nodes: {
        {
            node: "aa",
            Nodes: None,
        },
        {
            node: "ab",
            Nodes: None,
        },
        {
            node: "v",
            Nodes: None,
        },
        {
            node: "zac",
            Nodes: {
                       {
                            node: "acf",
                            Nodes: {
                                       node: "adr",
                                       Nodes: None,
                                   }   
                       },
                       {
                            node: "axx",
                            Nodes: None,
                       }
                   }
        }
    }
}

标签： algorithmwebstructrusttree

解决方案

我认为您将不得不自己编写一些代码。虽然您可以使用 Sven Marnach 提到的 radix trie，但您会遇到问题，它可能会在文件夹名称上拆分，而不仅仅是 /。Abc/df 和 abd/df 将保存为 (an, c/df, d/df)。

自己做一些事情，你必须问，你的输入大小有多大，长度或你的 vec，你的代码需要有多高的性能？

如果性能不是那么大的问题，那么就会找到一个 vec 的 struts。在每次插入时，只需检查当前文件夹是否已经在哈希图中并添加或向下一步。构建结构后，将其映射到所需的输出。

如果你需要一些高性能的东西，你可以实现像基数特里一样的东西，这个结构实现起来并不难，因为你只需要关心在“/”上的拆分​​，你可以以此为灵感https://www.cs.usfca。 edu/~galles/visualization/RadixTree.html。

推荐阅读