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每个节点,但你必须记住返回根的方式,因为你必须在用新值替换底部叶子后重建树.

一种可能的解决方案:明确记住下行路径,而不是堆栈.让我们使用简化的数据结构作为示例:

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这个想法可以很好地表达出来.

免责声明:我只编译了代码,我还没有测试过.

笔记:

• 这是使用拉链遍历功能树的特殊示例.使用拉链,您可以在任何类型的树上应用相同的想法,并在各个方向走树.
• 如果你希望树对更大的元素集(你可能会这样做,如果你有堆栈溢出)有用,我强烈建议让它自我平衡.也就是说,更新树的结构,使其深度始终为O(log n).那么在所有情况下你的操作都会很快,你不必担心堆栈溢出,你可以使用基于堆栈的非尾递归版本.可能自平衡树的最简单变体是AA树.