Scala:具有复杂结构的树插入尾递归 [英] Scala: Tree Insert Tail Recursion With Complex Structure

问题描述

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

I'm creating a tree of custom objects in scala and my insert method throws a stack overflow because it's not tail recursive. However, I can't quite figure out how to make it tail recursive. Related examples I've seen use "accumulator" variables, but they've either been things like Integers which can just be multiplied and overwritten, or lists which i'm having trouble adapting to a tree. Here's what I have:

我的树木的基础:

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

以递归方式创建树的插入方法(导致堆栈溢出的方法):

The insert method to recursively create the tree (method causing the stack overflow):

  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函数如何使用累加器提出建议，或通过其他方式使其递归尾部吗?

I don't think the code for the GeoNode is actually particularly relevant because it's very simple. The class has two Long attributes and the <, >, and == operators overriden appropriately for use inside a tree. Can someone make a suggestion on how to use an accumulator for my insert function, or some other way to make it tail recursive?

推荐答案

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

Your function can't be tail recursive. The reason is that your recursive calls to insert don't end the computation, they're used as a subexpressions, in this case in new Node(...). For example. if you were just searching for the bottom element, it would easy to make it tail recursive.

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

What's happening: As you're descending the tree down, calling insert on each of the nodes, but you have to remember the way back to the root, since you have to reconstruct the tree after you replace a bottom leaf with your new value.

可能的解决方案:请明确记住向下的路径，而不要放在堆栈上.让我们为示例使用简化的数据结构:

A possible solution: Remember the down path explicitly, not on stack. Let's use a simplified data structure for the example:

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

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

Now define what a path is: It's a list of nodes together with the information if we went right or left. The root is always at the end of the list, the leaf at the start.

type Path = List[(Node, Boolean)]

现在，我们可以创建一个尾递归函数，以给定值来计算路径:

Now we can make a tail recursive function that computes a path given a value:

// 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)
}

和一个采用路径和值并以该值作为路径底部的新节点重建新树的函数:

and a function that takes a path and a value and reconstructs a new tree with the value as a new node at the bottom of the path:

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

Note that this version isn't particularly efficient. Probably you could make it more efficient using Seq, or even further by using a mutable stack to store the path. But with List the idea can be expressed nicely.

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

Disclaimer: I only compiled the code, I haven't tested it at all.

注释:

• 这是一个使用拉链来遍历功能树的特殊示例.使用拉链，您可以将相同的想法应用到任何种类的树上，并沿着不同的方向行走树.
• 如果您希望树对更大的元素集有用(如果堆栈溢出，您可能会这样做)，我强烈建议将其做成 AA树.

• This is a special example of using zippers to traverse a functional tree. With zippers you can apply the same idea on any kind of tree and walk the tree in various directions.
• If you want the tree to be useful for larger sets of elements (which you probably do, if you're getting stack overflows), I'd strongly recommend making it self-balanced. That is, update the structure of the tree so that it's depth is always O(log n). Then your operations will be fast in all cases, you won't have to worry about stack overflows and you can use your stack-based, non-tail-recursive version. Probably the easiest variant of a self-balancing tree is the AA tree.

这篇关于Scala:具有复杂结构的树插入尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！