Baum 2-3-4

Ein 2-3-4-Baum ist ein 2-4- Baum B oder Baum B der Ordnung 2, dh ein Baum, der nur 2 Knoten, 3 Knoten und 4 Knoten umfasst (ein N-Knoten ist ein Knoten mit N. -1 Schlüssel und N Kinder), und deren Kinder die Schlüssel in den Unterbäumen begrenzen ( eine genaue Definition finden Sie im Baumartikel B ).

Als Baum B können wir damit die Symboltabelle für abstrakte Typen implementieren . Die Operationen zum Suchen, Einfügen und Löschen sind in O (ln n) .

Der interessanteste Aspekt von 2-3-4 Bäumen ist ihre Darstellung als zweifarbige Bäume  :

• Ein 2-Knoten wird nur durch einen schwarzen Knoten dargestellt.
• Ein 3-Knoten wird durch einen roten Knoten plus seinen schwarzen Vater dargestellt (ein 3-Knoten kann nach rechts oder links ausgerichtet werden, je nachdem, ob der rote Knoten das rechte oder das linke Kind ist).
• Ein 4-Knoten wird durch 2 rote Knoten plus ihren schwarzen Vater dargestellt.

Diese Darstellung ist einfacher zu handhaben, da es sich um einen binären Suchbaum handelt . Außerdem wird weniger Speicher verschwendet, wenn der Baum nur wenige 4-Knoten enthält.

• 2-Knoten

• 3-Knoten

• 4-Knoten