Arbre 2-3-4
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
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
v · m | |
|---|---|
| Arbre binaire |
|
| Arbre équilibré |
|
| Arbre B |
|
| Trie |
|
| Partition binaire de l'espace trees | |
| Arbres non binaires |
|
| Arbre de base de données spatiales |
|
| Autres arbres |
|
Portail de l'informatique théorique
