Ich mache ein Projekt, in dem ich btree oder b + Baum Datenstruktur benötigen. Kennt jemand eine bestehende Implementierung von btree oder b + tree (mit Einfüge-, Lösch-, Suchalgorithmen)? Es sollte String als Eingabe akzeptieren und btree oder b + tree dieser Zeichenfolge bilden.Bestehende Implementierung von Btree oder B + Baum in Java
In dem Mangel an Details über das Problem, das Sie lösen müssen, werde ich mir erlauben, eine alternative Lösung vorschlagen, könnte lösen Sie Ihr Problem: Verwenden Sie stattdessen eine rot/schwarz-Struktur.
das Rot/Schwarz-Baum kann als ein B-Baum betrachtet werden, wie auf Wikipedia erläuterte:
A Rot-Schwarz-Baum ist in der Struktur ähnlich zu einem B-Baum der Ordnung 4, wobei jeder Knoten kann zwischen 1 bis 3 Werte und (entsprechend) zwischen 2 bis 4 Kindzeiger enthalten. In einem solchen B-Baum enthält jeder Knoten nur einen Wert, der dem Wert in einem schwarzen Knoten des Rot-Schwarz-Baums entspricht, mit einem optionalen Wert davor und/oder danach im selben Knoten, die beide einem äquivalenten roten Knoten des Knotens entsprechen rot-schwarz-Baum [...]
Java verfügt über zwei integrierte Klassen, TreeMap und TreeSet, rot/schwarz Bäume bieten. Keiner von diesen wird eine Zeichenfolge als Eingabe nehmen und einen Baum daraus wachsen lassen, aber Sie könnten in der Lage sein, etwas Ähnliches "um" eine dieser Klassen herum zu implementieren.
danke für den Vorschlag .. Ich werde versuchen, Ihre Idee zu verwenden – rohit
jdbm hat eine sehr solide Implementierung von b + Baum. Auch h + Baum, was eine interessante verwandte Datenstruktur ist.
Seitdem gab es [JDBM3] (https://github.com/jankotek/JDBM3) und [JDBM4, die in MapDB umbenannt wurde] (http: // www .mapdb.org /). –
@PeterLamberg ja - MapDB entwickelt sich zu einem sehr netten Projekt. Noch ein paar Wochen vom ersten stabilen Release, aber es sieht sehr gut aus. Beachten Sie, dass MapDB nicht b + tree b/c von Parallelitätsanforderungen verwendet - ich glaube, dass sie einen verknüpften Baum irgendeiner Art verwenden. –
Sie könnten versuchen, Electric BTree (author page here).
Ich musste meine eigene und Open Source die code implementieren.
Ich habe es nicht getestet, aber die Split-Methode war, was ich mit jedem Einsatz suchte und entfernen. Mit nur 2 Elementen wird dies fast immer passieren. Frage: Mischen Sie das Top-Level-Element? Angenommen, Sie haben Daten von 1 -5000 (5000 für diesen Kommentar) und Sie hatten das erste Element als 300, wäre es nicht sinnvoll, das näher an 2500 zu haben? – Mukus
BTW .. +1 für Ihre Antwort. – Mukus
@TejaswiRana Ich habe mit 5000 Elementen (1-5000) getestet und die Wurzel endete mit dem 2048 Wert. Die Standardimplementierung ist 2-3 Baum, aber das war nur für Testzwecke. Sie können die Reihenfolge (minKeySize) des Baums im Konstruktor übergeben. – Justin
@rohit: Ich habe eine Bearbeitung Ihrer Frage gemacht, um sie zu einem weniger offensichtlichen Kandidaten für "nah wie keine echte Frage" zu machen. Wenn du meine Änderungen nicht magst, kannst du sie gerne ändern. –
Können Sie näher erläutern, wofür Sie die Datenstruktur verwenden? –