Fa 2-3-4

A 2-3-4 fa egy 2-4 fa B vagy 2. rendű fa, vagyis egy fa csak 2 csomópontot, 3 csomópontot és 4 csomópontot tartalmaz (egy N csomópont N -1 kulcs és N gyermek), és akiknek gyermekei korlátozzák az alfák kulcsait (az egyik a B cikkfára hivatkozik a pontos meghatározásra).

Mivel fa B , fel tudjuk használni, hogy hajtsák végre a absztrakt típus szimbólumtáblát . A keresés, beillesztés és törlés műveletei O (ln n) .

A 2-3-4 fa legérdekesebb szempontja, hogy kétszínű fákként ábrázolják őket  :

• A 2 csomópontot csak egy fekete csomópont képviseli;
• A 3 csomópontot vörös csomópont és fekete apja képviseli (a 3 csomópont jobbra vagy balra orientálható attól függően, hogy a piros csomópont a jobb vagy a bal gyermek);
• A 4 csomópontot 2 piros csomópont és fekete apjuk képviseli.

Ezt az ábrázolást könnyebb kezelni, mert ez egy bináris keresési fa . Ezenkívül kevesebb memóriát pazarol, ha a fa kevés 4 csomópontot tartalmaz.

• 2 csomópont

• 3 csomópont

• 4 csomópont