能否使用O(1)的内存消耗，进行尾递归优化的懒惰遍历递归数据结构？

Question

假设我们有一个递归的数据结构，比如二叉树。有很多遍历它的方法，它们具有不同的内存使用特点。例如，如果我们仅仅打印每个节点的值，使用伪代码像以下中序遍历...

visitNode(node) {
    if (node == null) return;
    visitNode(node.leftChild);
    print(node.value);
    visitNode(node.rightChild);
}

...我们的内存使用量将保持不变，但由于递归调用，我们会增加调用栈的大小。在非常大的树上，这可能会导致溢出。

假设我们决定优化调用栈大小；假设该语言能够进行 proper tailcalls，则我们可以将其重写为以下的先序遍历...

visitNode(node, nodes = []) {
    if (node != null) {
        print(node.value);
        visitNode(nodes.head, nodes.tail + [node.left, node.right]);
    } else if (node == null && nodes.length != 0 ) {
        visitNode(nodes.head, nodes.tail);
    } else return;
}

虽然我们永远不会“爆堆”，但是随着树的大小增加，我们现在将看到堆使用量呈线性增长。

假设我们现在尝试懒惰地遍历这棵树 - 这就是我的推理变得模糊的地方。我认为即使使用基本的惰性求值策略，我们增长的内存速率也将与尾调用优化版本相同。以下是一个使用Scala的Stream类提供的惰性求值的具体示例：

sealed abstract class Node[A] {
  def toStream: Stream[Node[A]]
  def value: A
}

case class Fork[A](value: A, left: Node[A], right: Node[A]) extends Node[A] {
  def toStream: Stream[Node[A]] = this #:: left.toStream.append(right.toStream)
}

case class Leaf[A](value: A) extends Node[A] {
  def toStream: Stream[Node[A]] = this #:: Stream.empty
}

即使只有流的头部是严格求值的，但每当 left.toStream.append(right.toStream) 被求值时，我认为这实际上会评估左右两个流的头部。即使它没有（由于追加 cleverness），我认为 递归构建这个 thunk（借用 Haskell 的术语）本质上会以相同的速率增加内存。我们不是说，“把这个节点放在要遍历的节点列表中”，而是基本上说，“这里有另一个要评估的值，它将告诉您下一个要遍历的内容”，但结果是相同的；线性内存增长。

我唯一能想到的避免这种情况的策略是在每个节点中具有可变状态，声明已经遍历过的路径。这将允许我们拥有一个参考透明的函数，该函数表示：“给定一个节点，我将告诉您下一个应该遍历的单个节点”，并且我们可以使用该函数构建 O(1) 迭代器。

是否有另一种方法可以实现二叉树的 O(1)、尾调用优化遍历，可能不需要可变状态？

- rybosome

---

使用可变状态来完成这个任务，虽然不容易但是可行的——这也是大多数（并非全部，因为我相信有些人不会费心）垃圾收集器在追踪时所做的。 - user395760

如果树不需要在遍历后保留，则可以通过线性化树以O(1)辅助空间进行迭代。否则，我认为您需要非常量级别的空间。 - Fred Foo

确实，使用指针反转可以在O(1)的额外空间内完成。但这并不总是适用，因为它会在遍历期间破坏树的结构。 - augustss

你说：“我们现在会看到堆使用率与树的大小呈线性增长”，但实际上应该是“与遍历深度呈线性增长”。就树的大小而言，它只是对数级别的增长，这与递归版本相同。 - firefrorefiddle

你为什么需要这个？如果你预计会看到的最大树深度增加了，只需增加最大堆栈大小...问题解决了。 - Robin Green

Answer 1

有没有其他方法可以实现O(1)、尾调用优化的二叉树遍历，可能不需要可变状态?

如我在评论中所述，如果树不需要在遍历后保留，则可以这样做。以下是一个Haskell示例：

data T = Leaf | Node T Int T

inOrder :: T -> [Int]
inOrder Leaf                     =  []
inOrder (Node Leaf x r)          =  x : inOrder r
inOrder (Node (Node l x m) y r)  =  inOrder $ Node l x (Node m y r)

如果我们假设垃圾收集器会清理我们刚处理过的任何Node，则此方法所需的辅助空间为O(1)，因此我们能够有效地通过右旋转版本进行替换。但是，如果我们处理的节点不能立即进行垃圾回收，则最终子句可能在到达叶子节点之前积累O(n)个节点。

如果您具有父指针，则这也是可行的。然而，父指针需要可变状态，并阻止子树共享，因此它们并不真正是函数式的。如果您使用一对(cur, prev)表示迭代器，它最初为(root, nil)，则可以按照这里所述的步骤执行迭代。但是，您需要使用指针比较的语言才能使其正常工作。

