DS: B-Baum einfügen und löschen

Показать описание

Hinweis: Bitte beachten, dass die Ordung je nach Definition unterschiedliche Bedeutung haben kann. In meinem Beispiel sagt die Ordnung m:
- Wurzelknoten hat mindestens 1, maximal 2m Elemente
- Kindknoten hat minimal m, maximal m*2 Elemente

Je nach Quelle und Definition des B-Baums kann die Ordnung bei euch/dir auch eine andere Bedeutung haben

Visualisierungen aller möglichen Algorithmen (auch B-Baum):

Verwendete Software: Windows Journal:

Empfehlung: Mit 1,5-facher Geschwindigkeit angucken

Falls Fehler gefunden werden: bitte in die Kommentare :)

Video erstellt mit HyperCam2

Рекомендации по теме

Комментарии

Leute vergess diese Definition nicht "Definition 8.2: (B-Bäume) Ein B-Baum der Ordnung m ist ein Vielweg-Suchbaum mit
folgenden Eigenschaften:
(i) Die Anzahl der Schlüssel in jedem Knoten mit Ausnahme der Wurzel liegt zwischen m und 2m. Die Wurzel enthält mindestens einen und maximal 2m Schlüssel.
(ii) Alle Pfadlängen von der Wurzel zu einem Blatt sind gleich.
(iii) Jeder innere Knoten mit s Schlüsseln hat genau s+1 Söhne (das heißt, es gibt keine
leeren Teilbäume). "
Also Beachte die Höhe der Ordnung, bei m=2, darf ein baum mindestend 4 Werte in den jeweiligen Ast beinhalten

tr

Beim Löschen der 67 in Minute 6:59 wäre es doch besser, wenn die 51 mit der 67 getauscht wird, weil es dann balanciert ist oder?

gustavvarnim

Super erklärt, nur eine Frage du erwähnst, wenn es beim Einfügen ein Overflow gibt, sollte man das mittlere Element hochnehmen. Bei der Ordnung 1 alles klar, aber was ist den bei der Ordnung 2 das mittlere Element?

shinable

bei ca. 7:50 packst du die 24 mit der 41 zusammen. Also 21/41. Dadurch geht dann der dritte Ast verloren? Ist das richtig so? Hatte das so verstanden dass dann 21, 41 und 89 eigentlich die letzte Ebene hätten bilden müssen? Kann aber komplett falsch liegen. Vielleicht hast du ja nen Tipp. ;)

jbvideography

bei 1:17 besitzt dein Wurzelknoten 2 Elemente. Laut deiner Definition des B-Baumes der Ordnung 1 (wie im Beispiel), dürfte deine Wurzel aber doch nur ein Element tragen?

xMcFlec

sehr nice!
ich wollte noch fragen was für ein Programm du zum Veranschaulichen benutzt

aglotgaming

Wenn ich einen Baum höherer Ordnung (z.b. 2) habe, wie wähle ich dann beim balance und beim merge aus welche Knoten ich nehme?

countdeville

Ich hab mir das Video in 2x Geschwindigkeit angeguckt und gaaar nichts gecheckt - kannst du es bitte nochmal langsam erklären! Danke ;)

TDJ

Einwandfrei! Wer hier einen Dislike gibt, schaut wahrscheinlich ohne Ton oder hat seinen Monitor ausgeschaltet.

MTBLeo

Sehr schöne Erklärung,

aber ein Fehler: Die maximal erlaubte Anzahl an Schlüsseln ist 2t - 1. In Ihrem Fall also 0. Das ergibt keinen Sinn, weswegen in Ihrem Beispiel die Ordnung eigentlich 2 sein sollte, nicht 1

Dies beantwortet dann auch die Frage anderer Nutzer zu höheren Ordnungen:
t = 2 -> Spaltung ab 3. Schlüssel
t = 3 -> Spaltung ab 5. Schlüssel
t = 4 -> Spaltung ab 7. Schlüssel
usw.
Somit kommt also auch immer ein ungerader Fall mit mittlerem Schlüssel heraus

Aber vielen Dank nochmal, ohne Sie wäre ich da immer noch auf dem Holzweg!

dinobot