C++ b树合并

作为一个例子，我有以下b树模型，每个节点包含标签/值对。该树指示优先级（或优先级），其中根是最高的，到叶片最低（但是这是特定于应用程序的）。我想将一个新的树节合并到父节点中，新节包含潜在的通用标记/值对，直到叶节点上方的节点（完全重复的新树节将不被合并）。例如。C++ 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

问题：是否有一个优雅这个B树合并使用std容器的C++解决方案，或者可能与像boost一样的库？谢谢。

2011-12-14 JeffR

最安全的方法是通过手动插入第一个b-tree中的所有项目。或者，查看www.ccs.neu.edu/home/bradrui/index_files/parareorg.pdf。 – izogfif 2012-02-20 10:14:05

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

这是一个类似于n-tree的STL实现。

documentation表示有一个可变的算法，名为merge，可以合并两棵树。它也解释了它是如何实现的。

2012-03-07 17:02:17 Gaston

回答