C++ b-tree合并

Question

作为一个例子,我有以下b树模型,每个节点包含标签/值对.树指示优先级(或优先级),根最高,向下最低(但这是应用程序特定的).我想将一个新的树节合并到父节点中,新节包含可能常见的标签/值对,一直到叶节点正上方的节点(完全重复的新树节将不合并).例如

现有的树(标签,值)对表示:

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

要合并的新树:

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

最终合并树:

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

问题:对于使用std容器的b-tree合并,是否有一个优雅的C++解决方案,或者可能使用像boost这样的库？谢谢.

Answer 1

您可以使用Kasper Peeter 的tree.hh库，它是GPLv2 和GPLv3。

它是类似于 N 叉树的 STL 实现。

文档说有一个名为 merge 的可变算法，可以合并两棵树。它还解释了它是如何实现的。