Estoy haciendo un proyecto en el que requiero estructura de datos btree o b + tree. ¿Alguien sabe de una implementación existente de btree o b + tree (con inserción, eliminación, algoritmos de búsqueda)? Debe aceptar cadena como entrada y formar btree o b + tree de esta cadena.Implementación existente del árbol Btree o B + en Java
En la falta de detalles sobre el problema que debe resolver, me permito sugerir una solución alternativa que podría resolver su problema: utilice un árbol rojo/negro en su lugar.
El árbol rojo/negro puede ser pensado como un árbol B, como se explica en Wikipedia:
Un árbol rojo-negro es similar en estructura a un árbol B de orden 4, donde cada nodo puede contener entre 1 y 3 valores y (en consecuencia) entre 2 y 4 punteros secundarios. En dicho árbol B, cada nodo contendrá solo un valor que coincida con el valor en un nodo negro del árbol rojo-negro, con un valor opcional antes y/o después en el mismo nodo, ambos coincidentes con un nodo rojo equivalente del árbol rojo-negro [...]
Java tiene dos clases incorporadas, TreeMap y TreeSet, que proporcionan los árboles rojo/negro. Ninguno de estos tomará una cadena como entrada y hará crecer un árbol a partir de ella, pero es posible que pueda implementar algo similar "alrededor" de una de esas clases.
gracias por la sugerencia. Trataré de usar su idea – rohit
jdbm tiene una implementación muy sólida de b + tree. También h + tree que es una estructura de datos relacionada interesante.
Desde entonces ha habido [JDBM3] (https://github.com/jankotek/JDBM3) y [JDBM4 que se renombró a MapDB] (http: // www .mapdb.org /). –
@PeterLamberg sí - MapDB se perfila como un proyecto muy agradable. Aún faltan algunas semanas para la primera publicación estable, pero se ve muy bien. Tenga en cuenta que MapDB no está utilizando b + tree b/c de requisitos de concurrencia. Creo que están utilizando un árbol vinculado de algún tipo. –
Puede probar el BTree de Electric (author page here).
He tenido que implementar el mío propio y abrir el code.
No lo he probado pero el método de división era lo que estaba buscando con cada inserción y quité. Con solo 2 elementos, esto ocurrirá casi todo el tiempo. Pregunta: ¿Mezclas el elemento de nivel superior? Digamos que tiene datos de 1 -5000 (5000 por el bien de este comentario) y tenía el primer elemento como 300, ¿no tendría sentido tenerlo tan cerca de 2500? – Mukus
btw .. +1 por su respuesta. – Mukus
@TejaswiRana He probado con 5000 elementos (1-5000) y la raíz terminó con el valor 2048. La implementación predeterminada es de 2 a 3 árboles, pero eso solo fue para fines de prueba. Puede pasar el orden (minKeySize) del árbol en el constructor. – Justin
@rohit: He hecho algo de edición de su pregunta para que sea un candidato menos obvio para "una pregunta cercana pero no real". Si no le gustan mis cambios, no dude en revertirlos. –
¿Puede explicar en qué va a utilizar la estructura de datos? –