有效地复制/复制树

Question

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

我的树是k元树，但不一定是填充的。主要操作是对现有树进行乘法(最多k次)，并将树作为子树添加到新节点。然后，叶节点级别将被擦除以保留固定级别规则。

有人知道提供这种功能的数据结构吗?

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

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

，我们想添加一个新的节点/叠底，比如

    R
   / 
  /   
 ..   ..

所以结果看起来像

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

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

Answer 1

当您添加R时，给它两个指向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)。

Answer 2

也许可以看看android的T9-dictionary代码。虽然看起来很平，但基本上他们做的是建立一个字母树，这样从上到下遍历树就能生成单词。我认为他们使用相对偏移量从一个节点跳到下一个节点(像链表)。

所以你应该能够在一次运行中复制整个树。

我不记得确切的布局了，我想它没有像我在这里做的那样做丑陋的填充，但是继续你的例子，它看起来像这样:

# your tree
         __________
      ///   _            _
     /// ///         /// 
A007021B007000D000000C007014E000000F000000
  \_/                   \_____/

# copying it, "under" R:
                __________                                __________
     _       ///   _            _                     ///   _            _
  ///      /// ///         ///                    /// ///         /// 
R007049A007021B007000D000000C007014E000000F000000A007021B007000D000000C007014E000000F000000
     \ \_/                   \_____/      /  \_/                   \_____/
      \______________________________________/