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

hawkeye78

Bekanntes Mitglied
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

Top Contributor
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:
Java:
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

Bekanntes Mitglied
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...

Top Contributor
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

Top Contributor
Eigentlich braucht man keine Referenz auf den Elternknoten. Man könnte auch eine Methode
Code:
void balance()
, die durch den Baum geht und jeder Elternknoten fragt die Kinder: "seid ihr übervoll? dann gibt mal was her".
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
D spezifische Knoten in einem Baum zählen Java Basics - Anfänger-Themen 9
L Baum Knoten zählen Java Basics - Anfänger-Themen 6
L B+Baum innere Knoten erstellen Java Basics - Anfänger-Themen 3
J Baum Knoten löschen Java Basics - Anfänger-Themen 10
Luk10 Anzahl der Knoten in einem Baum ausgeben! Java Basics - Anfänger-Themen 6
G eine Knoten aus einem Baum löschen. [SOLVED] Java Basics - Anfänger-Themen 7
HelpInneed Baum ausgeben (aber mal anders) Java Basics - Anfänger-Themen 3
G AVL-Baum Java Basics - Anfänger-Themen 1
G Rot-Schwarz-Baum Java Basics - Anfänger-Themen 8
L Baum aus Integer Liste erstellen Java Basics - Anfänger-Themen 0
CptK Interface Baum visualisieren Java Basics - Anfänger-Themen 37
CptK Best Practice Merge-Sort als Baum darstellen Java Basics - Anfänger-Themen 3
E Baum pfadweise durchlaufen Java Basics - Anfänger-Themen 11
O Naives links rechts einfügen in ADT Baum Java Basics - Anfänger-Themen 8
L Traversierungsverfahren Baum: LevelOrder Java Basics - Anfänger-Themen 17
L Rekursion im Baum Java Basics - Anfänger-Themen 9
D B-Baum einfügen und löschen Java Basics - Anfänger-Themen 2
F Aufgabe Rekursion Binärer Baum Java Basics - Anfänger-Themen 15
D Werte AVL-Baum löschen Java Basics - Anfänger-Themen 2
M Binären Baum Kinder setzen Java Basics - Anfänger-Themen 12
U 2-3-4 Baum Top-Down Java Basics - Anfänger-Themen 4
U 2-3-4 Baum Top-Down Java Basics - Anfänger-Themen 0
J Überprüfen, ob eine 2D Matrix ein Baum ist Java Basics - Anfänger-Themen 5
R Baum erzeugen Java Basics - Anfänger-Themen 61
B Baum Traversierung Postorder Java Basics - Anfänger-Themen 6
B OOP Über einen AVL-Baum iterieren (NullPointer) Java Basics - Anfänger-Themen 5
A Voller Baum Java Basics - Anfänger-Themen 7
S n-ärer Baum Java Basics - Anfänger-Themen 6
O Unterschied Baum <-> Automat Java Basics - Anfänger-Themen 2
K Tiefen- und Breitensuche beim Baum durch Stack und Warteschlange Java Basics - Anfänger-Themen 1
C kompletter baum Java Basics - Anfänger-Themen 2
M Collections Iterator und generischer Baum Java Basics - Anfänger-Themen 0
M Baum Code kurze frage ... Java Basics - Anfänger-Themen 6
D Ein Objekt in einem Baum finden und ausgeben. Java Basics - Anfänger-Themen 4
K Rot-Schwarz-Baum min und max-Tiefe Java Basics - Anfänger-Themen 1
A min() Methode Baum Java Basics - Anfänger-Themen 1
J Baum rekursiv durchlaufen Java Basics - Anfänger-Themen 2
T Baum mit Turtle zeichnen Java Basics - Anfänger-Themen 2
Screen 2,4 Baum Frage Java Basics - Anfänger-Themen 6
T Rot-schwarz Baum Problem Java Basics - Anfänger-Themen 3
A Rekursion in Baum und ArrayList als Rückgabe Java Basics - Anfänger-Themen 2
P Pythagoras Baum - Berechnung der Punkte Java Basics - Anfänger-Themen 9
C 2-3 Baum Java Basics - Anfänger-Themen 6
H Baum Java Basics - Anfänger-Themen 4
L Rot Scharz Baum von Binärbaum erben Java Basics - Anfänger-Themen 9
B Baum > Baum-Swing Java Basics - Anfänger-Themen 4
L eigenen Baum schreiben Java Basics - Anfänger-Themen 5
T Array in einen Baum zu überführen Java Basics - Anfänger-Themen 3
S Das reinschreiben einer Klasse in den Baum Java Basics - Anfänger-Themen 6
A Baum mit geometricfigur Werte Java Basics - Anfänger-Themen 6
D Datentypen Einfügen im RotSchwarz Baum Java Basics - Anfänger-Themen 2
F FileSystem in Baum darstellen/wurzel festlegen Java Basics - Anfänger-Themen 3
G List als Rückgabewert einer rekursiven Methode (Baum) Java Basics - Anfänger-Themen 3
I Baum graphisch darstellen Java Basics - Anfänger-Themen 2
P Binärer Baum mit Composite-Entwurfsmuster Java Basics - Anfänger-Themen 2
L Baum Swing AVL Java Basics - Anfänger-Themen 4
Binary.Coder 2-3-4 Baum vs. (2,4) Baum Java Basics - Anfänger-Themen 2
ModellbahnerTT Ab-Baum Applet Java Basics - Anfänger-Themen 3
P Baum-Menü in Java Java Basics - Anfänger-Themen 5
H Baum Java Basics - Anfänger-Themen 11
G AVL Baum Java Basics - Anfänger-Themen 20
J Baum spiegeln Java Basics - Anfänger-Themen 7
N 2-3 Baum, Einfügen Java Basics - Anfänger-Themen 5
G Rekursion mit Return - Baum durchlaufen Java Basics - Anfänger-Themen 4
G Baum Datenstruktur Java Basics - Anfänger-Themen 2
V Baum mit log n Aufwand für Einfügen und Löschen und. Java Basics - Anfänger-Themen 5
H Tiefensuche im binären Baum Java Basics - Anfänger-Themen 2
P Problem mit Darstellung im Baum Java Basics - Anfänger-Themen 4
G Binärer Baum Java Basics - Anfänger-Themen 3
M Binärer Baum Tiefe Java Basics - Anfänger-Themen 14
G universeller baum Java Basics - Anfänger-Themen 13
G Baum testen Java Basics - Anfänger-Themen 20
B Array To Baum Java Basics - Anfänger-Themen 2
B Baum to Array Java Basics - Anfänger-Themen 17
H Löschen in einem binären Baum führt zu einem StackOverflow Java Basics - Anfänger-Themen 2
L Binären Baum speichern Java Basics - Anfänger-Themen 6
R Pythagoras-Baum Java Basics - Anfänger-Themen 5
W Baum durchlaufen Java Basics - Anfänger-Themen 3
T binärer Baum Java Basics - Anfänger-Themen 3
P allg. Baum aus Liste Java Basics - Anfänger-Themen 2
J String in binären Baum umwandeln Java Basics - Anfänger-Themen 7
R binärer Baum Java Basics - Anfänger-Themen 2
F Abstrakte Klasse Baum Java Basics - Anfänger-Themen 6
H Liste Knoten NullPointerException Java Basics - Anfänger-Themen 7
Cassy3 Binärer Suchbaum Knoten rauslöschen Java Basics - Anfänger-Themen 1
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 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

Ähnliche Java Themen

Neue Themen


Oben