B-Tree - Warum kann es keinen Knoten mit einer geraden Anzahl von Schlüsseln geben?

Question

Ich versuche, einen B-Baum gemäß dem Kapitel "B-Trees" in "Einführung in Algorithmen" zu implementieren.

Was ich nicht ganz verstehe, ist der "minimale Grad". In dem Buch wird angegeben, dass der Grad eine Nummer ist, die die untere/obere Grenze für die Anzahl der Schlüssel angibt, die ein Knoten halten kann. Es heißt es weiter, dass:

1. Alle Nicht-Root-Knoten speichert mindestens t - 1 Schlüssel und hat t Kinder.
2. Jeder Knoten speichert höchstens 2*t - 1 Schlüssel und hat 2*t Kinder.

So erhalten Sie für t = 2:

1. t - 1 = 1 Tasten und t = 2 Kinder
2. 2*t - 1 = 3 Tasten und 4 Kinder

Für t = 3

1. t - 1 = 2 Tasten und t = 3 Kanal ildren
2. 2*t - 1 = 5 Tasten und 6 Kinder

Jetzt ist hier das Problem: Es scheint, dass die Knoten in einem B-Baum nur eine ungeradee Anzahl der Schlüssel 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?

Answer 1

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 zulässig.

Darüber hinaus darf die Wurzel des Baumes nur 1 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 amortisierte O(1) (zählende Splitting- und Fügeoperationen) Lösch- und Einfügeoperationen.

Answer 2

ist es nicht unmöglich, aber suboptimal. Wie teilt man einen Knoten mit einer ungeraden Anzahl von Kindern auf?