C++ b-tree merge

Question

As an example, I've the following b-tree model with each node containing tag/value pairs. The tree indicates precedence (or priority), with the root being highest, down to the leaves as lowest (but this is application specific). I want to merge a new tree section into the parent, with the new section containing potentially common tag/value pairs all the way down to the node just above a leaf node (a completely duplicate new tree section would just not be merged). E.g.

Existing tree (tag,value) pairs indicated:

            A,0
 ,----------,-------------,
B,1        B,2           B,3
      ,-------------,
     C,1           C,2

New tree to merge:

               A,0
                |
               B,3
          ,-----------,
         C,1         C,2

Final merged tree:

            A,0
 ,----------,-----------------,
B,1        B,2               B,3
      ,-------------,    ,-----------,
     C,1           C,2  C,1         C,2

Question: is there an elegant C++ solution to this b-tree merge using std containers, or possible with a library like boost? Thanks.

Answer 1

You can use Kasper Peeter's tree.hh library, it's GPLv2 and GPLv3.

It's an STL like implementation for an n-ary tree.

The documentation says that there's a mutable algorithm, named merge, that can merge two trees. It also explains how it's achieved.