B+Baum innere Knoten erstellen

Loddakwin

Aktives Mitglied
Hallo,

versuche gerade die inneren Knoten eines B+Baumes zu erstellen, jedoch scheitere ich an der Umsetzung. Was ich bisher habe:

Code:
  /**
   * Builds a valid inner level of this B+ tree with the minimal number of inner
   * nodes for the specified list of child nodes. This method returns a sorted
   * list of the inner nodes created in the process (sorted with respect to the
   * keys in the nodes). The children in an inner node are supposed to point
   * to the respective child nodes.
   *
   * @param children a sorted list of child nodes for which the next inner level
   *  is built
   *
   * @return a sorted list of all inner nodes created in the process, or
   *  <tt>null</tt> if there are no children to connect
   */
private List<BPNode<Key>> buildInnerLevel (final List<BPNode<Key>> children) {
    // deal with trivial cases
    if ((children == null) || children.isEmpty()) {
      return null;
    }

    List<BPNode<Key>> currentLevel = new ArrayList<BPNode<Key>>();
  
    BPNode<Key> temp = new BPNode<Key>(degree());
  
    for(int i = 1; i < children.size(); i++) {
        temp.addKey(children.get(i).key(0));
        if(temp.keys().size() > (degree() - 1)) {
      
        }
    }
  
    currentLevel.add(temp);
  
    System.out.println(currentLevel.get(0).key(0));
  
    return currentLevel;
  }

Bin mir aber ziemlich sicher das es so nicht funktionieren kann. Vielleicht muss es rekursiv umgesetzt werden?

LG
 
Hallo Loddakwin,

ein B+-Baum ist ein balancierter Baum, richtig? (Ist schon eine Weile her, dass ich Informatik studiert habe).
Prinzipiell wird zum Einfügen in einen Baum rekursiv die richtige Stelle gesucht und dann ein zusätzliches Blatt dort angehängt. Anschließend muss der Baum wieder ausbalanciert werden. Die Suche nach der richtigen Stelle kann nur dann nicht rekursiv gemacht werden, wenn die genaue Höhe des Baums und die Anzahl seiner Elemente bekannt sind, das ist in der Regel nicht der Fall, besonders nicht, wenn noch zusätzlich eingefügt werden soll.
Also musst Du eine Suchen-Funktion definieren, der Du zunächst die Wurzel des Baums übergibst. In dieser Funktion testst Du, ob Du die richtige Stelle gefunden hast -> return, oder wo weiter gesucht wird. Dieses Element übergibst Du rekursiv wieder der Funktion suchen, es ist jetzt die neue Wurzel des Teilbaums.
Irgendwann hast Du die passende Stelle gefunden, nun hängst Du dort das neue Blatt an ggf. muss evtl. der Knoten geteilt werden, wenn er sonst zu voll würde.
Ein Code-Beispiel gibt es auf GitHub: https://gist.github.com/mikelikesbikes/4742901

Hoffe es hilft weiter.

Otti
 

Loddakwin

Aktives Mitglied
Hallo Otti,

danke für deine Antwort. Ja es ist ein balancierter Baum. Die Anzahl der Element die eingefügt werden ist bekannt du meinst erst zu Laufzeit oder?. Mein großes Problem ist das ich nicht weiß, wie ich die Blätter(Liste children) so bearbeite, dass jedes erste Element eines Blattes zum ersten inneren Knoten wird und falls hier ein overflow passiert muss der Knoten gesplittet werden. Heißt erstelle 2 weiter Knoten einer auf selber Ebene mit dem neuen Schlüssel der den Overflow herbeiruft und einer steigt auf mit dem key ceil(m/2). M steht für pointer. Also ein Knoten hat bei m = 5 maximal m - 1 schlüssel bzw keys.

Die Blätter konnte ich schon richtig sortieren es geht jetzt nur mehr um die inneren Knoten und ich glaube das ich das eben nur rekursiv lösen kann, aber wie soetwas ausschauen soll hab ich echt ka.

LG
 
nehmen wir einmal das Beispiel. Der Knoten ist ein Blatt, vier Schlüssel sind drin,bei m=5 passen auch nur vier rein, d.h. das Blatt ist voll. Für dieses Blatt gibt es ein Element oberhalb, das genau auf das Blatt zeigt, nennen wir es Wurzel.
Beim Einfügen müssen jetzt korrekt zwei neue Blattkonten erzeugt werden und ein Element des bisherigen Blatts wird zur Wurzel des neuen Teilbaums, das Element soll ceil(m/2) heißen. Nun muss der Zeiger der Wurzel umgehängt werden, er muss auf ceil(m/2) zeigen. Es müssen also drei Zeiger initialisiert werden:
Wurzel ->ceil(m/2),
ceil(m/2) -> neues Blatt1,
ceil(m/2) -> neues Blatt2

Es ist also sinnvoll beim Abbruch des rekursiven Suchvorgangs die Wurzel des Teilbaums zurück zu geben, beim Einfügen dann einmal das richtige Element zu suchen und dann hast Du sämtliche Elemente und kannst Zeiger umhängen ohne dass Dir Infos verloren gehen.

Gruß

