Quiz on 2-3-Bäume (2-3 Trees)

In einem 2-3-Baum hat jeder innere Knoten entweder genau 2 Kinder (2-Knoten) oder genau 3 Kinder (3-Knoten).

Alle Blätter eines 2-3-Baums liegen immer auf derselben Höhe, wodurch der Baum balanciert ist.

In einem 2-3-Baum können Knoten beliebig viele Schlüssel enthalten, solange die Suchbaumeigenschaft erhalten bleibt.

Die Suchbaumeigenschaft eines 2-3-Baums besagt unter anderem, dass für einen 3-Knoten mit Schlüsseln $k_1 < k_2$ alle Werte im linken Teilbaum $< k_1$, im mittleren Teilbaum zwischen $k_1$ und $k_2$, und im rechten Teilbaum $> k_2$ liegen.

Beim Einfügen in einen 2-3-Baum kann es notwendig sein, Knoten zu spalten (splitten), wodurch sich die Höhe des Baums im Extremfall um 1 erhöhen kann.

Die Höhe eines 2-3-Baums mit $n$ Schlüsseln kann im Worst-Case linear in $n$ wachsen, also $h = O(n)$.

Ein 2-3-Baum ist ein Spezialfall eines allgemeineren $(a,b)$-Baums, bei dem jeder Knoten zwischen $a$ und $b$ Kindern haben darf.