有效压缩未标记的树木

cs.stackexchange https://cs.stackexchange.com/questions/168

题

考虑未标记的植根于二进制树。我们可以 压缩 这样的树：每当有指向子树的指针$ t $和$ t'$带有$ t = t'$（解释$ = $为结构平等）时，我们存储（WLOG）$ t $，然后将所有指针替换为$ t' $，指示为$ t $。看 Uli的答案 例如。

给出一种算法，该算法是在上述意义上作为输入，并计算压缩后保留的（最小）节点数。该算法应在时间$ cal {o}（n log n）$（在统一成本模型中）运行，并在输入中的节点数量。

这是一个考试问题，我无法提出一个不错的解决方案，也没有看过。

有帮助吗？

解决方案

是的，您可以在$ o（n log n）$时间中执行此压缩，但是这并不容易:)我们首先进行一些观察，然后呈现该算法。我们假设这棵树最初不是压缩的 - 这不是真正需要的，但是使分析更容易。

首先，我们以归纳的“结构平等”来表征。令$ t $和$ t'$为两（sub）树。如果$ t $和$ t'$都是无效的树（根本没有顶点），则它们在结构上是等效的。如果$ t $和$ t'$都不是无效的树，那么如果他们的左子女在结构上等同于结构上，那么它们在结构上是等效的，并且其正确的孩子在结构上是等效的。 “结构对等”是这些定义的最小固定点。

例如，任何两个叶子节点在结构上都是等效的，因为它们都将无效的树作为两个孩子，它们在结构上等效。

因为说“他们的左子女在结构上等同于他们，他们的合适的孩子也是如此，这很烦人，我们经常会说“他们的孩子在结构上是等价的”，并打算相同。另请注意，当我们的意思是“扎根于此顶点”时，我们有时会说“这个顶点”。

上面的定义立即为我们提供了如何执行压缩的提示：如果我们知道所有子树的结构等效性最多最多$ d $，那么我们可以轻松地计算出子树的结构等效性，其深度为$ d+1 $。我们确实必须以一种聪明的方式进行此计算，以避免$ O（n^2）$运行时间。

该算法将在执行过程中为每个顶点分配标识符。标识符是集合$ {1、2、3， dots，n } $中的数字。标识符是唯一的，永远不会改变：因此，我们假设我们在算法开始时将一些（全局）变量设置为1，并且每次我们将标识符分配给某个顶点时，我们都会为顶点和增量分配该变量的当前值该变量的值。

我们首先将输入树转换为（最多$ n $）列表，其中包含相等深度的顶点，以及指向父母的指针。这很容易在$ o（n）$时间中完成。

我们首先将所有叶子（可以在列表中找到深度0的顶点0）中压缩到一个顶点。我们将此顶点分配为标识符。通过重定向任一个顶点的母体指向另一个顶点的父来完成两个顶点的压缩。

我们进行了两次观察：首先，任何顶点都有严格的深度孩子，其次，如果我们对所有小于$ d $的深度顶点进行了压缩（并给出了标识符），则是两个深度$ d $的顶点在结构上等效，如果孩子的标识符重合，则可以压缩。最后观察得出的是以下论点：如果他们的孩子在结构上等同于结构上，两个顶点在结构上是等效的，并且在压缩后，这意味着他们的指针指向相同的孩子，这又意味着孩子的标识符是平等的。

我们遍历所有列表，这些列表的深度从小深度到较大的深度都具有相等的深度。对于每个级别，我们创建一个整数对列表，其中每对对应于该级别的某个顶点的孩子的标识符。我们在该级别上有两个顶点在结构上等效，如果它们相应的整数对相等。使用词典订购，我们可以对它们进行分类并获得相等的整数对。我们将这些集合压缩到上面的单个顶点，并给它们标识符。

上述观察结果证明了这种方法起作用并导致压缩树。总运行时间为$ O（n）$，加上对我们创建的列表进行排序所需的时间。由于我们创建的整数对的总数为$ n $，因此，根据需要，总的运行时间为$ O（n log n）$。计算过程结束时剩下多少个节点是微不足道的（只需查看我们分发出多少个标识符）即可。

其他提示

压缩不可用的数据结构，以使其不复制任何结构相等的子术语被称为 哈希求. 。这是功能编程中的内存管理中的重要技术。 Hash Consing是一种用于数据结构的系统回忆。

