Sto facendo un progetto in cui richiedo una struttura dati btree o b + tree. Qualcuno sa di un'implementazione esistente dell'albero btree o b + (con insert, delete, algoritmi di ricerca)? Dovrebbe accettare string come input e formare btree o b + tree di queste stringhe.Implementazione esistente dell'albero Btree o B + in Java
Nella mancanza di dettagli sul problema che è necessario risolvere, mi permetterò di suggerire una soluzione alternativa che potrebbe risolvere il problema: utilizzare invece un albero rosso/nero.
Il/albero nero rosso può essere pensato come un b-albero, come spiegato Wikipedia:
Un albero rosso-nero è simile nella struttura di un B-albero di ordine 4, dove ciascuna il nodo può contenere da 1 a 3 valori e (di conseguenza) tra 2 e 4 puntatori figlio. In tale B-tree, ogni nodo conterrà solo un valore corrispondente al valore in un nodo nero dell'albero rosso-nero, con un valore opzionale prima e/o dopo nello stesso nodo, entrambi corrispondenti a un nodo rosso equivalente del albero rosso-nero [...]
Java ha due classi incorporate, TreeMap e TreeSet, fornendo alberi rosso/nero. Nessuno di questi prenderà una stringa come input e far crescere un albero da esso, ma potresti essere in grado di implementare qualcosa di simile "attorno" a una di quelle classi.
grazie per il suggerimento .. proverò ad usare la tua idea – rohit
jdbm ha un'implementazione molto solida dell'albero b +. Anche h + tree, che è un'interessante struttura di dati correlati.
Da allora c'è stato [JDBM3] (https://github.com/jankotek/JDBM3) e [JDBM4 che è stato rinominato in MapDB] (http: // www .mapdb.org /). –
@PeterLamberg yes - MapDB si preannuncia come un progetto molto bello. Ancora poche settimane dalla prima versione stabile, ma sembra molto buona. Nota che MapDB non usa b + tree b/c dei requisiti di concorrenza - credo che stiano usando un albero collegato di qualche tipo. –
Si potrebbe provare Electric's BTree (author page here).
Ho dovuto implementare il mio e aprire il code.
Non l'ho provato ma il metodo split era quello che stavo cercando con ogni insert e remove. Con solo 2 elementi ciò avverrà quasi sempre. Domanda: mischia l'elemento di livello superiore? Supponiamo tu abbia dati da 1 -5000 (5000 per il gusto di questo commento) e tu avessi il primo elemento come 300, non avrebbe senso averlo più vicino a 2500? – Mukus
btw .. +1 per la tua risposta. – Mukus
@TejaswiRana Ho testato 5000 elementi (1-5000) e la radice ha finito con il valore 2048. L'implementazione predefinita è di 2-3 albero, ma era solo a scopo di test. Puoi passare l'ordine (minKeySize) dell'albero nel costruttore. – Justin
@rohit: Ho apportato alcune modifiche alla tua domanda per renderla un candidato meno ovvio per "chiudere come non una vera domanda". Se non ti piacciono le mie modifiche, sentiti libero di ripristinarle. –
Puoi approfondire su cosa utilizzerai la struttura dati? –