C ++ b-tree merge - PullRequest
Новая
       15

C ++ b-tree merge

5 голосов
/ 15 декабря 2011

В качестве примера приведена следующая модель 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

Вопрос: существует ли элегантное C ++ решение для этого слияния b-дерева с использованием контейнеров std или возможно с такой библиотекой, как boost?Спасибо.

1 Ответ

1 голос
/ 07 марта 2012

Вы можете использовать библиотеку Kasper Peeter tree.hh , это GPLv2 и GPLv3.

Это STL-подобная реализация для n-арного дерева.

The документация говорит, что существует изменяемый алгоритм с именем merge, который может объединять два дерева.Это также объясняет, как это достигается.

...