Balancierte Bäume: (2,3)-Bäume

(2,3)-Baum:

• alle Blätter sind gleich tief

  und haben keine Schlüssel

• jeder innere Knoten ist
  • ein 2-Knoten: 2 Kinder $[l,r]$, 1 Schlüssel $x$

    jeder Schlüssel in $l$ $< x <$ jeder Schlüssel in $r$

  • ein 3-Knoten: 3 Kinder $[l,m,r]$, 2 Schlüssel $[x,y]$

    jeder Schlüssel in $l$ $< x <$ jeder Schlüssel in $m$ $< y <$ jeder Schlüssel in $r$

Diese Eigeschaften (Invarianten) müssen bei allen Operationen erhalten bleiben.