11

我在 scala 中创建了一个自定义对象树，我的 insert 方法引发了堆栈溢出，因为它不是尾递归的。但是，我不太清楚如何使它尾递归。我见过的相关示例使用“累加器”变量，但它们要么是可以乘以和覆盖的整数之类的东西，要么是我无法适应树的列表。这是我所拥有的：

我的树的基础：

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

递归创建树的插入方法（导致堆栈溢出的方法）：

  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函数使用累加器或其他方式使其尾递归提出建议吗？

4

1 回答 1

16

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

发生了什么：当您将树向下传递时，调用insert每个节点，但您必须记住返回根的路径，因为您必须在用新值替换底部叶子后重建树。

一个可能的解决方案：明确记住下行路径，而不是在堆栈上。让我们使用一个简化的数据结构来举例：

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遍历功能树的特殊示例。使用拉链，您可以将相同的想法应用到任何种类的树上，并在各个方向上行走。
  • 如果您希望树对更大的元素集有用（如果您遇到堆栈溢出，您可能会这样做），我强烈建议将其设置为self-balanced。也就是说，更新树的结构，使其深度始终为O(log n)。那么您的操作在所有情况下都会很快，您不必担心堆栈溢出，并且可以使用基于堆栈的非尾递归版本。自平衡树最简单的变体可能是AA 树。
于 2013-07-07T13:01:27.987 回答