cours_17.md

title: "Tri par tas et arbres AVL"
date: "2022-03-09"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto

Questions sur les notions du dernier cours

• Comment représenter un tableau sous forme d'arbre binaire?

. . .

• Qu'est-ce qu'un tas?

Exemple de tri par tas (1/N)

        | 1 | 16 | 5 | 12 | 4 | 2 | 8 | 10 | 6 | 7 |

::: columns

:::: column

• Quel est l'arbre que cela représente?

. . .

graph TD;
    id0((1))-->id1((16));
    id0-->id2((5));
    id1-->id3((12));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((8));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((7));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff

::::

:::: column

But: Transformer l'arbre en tas.

• On commence à l'indice N/2 = 5: 4.
• 7 > 4 (enfant > parent).
• intervertir 4 et 7.

graph TD;
    id0((1))-->id1((16));
    id0-->id2((5));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((8));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff

::::

:::

. . .

                            *                    *
        | 1 | 16 | 5 | 12 | 7 | 2 | 8 | 10 | 6 | 4 |

Exemple de tri par tas (2/N)

        | 1 | 16 | 5 | 12 | 7 | 2 | 8 | 10 | 6 | 4 |

::: columns

:::: column

But: Transformer l'arbre en tas.

• On continue à l'indice N/2-1 = 4: 12.
• Déjà un tas, rien à faire.

graph TD;
    id0((1))-->id1((16));
    id0-->id2((5));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((8));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff

::::

:::: column

But: Transformer l'arbre en tas.

• On continue à l'indice N/2-2 = 3: 5.
• 5 < 8, échanger 8 et 5 (aka max(2, 5, 8))

graph TD;
    id0((1))-->id1((16));
    id0-->id2((8));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff

::::

:::

. . .

        | 1 | 16 | 8 | 12 | 7 | 2 | 5 | 10 | 6 | 4 |

Exemple de tri par tas (3/N)

        | 1 | 16 | 5 | 12 | 7 | 2 | 8 | 10 | 6 | 4 |

::: columns

:::: column

But: Transformer l'arbre en tas.

• Indice N/2-1 = 4: 12.
• Déjà un tas, rien à faire.

graph TD;
    id0((1))-->id1((16));
    id0-->id2((5));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((8));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff

::::

:::: column

But: Transformer l'arbre en tas.

• Indice N/2-2 = 3: 5.
• 5 < 8, 5 <=> max(2, 5, 8)

graph TD;
    id0((1))-->id1((16));
    id0-->id2((8));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff

::::

:::

                   *                *
        | 1 | 16 | 8 | 12 | 7 | 2 | 5 | 10 | 6 | 4 |

Exemple de tri par tas (4/N)

        | 1 | 16 | 8 | 12 | 7 | 2 | 5 | 10 | 6 | 4 |

::: columns

:::: column

But: Transformer l'arbre en tas.

• Indice N/2-3 = 1: 16.
• Déjà un tas, rien à faire.

graph TD;
    id0((1))-->id1((16));
    id0-->id2((8));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff

::::

:::: column

But: Transformer l'arbre en tas.

• Indice N/2-4 = 1: 1.
• 1 < 16 && 1 < 8, 1 <=> max(1, 16, 8)

graph TD;
    id0((16))-->id1((1));
    id0-->id2((8));
    id1-->id3((12));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff

::::

:::

           *   *
        | 16 | 1 | 8 | 12 | 7 | 2 | 5 | 10 | 6 | 4 |

Exemple de tri par tas (5/N)

        | 16 | 1 | 8 | 12 | 7 | 2 | 5 | 10 | 6 | 4 |

::: columns

:::: column

But: Transformer l'arbre en tas.

• Recommencer avec 1.
• 1 <=> max(1, 12, 7).

graph TD;
    id0((16))-->id1((12));
    id0-->id2((8));
    id1-->id3((1));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((10));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff

::::

:::: column

