précédent | suivant | table des matières

Arbres binaires équilibrés : arbre 2-3-4.

Sommaire
  1. Définition
  2. Propriété
  3. Ajout
  4. Suppression

1 Définition.

Les arbres 2-3-4 sont des arbres tels que  

  1. tous les nœuds ont 2, 3 ou 4 fils.
    les nœuds 2, 3, 4
    Les sous-arbres A, B, C et D ont les propriétés suivantes : 
  2. tous les nœuds feuilles sont à la même profondeur.

Exemple d'arbre 2-3-4 obtenu par l'ajout des nombres de la séquence 10, 5, 8, 7, 15, 20, 12, 9, 13 : exemple

2 Propriété.

La hauteur h de l'arbre 2-3-4 qui contient n valeurs est telle que :  log4(n+1) ≤ h ≤ log2(n+1).

En effet : 

3 Ajout.

L'insertion top-down se comporte de la façon suivante : 

Quand on descend dans l'arbre vers un nœud 4, celui-ci est éclaté avant d'y parvenir. Ainsi, ont est certain de ne jamais ajouter une nouvelle valeur dans un nœud 4.

  1. Si le nœud 4 est la racine il est éclaté de la façon suivante :
    exemple devient exemple C'est le cas où la hauteur de l'arbre augmente de 1.
  2. Si le nœud 4 n'est pas la racine il est le fils d'un nœud 2 ou d'un nœud 3 (il ne peut pas être le fils d'un nœud 4 car celui-ci aura été éclaté lors de la descente) :  Dans ces deux cas la hauteur de l'arbre n'est pas augmentée. Les transformations sont identiques si le nœud 4 à éclater est en position E ou F.

L'insertion conserve la propriété «toutes les feuilles sont à la même profondeur» : le seul moment où la hauteur de l'arbre augment, est lors de l"éclatement de la racine. Cet éclatement augmente les profondeurs de toutes les feuilles de 1.

4 Suppression.

Lors de la descente dans l'arbre, vers l'élément à supprimer, on fait les tranformations qu'il faut pour que le nœud où on arrive soit un nœud 3 ou un nœud 4 (sauf pour la racine).

  1. J'ai un frère immédiat gauche ou droite qui est un nœud 3 ou un nœud 4 : 
    exempledevientexemple
    Le principe est le même si c'est un frère à gauche.
  2. Sinon, j'ai un frère immédiat gauche ou droite qui est un nœud 2 : 

Quand on arrive sur un nœud qui contient l'élément à supprimer : 

haut de la page