B-Baum: Knoten Position als Parameter oder als Variable im Objekt?

[hawkeye78]

Hallo,

ich stehe im moment vor dem Problem das ich gerne einen 2-3-Baum (der ja ein Spezialfall vom B-Baum ist) implementieren möchte. Nun stehe ich allerdings vor dem Problem das ich nicht so recht weiß ob ich die interne Position des Knotens (also ob er links, rechts oder in der mitte steht) im Knoten selbst speichern soll oder auf dem Weg durch den Baum jeweils als Parameter mitgeben soll.
Damit ich jetzt nicht allzuviel rede, habe ich einfach mal ein bißchen gemalt[1]. Im oberen Fall hat der linke Knoten einen Schlüssel zuviel und er sollte darum den mittleren und den Rechten (hier also 9 und 10) an den Elternknoten zurückgegeben werden.
Im unteren Fall hat aber der rechte Knoten ein Datum zuviel darum soll er (wieder) den mittleren und das rechte Datum (hier 30, 40) zurück geben.
Letzten endes macht es für die Implementierung an sich keinen großen Unterschied ob ich das nun als Parameter mitgebe oder es direkt im Knoten speichere, aber mich würde halt interessieren wie ihr das implementieren würdet?
Ich würde mich über die eine oder andere Antwort auf jeden fall freuen.
Viele Grüsse
Dan


PS
Oder gibt es vielleicht sogar irgendeine möglichkeit wie ich da komplett drum herum komme? Die ich einfach nicht sehe...

[1] Imageshack - exampe23tree.png

 

[XHelp]

Bin mir nicht sicher was du damit meinst. Aber wenn du eine Baumstruktur implementieren willst ist es meiner Meinung nach sinnvoller es so zu machen:

public class Node<T> {
  private T kleinerWert;
  private T grosserWert;
  private Node linkerKnoten;
  private Node mittlererKnoten;
  private Node rechterKnoten;
}

Aber wie gesagt, wüsste jetzt auf anhieb nicht was du mit "als Parameter übergeben" und "im Knoten speichern" meinst.

 

[hawkeye78]

Hallo XHelp,

erst einmal vielen Dank für deine Antwort, ich meinte vom einem Elterknoten ausgehend hat jeder Knoten 3 Kinder (so wie auch in deinem Code-Schnipsel beschrieben). Wenn nun der Kind-Knoten aber "überläuft" also ein Datum zuviel hat immer das mittlere Datum und entweder das größte Datum, wenn es sich um ein linkes Kind handelt oder aber das kleinste Datum wenn es ein rechtes Kind (aus der Sicht des Elternknoten) ist zurück gegeben. Und genau da beginnt jetzt mein Problem entweder übergebe ich aus dem Elternknoten ein Parameter der dem Knoten mitteilt das er nun ein Linkes bzw. rechtes Kind ist oder ich speichere das gleich im Knoten selbst.
Aber wie gesagt vielleicht gibt es ja noch eine elegantere Möglichkeit das ganze zu lösen die ich im moment nicht sehe...
Viele Grüsse
Dan

 

[Michael...]

Bin mir nicht ganz sicher, ob ich Dein Problem richtig verstanden habe.
Aber wenn die Kindknoten bei "Überlauf" etwas an den Elternknoten zurückgeben müssen, dann brauchen sie dafür eine Referenz auf den Elternknoten. Daher könnten sie ja einfach den Elternknoten fragen, an welcher Position sie sich befinden. Oder sie sagen dem Elternknoten einfach: "Hey, ich bin übervoll. Nimm Dir was du brauchst" und der Elternknoten holt sich selbst die richtigen Daten.

 

[XHelp]

Eigentlich braucht man keine Referenz auf den Elternknoten. Man könnte auch eine Methode

void balance()

, die durch den Baum geht und jeder Elternknoten fragt die Kinder: "seid ihr übervoll? dann gibt mal was her".