---
title: "Arbres AVL"
date: "2025-03-21"
---

# Exercice (que vous avez dû faire à la maiso)

* 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/2)

\footnotesize

## Deux étapes

1. Entassement: 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 (15 min, matrix)

. . .

```python
rien tri_par_tas(tab)
    entassement(tab)
    échanger(tab[0], tab[size(tab)-1])
    pour i de size(tab)-1 à 2 
        tamisage(tab, 0)
        échanger(tab[0], tab[i-1])

rien entassement(tab)
    pour i de size(tab)/2-1 à 0
        tamisage(tab, i)

rien tamisage(tab, i)
    ind_max = ind_max(tab, i, gauche(i), droite(i))
    si i != ind_max
        échanger(tab[i], tab[ind_max])
        tamisage(tab, ind_max)
```

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

* Fonctions utilitaires

    ```python
    entier ind_max(tab, i, g, d)
        ind_max = i
        si g < size(tab) && tab[ind_max] < tab[g] 
            ind_max = g
        si d < size(tab) > d && tab[ind_max] < tab[d]
            ind_max = d
        retourne ind_max

    entier gauche(i)
        retourne 2 * i + 1
    
    entier 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)

. . .

```C 
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

. . .

```C
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;
}
``` -->




# Les arbres AVL

\Huge Les arbres AVL

# Un meilleur arbre

* Quelle propriété doit satisfaire un arbre pour que la recherche soit $O(\log_2(N))$?

. . .

* Si on a environ le même nombre de nœuds 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

```{.mermaid format=pdf width=400 loc=figs/}
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

```{.mermaid format=pdf width=400 loc=figs/}
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

\footnotesize

* 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 nœuds:
    * 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 nœuds 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

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((12))-->id1((10));
    id0-->id2((19));
    id2-->id3((17));
    id2-->id4((97));
```

::::

:::: column

. . .

```
A
V
L
```

::::

:::

# AVL ou pas?

::: columns

:::: column

```{.mermaid format=pdf width=400 loc=figs/}
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`?

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((12))-->id1((1));
    id0-->id2((19));
```

::::

:::: column

. . .

* `hd = hg`

```{.mermaid format=pdf width=400 loc=figs/}
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`?

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((12))-->id1((1));
    id0-->id2((19));
    id2-->id3((18));
    id2-->id4((  ));
    style id4 fill:#fff,stroke:#fff
```

::::

:::: column

. . .

* `hd < hg`

```{.mermaid format=pdf width=400 loc=figs/}
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)

\footnotesize

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

::: columns

:::: column

* `hd ? hg`.
* Insertion de `4`?

```{.mermaid format=pdf width=400 loc=figs/}
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`

```{.mermaid format=pdf width=400 loc=figs/}
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`

![Après insertion](figs/cas1a_gauche.png)

::::

:::: column

## Cas 1a

* Comment rééquilibrer?

. . .

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

![Après équilibrage](figs/cas1a_droite.png)

::::

:::

# Les cas de déséquilibre


::: columns

:::: column

## Cas 1b (symétrique 1a)

![Après insertion](figs/cas1b_gauche.png)

::::

:::: column

## Cas 1b (symétrique 1a)

* Comment rééquilibrer?

. . .

![Après équilibrage](figs/cas1b_droite.png)

::::

:::

# Les cas de déséquilibre


::: columns

:::: column

## Cas 2a

* `h(v1)=h(v2), h(u)=h(w)`.
* déséquilibre en `C` après insertion dans `v2`

![Après insertion](figs/cas2a_gauche.png)

::::

:::: column

## Cas 2a

* Comment rééquilibrer?

. . .

* ramène `u`, `v2`, `w` à la même hauteur (`v1` pas tout à fait).
* `v2` à droite de `B` (gauche de `C`)
* `B` à droite de `A` (gauche de `C`)
* `v1` à droite de `A` (gauche de `B`)

![Après équilibrage](figs/cas2a_droite.png)

::::

:::


# Les cas de déséquilibre


::: columns

:::: column

## Cas 2b (symétrique 2a)

![Après insertion](figs/cas2b_gauche.png)

