c++ - 有效地复制/乘法树

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 时，给它 2 个指向 A 的指针而不是复制从 A 开始的整个子树是微不足道的。

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

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

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

      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)的路径。