Как оптимизировать построение дерева из списка путей узлов?

Question

Предположим, я пишу функцию fromPaths(paths: List[String]): Node для построения дерева из нескольких путей к узлам, например:

case class Node(value: String, children: List[Node])
val paths = List("a/b/x", "a/b/y", "a/c", "a/c/d")
fromPaths(paths) // Node("a", List(Node("b", List(Node("x"), Node("y"))), Node("c", List(Node("d")))))

Я могу написать функцию addNode(root: Node, path: String): Node, а затем просто fold по списку. Однако это выглядит неоптимально, поскольку мы пересекаем дерево от root до node для каждого "пути" в paths.

Как бы вы оптимизировали fromPaths для общего числа пройденных узлов?

Answer 1

Кажется, что очевидная рекурсия работает нормально, по крайней мере, на ваших примерах:

case class Node[A](a: A, children: List[Node[A]])
def trieForest[A](lists: List[List[A]]): List[Node[A]] = {
  lists.filter(_.nonEmpty).groupBy(_.head).map { 
    case (k, vs) =>
    Node(k, trieForest(vs.map(_.tail)))
  }.toList
}

def fromPaths(paths: List[String]): Node[String] = {
  // assumes that there is only one tree in the 
  // top-level forest.
  trieForest(paths.map(_.split("/").toList)).head
}

println(fromPaths(List("a/b/x", "a/b/y", "a/c", "a/c/d")))

Печать (с отступом):

Node(a, List(
  Node(b,List(
    Node(y,List()), 
    Node(x,List())
  )),
  Node(c,List(
    Node(d,List())
  ))
))

Он не может работать намного быстрее асимптотически, потому что вы должны смотреть на каждую часть ввода хотя бы один раз.