Otti
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Detlef Bosau nichtstatische Innere Klasse, this Pointer. Java Basics - Anfänger-Themen 47
S Erste Schritte Innere Klassen und Interfaces Java Basics - Anfänger-Themen 2
J static verschachtelte Klassen und innere Klassen Java Basics - Anfänger-Themen 1
B Klassen Anonyme innere Klasse Java Basics - Anfänger-Themen 4
O Innere Klassen nutzen? Java Basics - Anfänger-Themen 4
F Klassen Innere Klasse - Problem Java Basics - Anfänger-Themen 2
D Annonyme Innere Klasse: Listen mit geradem Index ausgeben Java Basics - Anfänger-Themen 6
J Klassen Innere Klassen Java Basics - Anfänger-Themen 5
T Klassen Innere Klasse Java Basics - Anfänger-Themen 3
H Threads Problem bei Thread + Innere Klasse Java Basics - Anfänger-Themen 3
S Innere Klassen in Java Java Basics - Anfänger-Themen 4
A Klassen Innere Klassen, verkettete Liste Java Basics - Anfänger-Themen 9
D static, äußere/innere Klasse Java Basics - Anfänger-Themen 4
D Unterschied innere Klasse/ anonyme innere Klasse Java Basics - Anfänger-Themen 7
G innere Klassen Java Basics - Anfänger-Themen 2
G Innere Klasse static oder nicht Java Basics - Anfänger-Themen 9
berliner Klassen Vererbung und Zugriff auf innere private Variable Java Basics - Anfänger-Themen 22
M [Einfaches Beispiel] Problem mit innere Klassen Java Basics - Anfänger-Themen 4
P In innere Klassen Variablen übergeben Java Basics - Anfänger-Themen 10
S Innere Klasse, Wertübergabe (String) Java Basics - Anfänger-Themen 7
N enum als innere Klasse Java Basics - Anfänger-Themen 7
P Methode übergibt Parameter an innere Methode Java Basics - Anfänger-Themen 2
T Zugriff auf innere Klasse von aussen Java Basics - Anfänger-Themen 2
M Warum können innere Klassen keine static-members haben? Java Basics - Anfänger-Themen 2
J Innere Maße des Fensters Java Basics - Anfänger-Themen 3
A innere Klassen Java Basics - Anfänger-Themen 6
G Innere klasssen unde "extends" klassen definieren, Java Basics - Anfänger-Themen 2
H Liste Knoten NullPointerException Java Basics - Anfänger-Themen 7
Cassy3 Binärer Suchbaum Knoten rauslöschen Java Basics - Anfänger-Themen 1
D spezifische Knoten in einem Baum zählen Java Basics - Anfänger-Themen 9
Y Knoten an einem gegebenen Index aus einer Liste entfernen. Java Basics - Anfänger-Themen 6
Y Wie greift man auf die Knoten in einem Binärbaum zu? Java Basics - Anfänger-Themen 5
J ActionListener von JCheckBox im Knoten von JTree funktioniert nicht Java Basics - Anfänger-Themen 2
S Binärbäume knoten zählen Java Basics - Anfänger-Themen 16
T Collections Methode (Knoten hinzufügen) für Graphen Java Basics - Anfänger-Themen 32
H Knoten-Reihenfolge einer LinkedList invertieren Java Basics - Anfänger-Themen 11
G Binärer Suchbaum Knoten zählen Java Basics - Anfänger-Themen 1
M Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen Java Basics - Anfänger-Themen 11
O Suchbaum Elternknoten finden Level eines Knoten bestimmen Java Basics - Anfänger-Themen 24
O Knoten und Liste verarbeitung Java Basics - Anfänger-Themen 20
E Knoten eines Baumes unter Bedinung zählen Java Basics - Anfänger-Themen 2
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
L Baum Knoten zählen Java Basics - Anfänger-Themen 6
L Graphen: Anzahl Knoten // Knoten in Array speichern Java Basics - Anfänger-Themen 4
I Erste Schritte Referenz zum Knoten davor, in einer Liste Java Basics - Anfänger-Themen 4
J Max. Anzahl von Knoten im Binärbaum Java Basics - Anfänger-Themen 3
M Werte der Knoten in Binärbaum addieren (iterativ) Java Basics - Anfänger-Themen 6
S Baumstruktur: tiefsten Knoten finden Java Basics - Anfänger-Themen 3
B Methoden BinärBaum als String Knoten löschen Java Basics - Anfänger-Themen 5
J Baum Knoten löschen Java Basics - Anfänger-Themen 10
T Datentypen Knoten Großvater finden? Java Basics - Anfänger-Themen 12
S Methoden Abtrennen ab einem gegebenen Knoten eines Binärbaums Java Basics - Anfänger-Themen 4
M Binärbaum - Problem bei Knoten anhängen / löschen Java Basics - Anfänger-Themen 5
B JTree knoten wird nicht übernommen Java Basics - Anfänger-Themen 4
L BinärTree, Knoten löschen Java Basics - Anfänger-Themen 6
Luk10 Anzahl der Knoten in einem Baum ausgeben! Java Basics - Anfänger-Themen 6
T gebe mir den ersten eltern knoten Java Basics - Anfänger-Themen 3
K verkettete Listen - Klasse Knoten Java Basics - Anfänger-Themen 19
L LinkedList vorgänger Knoten zurück geben Java Basics - Anfänger-Themen 4
H B-Baum: Knoten Position als Parameter oder als Variable im Objekt? Java Basics - Anfänger-Themen 4
D An bestimmten Knoten einer Liste zugreifen Java Basics - Anfänger-Themen 4
S Binärbaum - Klasse Knoten - Methode Suchen Java Basics - Anfänger-Themen 5
M Nachbar von Knoten bestimmen Java Basics - Anfänger-Themen 8
0x7F800000 zwei adjazenzlisten für jeden knoten eines graphen sinnvoll? Java Basics - Anfänger-Themen 17
C Bäume in Java. Knoten in Array speichern Java Basics - Anfänger-Themen 3
G eine Knoten aus einem Baum löschen. [SOLVED] Java Basics - Anfänger-Themen 7
F JTree-Knoten (DefaultMutableTreeNode) formatieren ? Java Basics - Anfänger-Themen 3
Y JTree: ein Knoten als Objekt Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben