Article on other languages:
 |
del.icio.us |
 |
Digg |
 |
Furl |
 |
|
 |
Rojo |
| Add to OnlyWire |
 |
Cet article ou cette section ne cite pas suffisamment ses sources. (juillet 2007)
Son contenu est donc sujet à caution. Wikipédia doit être fondée sur des informations vérifiables. Améliorez cet article en signalant les passages qui demandent une référence (en y insérant par exemple le modèle {{Référence nécessaire}}), et en liant les informations à des sources, au moyen de notes de bas de page (voir les recommandations).
|
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 clés 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.
