3

我需要（对于 g++）一个（计算时间）优化的算法树结构来复制/乘一棵树。

我的树将是一棵 k-ary 树，但不一定是填充的。主要操作是将现有树相乘（最多 k 次）并将树作为子树添加到新节点。然后叶节点级别将被擦除以保持固定级别规则。

有人知道提供此功能的数据结构吗？

乘法的一个例子：假设我们有一个二叉树

      A
      |
     / \
    /   \
   B     C
   |    / \
   |   /   \
   D   E    F

我们想添加一个新节点/乘以

    R
   / \
  /   \
 ..   ..

所以结果看起来像

            R
           / \
          /   \
         /     \
        /       \
       /         \
      A           A
      |           |            
     / \         / \        
    /   \       /   \        
   B     C      B     C        
   |    / \     |    / \        
   |   /   \    |   /   \    
   D   E    F   D   E    F

我试图将它组织在一个类似于堆的结构中的 std::vector 上，但是乘以树仍然有点慢，因为我必须自己复制每个树级别，而不是一次复制整个树。

4

2 回答 2

3

当你添加 R 时，给它 2 个指向 A 的指针是微不足道的，而不是从 A 开始复制整个子树。

   R
  / \
  | |
  \ /
   A
   |           
  / \
 /   \
B     C
|    / \
|   /   \
D   E    F

这既非常快又很容易编码。

现在，如果您稍后想要更新树的一侧，而不是另一侧，那么问题就来了。例如，也许您想将“正确的”F 更改为 G。此时您可以仅在某些节点上使用写时复制策略，在这种情况下会导致

      R
     / \
    /   \
   A    A <-- copied, left side points to B
   |   / \        
  / \  *  \  
 /   \     \
B     C     C <-- copied, left side points to E
|    / \   / \
|   /   \  *  \
D   E    F     G

基本上，您只需要将路径从更改点 (F/G) 复制到根节点（最容易实现）或复制到共享的最高节点（本例中为 A）。

于 2013-04-17T10:59:33.760 回答
0

也许看看 T9 字典的 Android 代码。AFAIR 它看起来很平坦，但基本上他们所做的是构建一个字母树，这样从上到下遍历树就可以生成单词。而且我认为他们使用相对偏移量从一个节点跳转到下一个节点（如链表）。

因此，您应该能够一次复制整个树。

我不记得你的确切布局，我认为它并没有像我在这里做的那样做丑陋的填充，但是继续你的例子，它看起来像这样（！）：

# your tree

         __________
      ///   _      \      _
     /// /// \      \  /// \
A007021B007000D000000C007014E000000F000000
  \\\_/                   \\\_____/


# copying it, "under" R:
                __________                                __________
     _       ///   _      \      _                     ///   _      \      _
  /// \     /// /// \      \  /// \                   /// /// \      \  /// \
R007049A007021B007000D000000C007014E000000F000000A007021B007000D000000C007014E000000F000000
     \\\ \\\_/                   \\\_____/      /  \\\_/                   \\\_____/
      \\\______________________________________/
于 2013-04-17T07:14:08.680 回答