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

回答