::::

:::: column

## Cas 2b (symétrique 2a)

* Comment rééquilibrer?

. . .

![Après équilibrage](figs/cas2b_droite.png)

::::

:::

# 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é
```

![Illustration du `fe`](figs/facteur_equilibre.png){width=40%}

# 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(droite(P)) = -1 => cas 2b
fe(P) = +2 && fe(droite(P)) = +1 => cas 1b
```

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

![On verra un peu après les rotations.](figs/rotation_gauche_droite.png)

# La rotation

## La rotation gauche (5min, matrix)

![L'arbre de droite devient celui de gauche. Comment?](figs/rotation_gauche_droite.png)

. . .

\footnotesize
```
arbre rotation_gauche(arbre P) 
    si est_non_vide(P)
        Q = droite(P)
        droite(P) = gauche(Q)
        gauche(Q) = P
        retourne Q
    retourne P
```

# La rotation en C (1/2)

## La rotation gauche

```
arbre rotation_gauche(arbre P) 
    si est_non_vide(P)
        Q = droite(P)
        droite(P) = gauche(Q)
        gauche(Q) = P
        retourne Q
    retourne P
```

## Écrire le code C correspondant (5min, matrix)

1. Structure de données
2. Fonction `tree_t rotation_left(tree_t tree)`

. . .

\footnotesize
```C
typedef struct _node {
    int key;
    struct _node *left, *right;
    int bf; // balance factor
} node;
typedef node *tree_t;
```

# La rotation en C (2/2)

\footnotesize

```C
tree_t rotation_left(tree_t tree) {
    tree_t subtree = NULL;
    if (NULL != tree) {
        subtree = tree->right;
        tree->right = subtree->left;
        subtree->left = tree;
    }
    return subtree;
}
```

. . .

* Et la rotation à droite, pseudo-code (5min)?

. . .

```
arbre rotation_droite(arbre P) 
    si est_non_vide(P)
        Q = gauche(P)
        gauche(P) = droite(Q)
        droite(Q) = P
        retourne Q
    retourne P
```

<!-- ```C
tree_t rotation_right(tree_t tree) {
    tree_t subtree = NULL;
    if (NULL != tree) {
        subtree = tree->left;
        tree->left = subtree->right;
        subtree->right = tree;
    }
    return subtree;
}
``` -->

# Exemple de rotation (1/2)

## Insertion de 9?

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((5))-->id1((1));
    id0-->id2((6));
    id2-->id3((  ));
    id2-->id4((8));
    style id3 fill:#fff,stroke:#fff
```

# Exemple de rotation (2/2)

::: columns

:::: column

## Quelle rotation et sur quel noeud (5 ou 6)?

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((5))-->id1((1));
    id0-->id2((6));
    id2-->id3((  ));
    id2-->id4((8));
    id4-->id5((  ));
    id4-->id6((9));
    style id3 fill:#fff,stroke:#fff
    style id5 fill:#fff,stroke:#fff
```

::::

:::: column

. . .

## Sur le plus jeune évidemment!

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((5))-->id1((1));
    id0-->id2((8));
    id2-->id3((6));
    id2-->id4((9));
```

::::

:::

* Cas `1a/b` *check*!


# La rotation gauche-droite

## Là c'est plus difficile (cas 2a/b)

![La double rotation de l'enfer.](figs/double_rotation_gauche_droite.png)

# Exercices

## Faire l'implémentation de la double rotation (pas corrigé, 5min)

# Exercices

::: columns

:::: column

## Insérer 50, ex 10min (matrix)

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((89))-->id1((71));
    id0-->id2((90));
    id1-->id3((44));
    id3-->id4((37));
    id3-->id5((61));
    id1-->id6((81))
    id2-->id7((  ))
    id2-->id8((100))
    style id7 fill:#fff,stroke:#fff
```

::::

:::: column

. . .

## Où se fait la rotation?

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((89))-->id1((71));
    id0-->id2((90));
    id1-->id3((44));
    id3-->id4((37));
    id3-->id5((61));
    id1-->id6((81))
    id2-->id7((  ))
    id2-->id8((100))
    id5-->id9((50))
    id5-->id10((  ))
    style id7 fill:#fff,stroke:#fff
    style id10 fill:#fff,stroke:#fff
```

::::

:::

# Exercices

::: columns

:::: column

## Rotation gauche en 44

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((89))-->id1((71));
    id0-->id2((90));
    id1-->id3((61));
    id1-->id10((81));
    id3-->id4((44));
    id3-->id5((  ));
    id4-->id6((37))
    id4-->id7((50))
    id2-->id8((  ))
    id2-->id9((100))
    style id5 fill:#fff,stroke:#fff
    style id8 fill:#fff,stroke:#fff
```

::::

:::: column

. . .

## Rotation à droite en 71

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((89))-->id1((61));
    id0-->id2((90));
    id1-->id3((44));
    id1-->id10((71));
    id3-->id4((37));
    id3-->id5((50));
    id2-->id8((  ));
    id2-->id9((100));
    id10-->id11((  ))
    id10-->id12((81))
    style id8 fill:#fff,stroke:#fff
    style id11 fill:#fff,stroke:#fff
```

::::

:::

# Exercice de la mort

Soit l’arbre AVL suivant:

::: columns

:::: column

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((60))-->id1((40));
    id0-->id2((120));
    id1-->id3((20));
    id1-->id4((50));
    id3-->id5((10));
    id3-->id6((30));
    id2-->id7((100));
    id2-->id8((140));
    id7-->id9((80))
    id7-->id10((110))
    id9-->id11((70))
    id9-->id12((90))
    id8-->id13((130))
    id8-->id14((160))
    id14-->id15((150))
    id14-->id16((170))
```

::::

:::: column

1. Montrer les positions des insertions de feuille qui conduiront à un arbre
   désequilibré.
2. Donner les facteurs d’equilgaucheibre.
3. Dessiner et expliquer les modifications de l’arbre lors de l’insertion de la
   valeur `65`. On mentionnera les modifications des facteurs
   d’équilibre.

::::

:::

# Encore un petit exercice

* Insérer les nœuds suivants dans un arbre AVL

```
25 | 60 | 35 | 10 | 5 | 20 | 65 | 45 | 70 | 40 
    | 50 | 55 | 30 | 15
```

## Un à un et le/la premier/ère qui poste la bonne réponse sur matrix a un point

# Suppression dans un arbre AVL


::: columns

:::: column

## Algorithme par problème: supprimer 10

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((8))-->id1((4));
    id0-->id2((10));
    id1-->id3((2));
    id1-->id4((6));
    id3-->id5((1));
    id3-->id6((  ))
    id4-->id7((  ))
    id4-->id8((7))
    id2-->id9((9))
    id2-->id10((14))
    id10-->id11((12))
    id10-->id12((16))
    style id6 fill:#fff,stroke:#fff
    style id7 fill:#fff,stroke:#fff
```

::::

:::: column

. . .

## Algorithme par problème: supprimer 10

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((8))-->id1((4));
    id0-->id2((12));
    id1-->id3((2));
    id1-->id4((6));
    id3-->id5((1));
    id3-->id6((  ))
    id4-->id7((  ))
    id4-->id8((7))
    id2-->id9((9))
    id2-->id10((14))
    id10-->id11((  ))
    id10-->id12((16))
    style id6 fill:#fff,stroke:#fff
    style id7 fill:#fff,stroke:#fff
    style id11 fill:#fff,stroke:#fff
```

::::

:::

# Suppression dans un arbre AVL


::: columns

:::: column

## Algorithme par problème: supprimer 8

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((8))-->id1((4));
    id0-->id2((12));
    id1-->id3((2));
    id1-->id4((6));
    id3-->id5((1));
    id3-->id6((  ))
    id4-->id7((  ))
    id4-->id8((7))
    id2-->id9((9))
    id2-->id10((14))
    id10-->id11((  ))
    id10-->id12((16))
    style id6 fill:#fff,stroke:#fff
    style id7 fill:#fff,stroke:#fff
    style id11 fill:#fff,stroke:#fff
```

::::

:::: column

. . .

## Algorithme par problème: rotation de 12

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((9))-->id1((4));
    id0-->id2((12));
    id1-->id3((2));
    id1-->id4((6));
    id3-->id5((1));
    id3-->id6((  ))
    id4-->id7((  ))
    id4-->id8((7))
    id2-->id9((  ))
    id2-->id10((14))
    id10-->id11((  ))
    id10-->id12((16))
    style id6 fill:#fff,stroke:#fff
    style id7 fill:#fff,stroke:#fff
    style id9 fill:#fff,stroke:#fff
    style id11 fill:#fff,stroke:#fff
```

::::

:::

# Suppression dans un arbre AVL

::: columns

:::: column

## Algorithme par problème: rotation de 12

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((9))-->id1((4));
    id0-->id2((14));
    id1-->id3((2));
    id1-->id4((6));
    id3-->id5((1));
    id3-->id6((  ))
    id4-->id7((  ))
    id4-->id8((7))
    id2-->id9((12))
    id2-->id10((16))
    style id6 fill:#fff,stroke:#fff
    style id7 fill:#fff,stroke:#fff
```

::::

:::: column

. . .

1. On supprime comme d'habitude.
2. On rééquilibre si besoin à l'endroit de la suppression.

* Facile non?

. . .

* Plus dur....

::::

:::

# Suppression dans un arbre AVL 2.0

::: columns

:::: column

## Algorithme par problème: suppression de 30

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((50))-->id1((30));
    id0-->id2((100));
    id1-->id3((10));
    id1-->id4((40));
    id3-->id5((  ));
    id3-->id6((20))
    id2-->id7((80))
    id2-->id8((200))
    id7-->id9((70))
    id7-->id10((90))
    id9-->id11((60))
    id9-->id12((  ))
    id8-->id13((  ))
    id8-->id14((300))
    style id5 fill:#fff,stroke:#fff
    style id12 fill:#fff,stroke:#fff
    style id13 fill:#fff,stroke:#fff
```

::::

:::: column

. . .

## Algorithme par problème: rotation GD autour de 40

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((50))-->id1((40));
    id0-->id2((100));
    id1-->id3((10));
    id1-->id4((  ));
    id3-->id5((  ));
    id3-->id6((20))
    id2-->id7((80))
    id2-->id8((200))
    id7-->id9((70))
    id7-->id10((90))
    id9-->id11((60))
    id9-->id12((  ))
    id8-->id13((  ))
    id8-->id14((300))
    style id4 fill:#fff,stroke:#fff
    style id5 fill:#fff,stroke:#fff
    style id12 fill:#fff,stroke:#fff
    style id13 fill:#fff,stroke:#fff
```

::::

:::

# Suppression dans un arbre AVL 2.0

::: columns

:::: column

## Argl! 50 est déséquilibré!

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((50))-->id1((20));
    id0-->id2((100));
    id1-->id3((10));
    id1-->id4((40));
    id2-->id7((80))
    id2-->id8((200))
    id7-->id9((70))
    id7-->id10((90))
    id9-->id11((60))
    id9-->id12((  ))
    id8-->id13((  ))
    id8-->id14((300))
    style id12 fill:#fff,stroke:#fff
    style id13 fill:#fff,stroke:#fff
```

::::

:::: column

. . .

## Algorithme par problème: rotation DG autour de 50

```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    id0((80))-->id1((50));
    id0-->id2((100));
    id1-->id3((20));
    id1-->id4((70));
    id3-->id5((10));
    id3-->id6((40));
    id4-->id9((60))
    id4-->id10((  ))
    id2-->id7((90))
    id2-->id8((200))
    id8-->id13((  ))
    id8-->id14((300))
    style id10 fill:#fff,stroke:#fff
    style id13 fill:#fff,stroke:#fff
```

::::

:::

# Résumé de la suppression

1. On supprime comme pour un arbre binaire de recherche.
2. Si un nœud est déséquilibré, on le rééquilibre.
    * Cette opération peut déséquilibrer un autre nœud.
3. On continue à rééquilibrer tant qu'il y a des nœuds à équilibrer.
