Scala:具有复杂结构的树插入尾递归

Question

我正在Scala中创建一棵自定义对象树，而我的insert方法会引发堆栈溢出，因为它不是尾递归的。但是，我不太清楚如何使它尾部递归。我见过的相关示例使用“累加器”变量，但它们要么是像Integers这样的东西，就可以被相乘和覆盖，要么是我难以适应树的列表。这是我所拥有的:

我的树木的基础:

abstract class GeoTree
case object EmptyTree extends GeoTree
case class Node(elem:GeoNode, left:GeoTree, right:GeoTree) extends GeoTree

用于递归创建树的insert方法(方法导致堆栈溢出):

  def insert(t:GeoTree, v: GeoNode): GeoTree = t match {
    case EmptyTree => new Node(v, EmptyTree, EmptyTree)
    case Node(elem:GeoNode, left:GeoTree, right:GeoTree) => {
      if (v < elem) new Node(elem, insert(left, v), right)
      else new Node(elem, left, insert(right, v))
    }
  }

我认为GeoNode的代码实际上并不特别相关，因为它非常简单。该类具有两个Long属性，并且适当重写了<，>和==运算符，以在树中使用。有人可以对我的insert函数使用累加器提出建议，还是通过其他方式使其成为尾递归？

Answer 1

您的函数不能是尾递归的。原因是您对insert的递归调用不会结束计算，而是将它们用作子表达式，在本例中为new Node(...)。例如。如果您只是在搜索底部元素，则很容易使其尾部递归。

发生了什么:当您将树降下时，在每个节点上调用insert，但是您必须记住返回根的方式，因为在用新叶子替换底部叶子后必须重新构造树值(value)。

可能的解决方案:记住显式的向下路径，而不是在堆栈上。让我们为示例使用简化的数据结构:

sealed trait Tree;
case object EmptyTree extends Tree;
case class Node(elem: Int, left:Tree, right:Tree) extends Tree;

现在定义路径是什么:这是节点列表以及信息(如果我们向右或向左走)。根始终在列表的末尾，叶始终在列表的末尾。

type Path = List[(Node, Boolean)]

现在我们可以制作一个尾递归函数，该函数计算给定值的路径:

// Find a path down the tree that leads to the leaf where `v` would belong.
private def path(tree: Tree, v: Int): Path = {
  @tailrec
  def loop(t: Tree, p: Path): Path =
    t match {
      case EmptyTree        => p
      case n@Node(w, l, r)  =>
        if (v < w) loop(l, (n, false) :: p)
        else       loop(r, (n, true)  :: p)
    }

  loop(tree, Nil)
}

还有一个函数，该函数采用路径和值，并使用该值重建新树，并将其作为路径底部的新节点:

// Given a path reconstruct a new tree with `v` inserted at the bottom
// of the path.
private def rebuild(path: Path, v: Int): Tree = {
  @tailrec
  def loop(p: Path, subtree: Tree): Tree =
    p match {
      case Nil                          => subtree
      case (Node(w, l, r), false) :: q  => loop(q, Node(w, subtree, r))
      case (Node(w, l, r), true)  :: q  => loop(q, Node(w, l, subtree))
    }
  loop(path, Node(v, EmptyTree, EmptyTree))
}

这样插入就很容易了:

def insert(tree: Tree, v: Int): Tree =
  rebuild(path(tree, v), v)

请注意，此版本并不是特别有效。可能您可以使用Seq或通过使用可变堆栈来存储路径来提高效率。但是使用List可以很好地表达这个想法。

免责声明:我只编译了代码，没有进行任何测试。

注意:

这是使用zippers遍历功能树的特殊示例。使用 zipper ，您可以将相同的想法应用到任何种类的树上，并沿不同方向行走。

如果您希望树对较大的元素集有用(如果堆栈溢出，您可能会这样做)，我强烈建议将其设置为self-balanced。也就是说，更新树的结构，使其深度始终为O(log n)。这样，在所有情况下您的操作都将很快，您不必担心堆栈溢出，并且可以使用基于堆栈的非尾递归版本。自平衡树的最简单的变体可能是AA tree。