1.2 Arbres marqués
29
Fig. 1.28 Un arbre 2-3 de recherche à 12 nœuds et 19 clés, complété avec les 20 possibilités
d’insertion
Fig. 1.29 Insertion dans un arbre 2-3 : à gauche, la clé x arrive dans un nœud non plein. Elle s’y
place et il y a à droite 3 possibilités d’insertion
Fig. 1.30 Insertion dans un arbre 2-3 : à gauche, la clé x arrive dans un nœud plein ; ici nous
supposons que x < y < z et la clé y est donc renvoyée au niveau supérieur dans le dessin de droite
d’insertion), la nouvelle clé x peut y être ajoutée, et le nœud interne terminal
contient ensuite deux clés et a trois enfants qui sont des possibilités d’insertion
(cf. la figure 1.29).
– Si ce nœud interne terminal contient déjà deux clés y et z et a trois enfants (cf. la
figure 1.30), il est plein et ne peut accueillir de clé supplémentaire ; la clé médiane
de {x, y, z} est alors envoyée au niveau supérieur pour obtenir deux nœuds ayant
chacun une clé, et donc quatre possibilités d’insertion en tout. Naturellement, la
clé médiane qui remonte au niveau supérieur peut arriver à son tour dans un nœud