如果没有父指针和可变状态，您需要维护某些数据结构，以至少跟踪树的根节点及其位置，因为您需要在中序或后序遍历期间的某个时候使用此类结构。这样的结构必然需要Ω(d)的空间，其中d是树的深度。

- Fred Foo

Answer 2

一个花哨的答案。

我们可以使用自由单子来获得有效的内存利用边界。

    {-# LANGUAGE RankNTypes
               , MultiParamTypeClasses
               , FlexibleInstances
               , UndecidableInstances #-}

    class Algebra f x where
      phi :: f x -> x

一个函子的代数是指对于某个对象x，从f x到x的函数phi。例如，任何单子都有一个关于任何对象m x的代数：

    instance (Monad m) => Algebra m (m x) where
      phi = join

可以构建任何函子f的自由单子（可能是某种类型的函子，如omega-cocomplete，或一些其他类型；但是所有Haskell类型都是多项式函子，这些函子是omega-cocomplete的，因此对于所有Haskell函子，该语句肯定成立）：

    data Free f a = Free (forall x. Algebra f x => (a -> x) -> x)
    runFree g (Free m) = m g

    instance Functor (Free f) where
      fmap f m = Free $ \g -> runFree (g . f) m

    wrap :: (Functor f) => f (Free f a) -> Free f a
    wrap f = Free $ \g -> phi $ fmap (runFree g) f

    instance (Functor f) => Algebra f (Free f a) where
      phi = wrap

    instance (Functor f) => Monad (Free f) where
      return a = Free ($ a)
      m >>= f = fjoin $ fmap f m

    fjoin :: (Functor f) => Free f (Free f a) -> Free f a
    fjoin mma = Free $ \g -> runFree (runFree g) mma

现在我们可以使用Free为函子T a构建自由单子：

    data T a b = T a b b
    instance Functor (T a) where
      fmap f (T a l r) = T a (f l) (f r)

对于这个函数对象，我们可以为对象[a]定义一个代数结构。

    instance Algebra (T a) [a] where
      phi (T a l r) = l++(a:r)

一棵树是一个自由单子，它的函子为 T a：

    type Tree a = Free (T a) ()

它可以使用以下函数构建（如果定义为ADT，则它们将是构造函数名称，因此没有什么特别的）：

    tree :: a -> Tree a -> Tree a -> Tree a
    tree a l r = phi $ T a l r -- phi here is for Algebra f (Free f a)
    -- and translates T a (Tree a) into Tree a

    leaf :: Tree a
    leaf = return ()

为了演示这是如何工作的：

    bar = tree 'a' (tree 'b' leaf leaf) $ tree 'r' leaf leaf
    buz = tree 'b' leaf $ tree 'u' leaf $ tree 'z' leaf leaf
    foo = tree 'f' leaf $ tree 'o' (tree 'o' leaf leaf) leaf

    toString = runFree (\_ -> [] :: String)

    main = print $ map toString [bar, buz, foo]

当 runFree 遍历树以将 leaf () 替换为 [] 时，所有上下文中 T a [a] 的代数都是构造表示树的中序遍历的字符串的代数。因为函子 T a b 在进行遍历时构造了一棵新树，所以它必须具有与 larsmans 引用的解决方案相同的内存消耗特征 - 如果树没有保存在内存中，那么节点在被表示整个子树的字符串替换后立即被丢弃。

- Sassa NF

Answer 3

假设你有节点父级的引用，这里链接有一个很好的解决方案。将while循环替换为尾递归调用（传入last和current），就可以实现了。

内置的反向引用允许你跟踪遍历顺序。如果没有这些，我想不出在（平衡）树上使用少于O(log(n))辅助空间的方法。

- Ben Sidhom

Answer 4

我没有找到答案，但是我得到了一些指针。请查看http://www.ics.uci.edu/~dan/pub.html，向下滚动到

[33] D.S. Hirschberg和S.S. Seiden，一个有界空间的树遍历算法，信息处理信件47（1993）

下载后缀为postscript的文件，您可能需要convert它为PDF格式（我的ps查看器无法正确显示它）。第2页（表1）提到了许多算法和其他文献。

- huynhjl

---

参考算法需要修改树，因为它使用了可变状态，并且假设您可以获取结构的地址。函数式编程语言通常不允许这样做。 - Fred Foo

@larsmans，是的，我在谷歌上只找到了一个纯函数式的东西，就是http://www.scss.tcd.ie/Glenn.Strong/Documents/drafts/ifl2004-draft.ps，但似乎没有完成。所以我没有链接它。它似乎有线性化代码，通过莫里斯风格的线程，但我无法确定它是否真正是O(1)。 - huynhjl

@larsmans，另外原始文章还引用了其他具有空间特征的算法，因此您仍然可以看到1993年左右的最新技术水平。 - huynhjl