Les rotations

50

25 70

13

4545

85

8

4848

2828

3838

3636 60

2626

64 9055

62

17

• Voici un autre exemple d’ajout. Celui-ci engendre un cas simple de déséquilibre, car l’arbre sous-critique penche dans le même sens que le déséquilibre au nœud critique.

• Supposons que nous ajoutons un nœud avec la valeur de clé 40 à l’arbre ci-bas.

40

Les rotations

<50

25 70

13

4545

85

8

4848

2828

3838

3636 60

2626

64 9055

62

17

• Ajout de 40.

40

Les rotations

<50

25 70

13

4545

85

8

4848

2828

3838

3636 60

2626

64 9055

62

17

• Ajout de 40.

40

Les rotations

<50

25 70

13

4545

85

8

4848

2828

3838

3636 60

2626

64 9055

62

17

• Ajout de 40.

40

Les rotations

5050

>25 70

13

4545

85

8

4848

2828

3838

3636 60

2626

64 9055

62

17

• Ajout de 40.

40

Les rotations

5050

>25 70

13

4545

85

8

4848

2828

3838

3636 60

2626

64 9055

62

17

• Ajout de 40.

40

Les rotations

5050

2525 70

13

4545

85

8

4848

2828

3838

>36 60

2626

64 9055

62

17

• Ajout de 40.

40

Les rotations

5050

2525 70

13

4545

85

8

4848

2828

3838

>36 60

2626

64 9055

62

17

• Ajout de 40.

40

Les rotations

5050

2525 70

13

<45

85

8

4848

2828

3838

3636 60

2626

64 9055

62

17

• Ajout de 40.

40

Les rotations

5050

2525 70

13

<45

85

8

4848

2828

3838

3636 60

2626

64 9055

62

17

• Ajout de 40.

40

Les rotations

5050

2525 70

13

4545

85

8

4848

2828

>38

3636 60

2626

64 9055

62

17

• Ajout de 40.

40

Les rotations

5050

2525 70

13

4545

85

8

4848

2828

>38

3636 60

2626

64 9055

62

17

• Ajout de 40.

40

Les rotations

5050

2525 70

13

4545

85

8

4848

2828

3838

3636 60

2626

64 9055

62

17

• La position du nouveau nœud 40 a été déterminée. On doit donc, en remontant, vérifier si l’arbre est déséquilibré.

40

Les rotations

5050

2525 70

13

4545

85

8

4848

2828

38

3636 60

2626

64 9055

62

17

• On vérifie l’équilibre nœud par nœud, en remontant le long du chemin parcouru depuis la racine.

40

10

Les rotations

5050

2525 70

13

45

85

8

4848

2828

3838

3636 60

2626

64 9055

62

17

• On vérifie l’équilibre nœud par nœud, en remontant le long du chemin parcouru depuis la racine.

40

12

Les rotations

5050

2525 70

13

4545

85

8

4848

2828

3838

36 60

2626

64 9055

62

17

• On vérifie l’équilibre nœud par nœud, en remontant le long du chemin parcouru depuis la racine.

40

32

Les rotations

5050

25 70

13

4545

85

8

4848

2828

3838

3636 60

2626

64 9055

62

17

• On vérifie l’équilibre nœud par nœud, en remontant le long du chemin parcouru depuis la racine.

• Un déséquilibre est détecté au nœud 25.

40

42

Les rotations

25

13

45458

4848

2828

3838

36

2626

17

• On vérifie l’équilibre nœud par nœud, en remontant le long du chemin parcouru depuis la racine.

• Un déséquilibre est détecté au nœud 25.• Le nœud sous-critique est le nœud 36.

40

Les rotations

25

13

45458

4848

2828

3838

36

2626

17

• On constate que l’arbre sous-critique penche dans le même sens que le déséquilibre au nœud critique.

• On aura donc une seule rotation à faire.

40

Les rotations

25

13

45458

4848

2828

3838

36

2626

17

• On a une seule rotation à faire.

40

Les rotations

25

13

45458

4848

2828

3838

36

2626

17

• On a une seule rotation à faire.

40

Les rotations

25

134545

8 4848

2828

3838

36

262617

• On a une seule rotation à faire.

40

Les rotations

25

13 4545

8 4848

2828

3838

36

262617

• On a une seule rotation à faire.

40

Les rotations

25

134545

8

48482828

3838

36

262617

• On a une seule rotation à faire.

40

Les rotations

25

13

4545

8

484828283838

36

262617

• On a une seule rotation à faire.

40

Les rotations

25

13

4545

8

484828283838

36

262617

• On a une seule rotation à faire.• Nous avons donc rééquilibré l’arbre à partir du nœud

critique que nous avions.• Il reste encore à vérifier l’équilibre pour le reste du chemin

en remontant à la racine, car il pourrait y en avoir d’autres.

40

Les rotations

5050

2525

70

13

4545 85

8

484828283838

3636

60

2626

64 9055

6217

• On a une seule rotation à faire.• Nous avons donc rééquilibré l’arbre à partir du nœud

critique que nous avions.• Il reste encore à vérifier l’équilibre pour le reste du chemin

en remontant à la racine, car il pourrait y en avoir d’autres.

40

Les rotations

50

2525

70

13

4545 85

8

484828283838

3636

60

2626

64 9055

6217

• En l’occurrence, il ne reste qu’à vérifier qu’il n’y a pas de déséquilibre au nœud 50.

40

4 4

Les rotations

5050

2525

70

13

4545 85

8

484828283838

3636

60

2626

64 9055

6217

• On a une seule rotation à faire.• Nous avons donc rééquilibré l’arbre à partir du nœud

critique que nous avions.• Il reste encore à vérifier l’équilibre pour le reste du chemin

en remontant à la racine, car il pourrait y en avoir d’autres.

4040