Ich versuche, einen B-Tree gemäß dem Kapitel "B-Trees" in "Einführung in Algorithmen" zu implementieren.
Was ich nicht ganz verstehe, ist der "minimale Abschluss". In dem Buch wird angegeben, dass der Grad eine Zahl ist, die die untere / obere Grenze für die Anzahl der Schlüssel angibt, die ein Knoten enthalten kann . Es sagt weiter, dass:
t - 1 keys und hat t children . 2*t - 1 keys und hat 2*t children . Sie erhalten also für t = 2:
t - 1 = 1 Schlüssel und t = 2 Kinder 2*t - 1 = 3 Schlüssel und 4 Kinder Für t = 3
t - 1 = 2 Schlüssel und t = 3 Kinder 2*t - 1 = 5 Schlüssel und 6 Kinder Jetzt ist das Problem: Es scheint, dass die Knoten in einem B-Baum nur eine ungerade Anzahl von Schlüsseln speichern können, wenn sie voll sind.
Warum kann es keinen Knoten geben mit, sagen wir höchstens 4 Schlüssel und 5 Kinder? Hat es etwas mit dem Teilen des Knotens zu tun?
Es scheint, dass die Knoten in einem B-Baum nur eine ungerade Anzahl von Schlüsseln speichern können?
Definitiv nicht. Die von Ihnen geschriebenen Zahlen sind die minimale bzw. die maximale Anzahl der Schlüssel. Für t = 2 sind Knoten mit 1, 2, 3 Schlüsseln zulässig. Für t = 3 sind Knoten mit 2, 3, 4, 5 Schlüsseln erlaubt.
Außerdem darf die Wurzel des Baums nur einen Schlüssel haben.
Es ist möglich, Bäume zu definieren (und zu implementieren), die z. 1 oder 2 Schlüssel in einem Knoten (sogenannte 2-3 Bäume). Der Grund, warum B-Bäume definiert sind, um einen mehr aufzunehmen, ist, dass dies zu einer schnelleren Leistung führt. Insbesondere ermöglicht dies amortisierten O(1) (zählende Aufspalten und Fügen Operationen) löschen und einfügen Operationen.
Tags und Links algorithm data-structures b-tree