我们将在哈希（Hash Consing）之后进行哈希（Hash-cons the Tree），并计算节点。 hash可以始终以$ o（n ： mathrm {lg}（n））$ operations在$ o（n ： mathrm {lg}（lg}（n））$ operations中，可以完成大小$ n $的数据结构；计数末尾的节点数为线性在节点数中。

我将树认为具有以下结构（在Haskell语法中写）：

data Tree = Leaf
          | Node Tree Tree

对于每个构造函数，我们需要将其从其可能的论点定位为将构造函数应用于这些参数的结果。叶子是微不足道的。对于节点，我们维护有限的部分地图$ mathtt {nodes}：t times t to n $，其中$ t $是一组树标识符，$ n $是一组节点标识符； $ t = n uplus { ell } $，其中$ ell $是唯一的叶子标识符。 （用具体的术语，标识符是指向内存块的指针。）

我们可以使用对数时间数据结构 nodes, ，例如平衡的二进制搜索树。下面我会打电话 lookup nodes 查找键的操作 nodes 数据结构， insert nodes 在新键下增加值并返回该键的操作。

现在，我们穿越树并添加节点。尽管我正在用像haskell一样的伪代码写作，但我会治疗 nodes 作为全球可变变量；我们只会添加它，但是插入需要贯穿整个过程。这 add 功能在树上递归，将其子树添加到 nodes 地图，并返回根的标识符。

insert (p1,p2) =
add Leaf = $\ell$
add (Node t1 t2) =
    let p1 = add t1
    let p2 = add t2
    case lookup nodes (p1,p2) of
      Nothing -> insert nodes (p1,p2)
      Just p -> p

的数量 insert 呼叫，这也是最终尺寸 nodes 数据结构是最大压缩后节点的数量。 （如果需要，为空树添加一个。）

这是另一个想法，它旨在将树的结构编码成数字，而不是任意标记它们。为此，我们使用任何数字的主要分解都是唯一的。

就我们的目的而言，让$ e $表示在树上的空位置，$ n（l，r）$ a节点带有左子树$ l $和右Subtree $ r $。 $ n（e，e）$将是一片叶子。现在，让我们

美元结束{align*} $

使用$ f $，我们可以计算树自下而上包含的所有子树的集合；在每个节点中，我们合并了从孩子那里获得的编码集并添加一个新数字（可以在孩子的编码中以恒定时间计算出来）。

最后一个假设是对真实机器的伸展。在这种情况下，人们希望使用类似的东西 康托的配对功能 而不是指数。

该算法的运行时间取决于树的结构（在平衡树上，$ cal {o}（n log n）$，并具有任何允许在线性时间内联合的设置实现）。对于一般树，我们将需要对数时间结合，并进行简单的分析。不过，也许复杂的分析可能会有所帮助。请注意，通常的最坏情况树是线性列表，在这里承认$ cal {o}（n log n）$时间，因此目前尚不清楚最坏的案例可能是什么。

因为在评论中不允许图片：

enter image description here

左上：输入树

右上：植根于节点5和7的子树也是同构。

左下和右下：压缩树不是唯一的定义。

请注意，在这种情况下，树的大小从$ 7+5 | t | $ too $ 6+| t | $下降。

编辑：我读了一个问题，因为t和t'是同一个父母的孩子。我将压缩的定义也是递归的，这意味着您可以压缩两个先前压缩的子树。如果这不是实际的问题，那么我的答案可能不起作用。

$ o（n log n）$ begs $ t（n）= 2t（n/2） + cn $ divide和Conquer解决方案。递归压缩节点并在压缩后计算每个子树中的后代数量。这是一些Python风格的伪代码。

def Comp(T):
   if T == null:
     return 0
   leftCount = Comp(T.left)
   rightCount = Comp(T.right)
   if leftCount == rightCount:
     if hasSameStructure(T.left, T.right):
       T.right = T.left
       return leftCount + 1
     else
       return leftCount + rightCount + 1

在哪里 hasSameStructure() 是一个在线性时间内比较两个已经压缩子树的函数，以查看它们是否具有完全相同的结构。编写一个线性时间递归函数，该功能每次遍历每个函数，并检查一个子树在另一个人时是否有左孩子等。不应该很难。

令$ n_ ell $和$ n_r $分别为左右子树的大小（压缩后）。然后运行时间为$$ t（n）= t（n_1） + t（n_2） + o（1） mbox {如果$ n_ ell ell neq n_r $} $$和$$ 2T（n/2） + o（n） mbox {否则} $$

许可以下： CC-BY-SA 和 归因
不隶属于 cs.stackexchange
scroll top