C++ b-tree merge

Como ejemplo, tengo el siguiente modelo de árbol b con cada nodo que contiene pares de etiqueta/valor. El árbol indica prioridad (o prioridad), con la raíz más alta, hasta las hojas como más baja (pero esto es específico de la aplicación). Quiero fusionar una nueva sección de árbol en el elemento principal, con la nueva sección que contiene pares de etiquetas/valores potencialmente comunes hasta el nodo que se encuentra justo encima de un nodo hoja (una nueva sección de árbol completamente duplicada simplemente no se fusionaría). P.ej.C++ b-tree merge

pares existentes árbol (etiqueta, valor) indicaron:

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

Nueva árbol de fusionar:

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

final árbol fusionada:

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

Pregunta: ¿Hay un elegante ¿Solución de C++ a esta combinación de b-tree usando contenedores estándar, o posible con una biblioteca como boost? Gracias.

Fuente

2011-12-14 JeffR

La forma más segura de hacerlo es mediante la inserción manual de todos los elementos del segundo árbol b dentro del primero. Alternativamente, eche un vistazo a www.ccs.neu.edu/home/bradrui/index_files/parareorg.pdf. – izogfif

Hay un boost.btree (en desarrollo), no estoy seguro de si va a ayudar, pero aquí está: https://github.com/Beman/Boost-Btree –

Es posible que también desee comprobar esta implementación de un b- tree: http://touc.org/btree.html – nevero

Puede usar la biblioteca tree.hh de Kasper Peeter, es GPLv2 y GPLv3.

Es una implementación similar a STL para un árbol n-ario.

El documentation dice que hay un algoritmo mutable, llamado merge, que puede unir dos árboles. También explica cómo se logra.

Fuente

2012-03-07 17:02:17 Gaston

Respuesta

Cuestiones relacionadas