15

假设我们有一个递归数据结构，比如二叉树。有很多方法可以遍历它，并且它们具有不同的内存使用配置文件。例如，如果我们要简单地打印每个节点的值，使用如下的按顺序遍历的伪代码......

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

...我们的内存使用量是恒定的，但是由于递归调用，我们会增加调用堆栈的大小。在非常大的树上，这可能会溢出它。

假设我们决定优化调用堆栈大小；假设这种语言能够进行适当的尾调用，我们可以将其重写为以下的前序遍历......

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)评估，我认为这实际上会评估左右流的头部。即使它没有（由于附加的聪明），我认为递归地构建这个 thunk（借用 Haskell 的一个术语）基本上会以相同的速度增长内存。与其说“把这个节点放在要遍历的节点列表中”，不如说“这是另一个要评估的值，它将告诉你接下来要遍历什么”，但结果是一样的；线性内存增长。

我能想到的唯一可以避免这种情况的策略是在每个节点中具有可变状态，声明已经遍历了哪些路径。这将允许我们拥有一个引用透明的函数，它说“给定一个节点，我会告诉你接下来应该遍历哪个单个节点”，我们可以使用它来构建一个 O(1) 迭代器。

是否有另一种方法来完成 O(1)、尾调用优化的二叉树遍历，可能没有可变状态？

4

4 回答 4

12

是否有另一种方法来完成 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是树的深度。

于 2013-08-21T12:55:58.797 回答
8

一个花哨的答案。

我们可以使用免费的 monad 来获得有效的内存利用率限制。

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

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

函子的代数是从到对 somef的函数。例如，任何 monad 都有任何 object 的代数：phif xxxm 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为 functor 构造免费的 monad 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]上下文中的代数都是构造表示树的有序遍历的字符串的代数。因为 functorT a b在运行时会构造一棵新树，所以它必须具有与 larsmans 引用的解决方案相同的内存消耗特性——如果树没有保存在内存中，则节点一被代表整体的字符串替换就被丢弃子树。

于 2013-08-21T17:29:07.440 回答
1

鉴于您引用了节点的父节点，这里发布了一个不错的解决方案。用尾递归调用替换 while 循环（传入lastandcurrent应该这样做。

内置的反向引用允许您跟踪遍历顺序。没有这些，我想不出一种方法可以在O(log(n))辅助空间小于的（平衡）树上做到这一点。

于 2013-08-20T23:30:42.380 回答
0

我无法找到答案，但我得到了一些指示。去看看http://www.ics.uci.edu/~dan/pub.html，向下滚动到

[33] DS Hirschberg 和 SS Seiden，有界空间树遍历算法，信息处理快报 47 (1993)

下载 postscript 文件，您可能需要将其转换为 PDF（我的 ps 查看器无法正确显示）。它在第 2 页（表 1）中提到了一些算法和其他文献。

于 2013-08-21T05:55:11.663 回答