Einfügen in (2,3)-Bäume

(Suchen funktioniert ähnlich wie bei binären Suchbäumen.)

• suchen den Knoten (direkt über Blättern), der neuen Schlüssel aufnehmen sollte.
• aus 2-Knoten wird 3-Knoten (OK),
• aus 3-Knoten wird 4-Knoten (verboten).
• Lösung:
  • diesen 4-Knoten in zwei 2-Knoten (und einen Schlüssel) zerlegen,
  • diesen Schlüssel in Vorgänger einfügen