Duplicate / multiplicate tree efficiently

Question

I need (for g++) a (computation time) optimized algorithm tree structure to duplicate/multiplicate a tree.

My tree will be a k-ary tree, but not necessarily filled. The main operation is to multiplicate (up to k times) the existing tree and add the trees as subtrees to a new node. Then the leaf node level will be erased to hold the fixed-level rule.

Does anybody know of a data structure offering this?

An example for the multiplication: Suppose we have a binary tree

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

and we want to add a new node / multiply like

    R
   / \
  /   \
 ..   ..

So the result will look like

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

I tried to organize this on a std::vector in a heap-like structure, but multiplying the tree is still kind of slow, because I have to copy each tree level by itself rather than just copying the whole tree at once.

Answer 1

When you add R, it is trivial to give it 2 pointers to A, rather than copying the entire subtree starting at A.

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

This is both very fast and very easy to code.

Now, the hitch in this comes in if you later want to update one side of the tree, but not the other. For example, perhaps you want to change the "right" F to a G. At that point you can use a copy-on-write strategy on only certain of the nodes, in this case leading to

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

Basically, you only need to copy the path from the point of the change (F/G) up to either the root (easiest to implement) or up to the highest node that is shared (A in this example).

Answer 2

Maybe take a look on Androids code for the T9-dictionary. AFAIR it looks flat, but basically what they do is build a tree of letters, so that traversing the tree from top to bottom makes words. And I think they used relative offsets to jump from on node to the next (like a linked list).

So you should be able to copy the whole tree in one run.

I don't remember the exact layout thou, and i think it didn't do ugly padding as I do here, but to continue w/ your example it would look something(!) like this:

# your tree

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


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