Arbre 2-3-4

Un arbre 2-3-4 est un 2-4 arbre B ou arbre B d'ordre 2, c'est-à-dire un arbre comportant uniquement des 2-nœuds, 3-nœuds et 4-nœuds (un N-nœud étant un nœud possédant N-1 clés et N fils), et dont les fils bornent les clés dans les sous arbres (on se reportera à l'article arbre B pour une définition précise).

En tant qu'arbre B, on peut l'utiliser pour implémenter le type abstrait table de symboles. Les opérations de recherche, d'insertion et de suppression sont en O(ln n).

L'aspect le plus intéressant des arbres 2-3-4 est leur représentation sous forme d'arbres bicolores :

• Un 2-nœud est représenté par un nœud noir seul ;
• Un 3-nœud est représenté par un nœud rouge plus son père noir (un 3-nœud peut être orienté à droite ou à gauche selon que le nœud rouge est le fils droit ou gauche) ;
• Un 4-nœud est représenté par 2 nœuds rouges plus leur père noir.

Cette représentation est plus simple à manipuler car il s'agit d'un arbre binaire de recherche. De plus, elle gaspille moins de place mémoire quand l'arbre contient peu de 4-nœuds.

• 
  2-node
• 
  3-node
• 
  4-node

• Portail de l'informatique théorique