But: Transformer l'arbre en tas.

• Recommencer avec 1.
• 1 <=> max(1, 10, 6).

graph TD;
    id0((16))-->id1((12));
    id0-->id2((8));
    id1-->id3((10));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((1));
    id3-->id8((6));
    id4-->id9((4));
    id4-->id10(( ));    
    style id10 fill:#fff,stroke:#fff

::::

:::

                *        *               *
        | 16 | 12 | 8 | 10 | 7 | 2 | 5 | 1 | 6 | 4 |

• L'arbre est un tas.

Exemple de tri par tas (6/N)

        | 16 | 12 | 8 | 10 | 7 | 2 | 5 | 1 | 6 | 4 |

::: columns

:::: column

But: Trier les tas.

• Échanger la racine, 16 (max de l'arbre) avec 4.
• Traiter la racine.

graph TD;
    id0((4))-->id1((12));
    id0-->id2((8));
    id1-->id3((10));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((1));
    id3-->id8((6));

::::

:::: column

But: Trier les tas.

• 4 <=> max(4, 12, 8).
• 4 <=> max(4, 10, 7).
• 4 <=> max(4, 1, 6).

graph TD;
    id0((12))-->id1((10));
    id0-->id2((8));
    id1-->id3((6));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((1));
    id3-->id8((4));

::::

:::

        | 12 | 10 | 8 | 6 | 7 | 2 | 5 | 1 | 4 || 16

Exemple de tri par tas (7/N)

        | 12 | 10 | 8 | 6 | 7 | 2 | 5 | 1 | 4 || 16

::: columns

:::: column

But: Trier les tas.

• Échanger la racine, 12 (max de l'arbre) avec 4.
• Traiter la racine.

graph TD;
    id0((4))-->id1((10));
    id0-->id2((8));
    id1-->id3((6));
    id1-->id4((7));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((1));
    id3-->id8((  ));
    style id8 fill:#fff,stroke:#fff

::::

:::: column

But: Trier les tas.

• 4 <=> max(4, 10, 8).
• 4 <=> max(4, 6, 7).

graph TD;
    id0((10))-->id1((7));
    id0-->id2((8));
    id1-->id3((6));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((5));
    id3-->id7((1));
    id3-->id8((  ));
    style id8 fill:#fff,stroke:#fff

::::

:::

        | 10 | 7 | 8 | 6 | 4 | 2 | 5 | 1 || 12 | 16

Exemple de tri par tas (8/N)

        | 10 | 7 | 8 | 6 | 4 | 2 | 5 | 1 || 12 | 16

::: columns

:::: column

But: Trier les tas.

• Échanger la racine, 10 (max de l'arbre) avec 1.
• Traiter la racine.

graph TD;
    id0((1))-->id1((7));
    id0-->id2((8));
    id1-->id3((6));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((5));

::::

:::: column

But: Trier les tas.

• 1 <=> max(1, 7, 8).
• 5 <=> max(1, 2, 5).

graph TD;
    id0((8))-->id1((7));
    id0-->id2((5));
    id1-->id3((6));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((1));

::::

:::

        | 8 | 7 | 5 | 6 | 4 | 2 | 1 || 10 | 12 | 16

Exemple de tri par tas (9/N)

        | 8 | 7 | 5 | 6 | 4 | 2 | 1 || 10 | 12 | 16

::: columns

:::: column

But: Trier les tas.

• Échanger la racine, 8 (max de l'arbre) avec 1.
• Traiter la racine.

graph TD;
    id0((1))-->id1((7));
    id0-->id2((5));
    id1-->id3((6));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((  ));
    style id6 fill:#fff,stroke:#fff

::::

:::: column

But: Trier les tas.

• 1 <=> max(1, 7, 5).
• 1 <=> max(1, 6, 4).

graph TD;
    id0((7))-->id1((6));
    id0-->id2((5));
    id1-->id3((1));
    id1-->id4((4));
    id2-->id5((2));
    id2-->id6((  ));
    style id6 fill:#fff,stroke:#fff

::::

:::

        | 7 | 6 | 5 | 1 | 4 | 2 || 8 | 10 | 12 | 16

Exemple de tri par tas (10/N)

        | 7 | 6 | 5 | 1 | 4 | 2 || 8 | 10 | 12 | 16

::: columns

:::: column

But: Trier les tas.

• Échanger la racine, 7 (max de l'arbre) avec 2.
• Traiter la racine.

graph TD;
    id0((2))-->id1((6));
    id0-->id2((5));
    id1-->id3((1));
    id1-->id4((4));

::::

:::: column

But: Trier les tas.

• 2 <=> max(2, 6, 5).
• 2 <=> max(2, 1, 4).

graph TD;
    id0((6))-->id1((4));
    id0-->id2((5));
    id1-->id3((1));
    id1-->id4((2));

::::

:::

        | 6 | 4 | 5 | 1 | 2 || 8 | 10 | 12 | 16

Exemple de tri par tas (11/N)

        | 6 | 4 | 5 | 1 | 2 || 8 | 10 | 12 | 16

::: columns

:::: column

But: Trier les tas.

• Échanger la racine, 6 (max de l'arbre) avec 2.
• Traiter la racine.

graph TD;
    id0((2))-->id1((4));
    id0-->id2((5));
    id1-->id3((1));
    id1-->id4((  ));
    style id4 fill:#fff,stroke:#fff

::::

:::: column

But: Trier les tas.

• 2 <=> max(2, 4, 5).
• 2 <=> max(2, 1, 4).

graph TD;
    id0((5))-->id1((4));
    id0-->id2((2));
    id1-->id3((1));
    id1-->id4((  ));
    style id4 fill:#fff,stroke:#fff

::::

:::

        | 5 | 4 | 2 | 1 || 6 | 8 | 10 | 12 | 16

Exemple de tri par tas (12/N)

        | 5 | 4 | 2 | 1 || 6 | 8 | 10 | 12 | 16

::: columns

:::: column

But: Trier les tas.

• Échanger la racine, 5 (max de l'arbre) avec 1.
• Traiter la racine.

graph TD;
    id0((1))-->id1((4));
    id0-->id2((2));

::::

:::: column

But: Trier les tas.

• 1 <=> max(1, 4, 2).

graph TD;
    id0((4))-->id1((1));
    id0-->id2((2));

::::

:::

        | 4 | 1 | 2 || 5 | 6 | 8 | 10 | 12 | 16

Exemple de tri par tas (13/N)

        | 4 | 1 | 2 || 5 | 6 | 8 | 10 | 12 | 16

::: columns

:::: column

But: Trier les tas.

• Échanger la racine, 4 (max de l'arbre) avec 2.
• Traiter la racine.

graph TD;
    id0((2))-->id1((1));
    id0-->id2(( ));
    style id2 fill:#fff,stroke:#fff

::::

:::: column

But: Trier les tas. Plus rien à trier

• On fait les 2 dernières étapes en vitesse.
• Échange 2 avec 1.
• Il reste que 1. GGWP!

::::

:::

        | 1 | 2 | 4 | 5 | 6 | 8 | 10 | 12 | 16

Exercice (10min)

• Trier par tas le tableau

        | 1 | 2 | 4 | 5 | 6 | 8 | 10 | 12 | 16

• Mettez autant de détails que possible.
• Que constatez-vous?
• Postez le résultat sur matrix.

L'algorithme du tri par tas (1/4)

\footnotesize

Deux étapes

1. Entassement (tamisage): transformer l'arbre en tas.
2. Échanger la racine avec le dernier élément et entasser la racine.

Pseudo-code d'entassement de l'arbre (5 min, matrix)

. . .

tri_par_tas(tab)
    entassement(tab)
    échanger(tab[0], tab[size(tab)-1])
    pour i = size(tab)-1 à 2 
        promotion(tab, 0)
        échanger(tab[0], tab[i-1])
entassement(tab)
    pour i = size(tab) / 2 - 1 jusqu'à 0
        promotion(tab, i)
promotion(tab, i)
    ind_max = ind_max(tab, i, gauche(i), droite(i))
    si i != ind_max
        échanger(tab[i], tab[ind_max])
        promotion(tab, ind_max)

L'algorithme du tri par tas (2/4)

• Fonctions utilitaires

int ind_max(tab, i, g, d)
    ind_max = i
    si tab[ind_max] < tab[l]
        ind_max = l
    si tab[ind_mx] < tab[r]
        ind_max = r
    retourne ind_max
int gauche(i)
    retourne 2 * i + 1
int droite(i)
    retourne 2 * i + 2

L'algorithme du tri par tas (3/4)

\footnotesize

Implémenter en C l'algorithme du tri par tas (matrix, 20min)

. . .

void heapsort(int size, int tab[size]) {
    heapify(size, tab);
    swap(tab, tab + size - 1);
    for (int s = size - 1; s > 1; s--) {
        sift_up(s, tab, 0);
        swap(tab, tab + s - 1);
    }
}
void heapify(int size, int tab[size]) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        sift_up(size, tab, i);
    }
}
void sift_up(int size, int tab[size], int i) {
    int ind_max = ind_max3(size, tab, i, left(i), right(i));
    if (i != ind_max) {
        swap(tab + i, tab + ind_max);
        sift_up(size, tab, ind_max);
    }
}

L'algorithme du tri par tas (4/4)

\footnotesize

Fonctions utilitaires

. . .

int ind_max3(int size, int tab[size], int i, int l, int r) {
    int ind_max = i;
    if (l < size && tab[ind_max] < tab[l]) {
        ind_max = l;
    }
    if (r < size && tab[ind_max] < tab[r]) {
        ind_max = r;
    }
    return ind_max;
}
void swap(int *a, int *b) {
    int tmp = *a;
    *a      = *b;
    *b      = tmp;
}
int left(int i) {
    return 2 * i + 1;
}
int right(int i) {
    return 2 * i + 2;
}

Complexités

::: columns

:::: column

Complexité de la recherche

1. En moyenne?
2. Dans le pire des cas?

. . .

1. O(\log_2(N))
2. O(N)

::::

:::: column

graph TD;
    id0((10))-->id1((9));
    id0-->id8((  ));
    id1-->id2((7));
    id1-->id9((  ));
    id2-->id3((6));
    id2-->id10((  ));
    id3-->id4((5));
    id3-->id11((  ));
    style id8 fill:#fff,stroke:#fff
    style id9 fill:#fff,stroke:#fff
    style id10 fill:#fff,stroke:#fff
    style id11 fill:#fff,stroke:#fff

::::

:::

Un meilleur arbre

• Quelle propriété doit satisfaire un arbre pour être O(\log_2(N))?

. . .

• Si on a environ le même nombre de noeuds dans les sous-arbres.

Définition

Un arbre binaire est parfaitement équilibré si, pour chaque nœud, la différence entre les nombres de nœuds des sous- arbres gauche et droit vaut au plus 1.

• Si l'arbre est parfaitement équilibré, alors tout ira bien.
• Quelle est la hauteur (profondeur) d'un arbre parfaitement équilibré?

. . .

• O(\log_2(N)).

Équilibre parfait ou pas?

::: columns

:::: column

graph TD;
    id0((W))-->id1((B));
    id0-->id8((Y));
    id1-->id2((A));
    id1-->id9((  ));
    id8-->id10((X));
    id8-->id11((  ));
    style id9 fill:#fff,stroke:#fff
    style id11 fill:#fff,stroke:#fff

::::

:::: column

. . .

É
Q
U
I
L
I
B
R
É

::::

:::

Équilibre parfait ou pas?

::: columns

:::: column

graph TD;
    id0((16))-->id1((10));
    id0-->id2((19));
    id1-->id3((8));
    id1-->id4((12));
    id4-->id5((11));
    id4-->id6((  ));
    id2-->id7((17));
    id2-->id8((  ));
    id7-->id9((  ));
    id7-->id10((18));
    style id6 fill:#fff,stroke:#fff
    style id8 fill:#fff,stroke:#fff
    style id9 fill:#fff,stroke:#fff

::::

:::: column

. . .

P 
A
S 

É
Q
U
I
L
I
B
R
É

::::

:::

Arbres AVL

• Quand est-ce qu'on équilibre un arbre?

. . .

• A l'insertion/suppression.
• Maintenir un arbre en état d'équilibre parfait: cher (insertion, suppression).
• On peut "relaxer" la condition d'équilibre: profondeur (hauteur) au lieu du nombre de neouds:
  • La hauteur \sim\log_2(N).

Définition

Un arbre AVL (Adelson-Velskii et Landis) est un arbre binaire de recherche dans lequel, pour chaque nœud, la différence de hauteur entre le sous-arbre gauche et droit vaut au plus 1.

• Relation entre noeuds et hauteur: \log_2(1+N)\leq 1+H\leq 1.44\cdot\log_2(2+N),\quad N=10^5,\ 17\leq H \leq 25.
• Permet l'équilibrage en temps constant: insertion/suppression O(\log_2(N)).

Notation

• hg: hauteur du sous-arbre gauche.
• hd: hauteur du sous-arbre droit.
• facteur d'équilibre = fe = hd - hg
• Que vaut fe si l'arbre est AVL?

. . .

• fe = {-1, 0, 1}

AVL ou pas?

::: columns

:::: column

graph TD;
    id0((12))-->id1((10));
    id0-->id2((19));
    id2-->id3((17));
    id2-->id4((97));

::::

:::: column

. . .

A
V
L

::::

:::

AVL ou pas?

::: columns

:::: column

graph TD;
    id0((12))-->id1((1));
    id0-->id2((19));
    id2-->id3((17));
    id2-->id4((97));
    id4-->id5((37));
    id4-->id6((  ));
    style id6 fill:#fff,stroke:#fff

::::

:::: column

. . .

P
A
S

A
V
L

::::

:::

Insertion dans un arbre AVL (1/N)

1. On part d'un arbre AVL.
2. On insère un nouvel élément.

::: columns

:::: column

• hd ? hg.
• Insertion de 4?

graph TD;
    id0((12))-->id1((1));
    id0-->id2((19));

::::

:::: column

. . .

• hd = hg

graph TD;
    id0((12))-->id1((1));
    id0-->id2((19));
    id1-->id4((  ));
    id1-->id5((4));
    style id4 fill:#fff,stroke:#fff

• fe = -1

::::

:::

Insertion dans un arbre AVL (2/N)

1. On part d'un arbre AVL.
2. On insère un nouvel élément.

::: columns

:::: column

• hd ? hg.
• Insertion de 4?

graph TD;
    id0((12))-->id1((1));
    id0-->id2((19));
    id2-->id3((18));
    id2-->id4((  ));
    style id4 fill:#fff,stroke:#fff

::::

:::: column

. . .

• hd < hg

graph TD;
    id0((12))-->id1((1));
    id0-->id2((19));
    id2-->id3((18));
    id2-->id4((  ));
    id1-->id5((  ));
    id1-->id6((4));
    style id4 fill:#fff,stroke:#fff
    style id5 fill:#fff,stroke:#fff

• fe = 0

::::

:::

Insertion dans un arbre AVL (3/N)

1. On part d'un arbre AVL.
2. On insère un nouvel élément.

::: columns

:::: column

• hd ? hg.
• Insertion de 4?

graph TD;
    id0((12))-->id1((1));
    id0-->id2((19));
    id1-->id3((  ));
    id1-->id4((6));
    id2-->id5((  ));
    id2-->id6((  ));
    style id3 fill:#fff,stroke:#fff
    style id5 fill:#fff,stroke:#fff
    style id6 fill:#fff,stroke:#fff

::::

:::: column

. . .

• hd > hg

graph TD;
    id0((12))-->id1((1));
    id0-->id2((19));
    id1-->id3((  ));
    id1-->id4((6));
    id4-->id5((4));
    id4-->id6((  ));
    id2-->id7((  ));
    id2-->id8((  ));
    style id3 fill:#fff,stroke:#fff
    style id6 fill:#fff,stroke:#fff
    style id7 fill:#fff,stroke:#fff
    style id8 fill:#fff,stroke:#fff

::::

:::

Déséquilibre! Que vaut fe?

. . .

• fe = 2

Les cas de déséquilibre

::: columns

:::: column

Cas 1a

• u, v, w même hauteur.
• déséquilibre en B après insertion dans u

::::

:::: column

Cas 1a

• Comment rééquilibrer?

. . .

• ramène u, v w à la même hauteur.
• v à droite de A (gauche de B)

::::

:::

Les cas de déséquilibre

::: columns

:::: column

Cas 1b (symétrique 1a)

::::

:::: column

Cas 1b (symétrique 1a)

• Comment rééquilibrer?

. . .

::::

:::

Les cas de déséquilibre

::: columns

:::: column

Cas 2a

• v1, v2, u, w même hauteur.
• déséquilibre en C après insertion dans v2

::::

:::: column

Cas 2a

• Comment rééquilibrer?

. . .

• ramène u, v1, v2, w à la même hauteur.
• v2 à droite de B (gauche de C)
• B à droite de A (gauche de C)
• v1 à droite de A (gauche de B)

::::

:::

Les cas de déséquilibre

::: columns

:::: column

Cas 2b (symétrique 2a)

::::

:::: column

Cas 2b (symétrique 2a)

• Comment rééquilibrer?

. . .

::::

:::

Le facteur d'équilibre (balance factor)

Définition

fe(arbre) = hauteur(droite(arbre)) - hauteur(gauche(arbre))

Valeurs possibles?

. . .

fe = {-1, 0, 1} // arbre AVL
fe = {-2, 2}    // arbre déséquilibré

Algorithme d'insertion

• Insérer le noeud comme d'habitude.
• Mettre à jour les facteurs d'équilibre jusqu'à la racine (ou au premier noeud déséquilibré).
• Rééquilibrer le noeud si nécessaire.

Cas possibles

::: columns

:::: column

Sous-arbre gauche (avant)

fe(P) =  1 
fe(P) =  0 
fe(P) = -1 

::::

:::: column

Sous-arbre gauche (après)

. . .

=> fe(P) =  0 
=> fe(P) = -1 
=> fe(P) = -2 // Rééquilibrer P

::::

:::

Algorithme d'insertion

• Insérer le noeud comme d'habitude.
• Mettre à jour les facteurs d'équilibre jusqu'à la racine (ou au premier noeud déséquilibré).
• Rééquilibrer le noeud si nécessaire.

Cas possibles

::: columns

:::: column

Sous-arbre droit (avant)

fe(P) =  1 
fe(P) =  0 
fe(P) = -1 

::::

:::: column

Sous-arbre droit (après)

. . .

=> fe(P) =  0 
=> fe(P) = +1 
=> fe(P) = +2 // Rééquilibrer P

::::

:::

Rééquilibrage

Lien avec les cas vus plus tôt

fe(P) = -2 && fe(gauche(P)) = -1 => cas 1a
fe(P) = -2 && fe(gauche(P)) = +1 => cas 2a

fe(P) = +2 && fe(gauche(P)) = -1 => cas 1b
fe(P) = +2 && fe(gauche(P)) = +1 => cas 2b

Dessiner les différents cas, sur le dessin ci-dessous