---
title: "Arbres AVL et arbres quaternaires"
date: "2025-03-28"
---

# Rappel: 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.

# Rappel: 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)

::::

:::

# Rappel: 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)

::::

:::

# Rappel: Rééquilibrage

## Rotation simple

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

# Rappel: La rotation gauche-droite

## Le cas 2a/b

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

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

```










```

# La suppression dans un arbre AVL

\Huge La suppression dans un arbre AVL

# 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 sur le chemin menant au noeud supprimé.
3. On continue à rééquilibrer tant qu'il y a des nœuds à équilibrer en remontant le chemin.


# Les arbres quaternaires

\Huge Les arbres quaternaires


# Les arbres quaternaires

## Définition

Arbre dont chaque nœud a 4 enfants ou aucun. 

![Un exemple d'arbre quaternaire.](figs/quad_ex.svg)

# Les arbres quaternaires

## Cas d'utilisation

Typiquement utilisés pour représenter des données bidimensionnelles.

Son équivalent tri-dimensionnel est l'octree (chaque nœud a 8 enfants ou aucun).

## Cas d'utilisation: images

* Stockage: compression.
* Transformations: symétries, rotations, etc.

## Cas d'utilisation: simulation

* Indexation spatiale.
* Détection de collisions.
* Simulation de galaxies (algorithme de Barnes-Hut).

# Exemple de compression

::: columns

:::: {.column width=30%}

## Comment représenter l'image

![Image noir/blanc.](figs/board_blacked_parts.svg)

::::

:::: {.column width=70%}

## Sous la forme d'un arbre quaternaire?

. . .

![L'arbre quaternaire correspondant.](figs/quad_img.svg)

**Économie?**

. . .

Image 64 pixels, arbre 25 nœuds.

::::

:::


# Structure de données

::: columns

:::: {.column width=50%}

## Pseudo-code?

. . .

```python
struct node
    info
    node sup_gauche, sup_droit,
         inf_gauche, inf_droit
```

![Un nœud d'arbre quaternaire.](figs/quad_struct.svg)

::::

:::: {.column width=50%}

## En C?

. . .

```C
struct _node {
    int info;
    struct _node *sup_left;
    struct _node *sup_right;
    struct _node *inf_left;
    struct _node *inf_right;
};
```

* Pourquoi le `*` est important?

. . .

* Type récursif => taille inconnue à la compilation.

::::

:::

# Une fonctionnalité simple

\footnotesize

## La fonction `est_feuille(noeud)`

* Problème avec cette implémentation?

```python
bool est_feuille(noeud) 
    retourne
        est_vide(sup_gauche(noeud)) &&
        est_vide(sup_droit(noeud))  &&
        est_vide(inf_gauche(noeud)) &&
        est_vide(inf_droit(noeud))
```

. . .

* Inutile d'avoir 4 conditions (soit 4 enfants soit aucun!)
* Facile d'en oublier un!
* Comment changer la structure pour que ça soit moins terrible?

. . .

```python
struct node
    info
    node enfant[4]
```

# Structure de données

## En C?

. . .

```C 
typedef struct _node {
    int info;
    struct _node *child[4];
} node;
```

## Fonction `is_leaf(node *tree)`?

. . .

```C 
bool is_leaf(node *tree) {
    return (NULL == tree->child[0]); // only first matters
}
```

# Problème à résoudre

* Construire un arbre quaternaire à partir d'une image:
    * Créer l'arbre (allouer la mémoire pour tous les nœuds)
    * Remplir l'arbre avec les valeurs des pixels
* Compression de l'image:
    * Si les pixels sont les mêmes dans le quadrant on supprime le sous-arbre (sans perte)
    * Si les pixels ne dévient pas trop, on supprime le quadrant (avec perte)

# Création de l'arbre

## Comment créer un arbre de profondeur `prof` (3min)?

. . .

```python
arbre creer_arbre(prof)
    n = nouveau_noeud() # alloue la mémoire
    si prof > 0
        pour i = 0 à 3
            n.enfant[i] = creer_arbre(prof-1)
    retourne n
```

## En `C` (3 min, matrix)?

. . .

```C
node *qt_create(int depth) {
    node *n = calloc(1, sizeof(node));
    if (depth > 0) {
        for (int i = 0; i < 4; ++i) {
            n->child[i] = qt_create(depth-1);
        }
    }
    return n;
}
```

# Le nombre de nœuds?

## Comment implémenter la fonction (pseudo-code, 5min, matrix)?

. . .

```C
entier nombre_nœuds(arbre)
    si est_feuille(arbre)
        retourne 1
    sinon
        somme = 1
        pour i de 0 à 3
            somme += nombre_nœuds(arbre.enfant[i])
        retourne somme
```

# Le nombre de nœuds?

## Comment implémenter la fonction en C (3min, matrix)?

. . .

```C
int size(node *qt) {
    if (is_leaf(qt)) {
        return 1;
    } else {
        int sum = 1;
        for (int i = 0; i < 4; ++i) {
            sum += size(qt->child[i]);
        }
        return sum;
    }
}
```

# La profondeur en C?

## Implémentation (5min, matrix)

. . .

\footnotesize

```C
int max(int x, int y) {
   return  (x >= y ? x : y);
}
int max_depth(int depths[4]) {
    int m = depths[0];
    for (int i = 1; i < 4; ++i) {
        m = max(m, depths[i]);
    }
    return m;
}
int depth(node *qt) {
    int depths[] = {0, 0, 0, 0};
    if (is_leaf(qt)) {
        return 0;
    } else {
        for (int i = 0; i < 4; ++i) {
            depths[i] = depth(qt->child[i]);
        }
        return 1 + max_depth(depths);
    }
}
```

# Fonctions utiles (1/4)

## Comment remplir un arbre depuis une matrice?

```
   SG=0  |  SD=1
 21 | 12 | 4 |  4
  9 |  7 | 4 |  4
-----------------
  1 |  1 | 0 | 31
  1 |  1 | 3 | 27
   IG=2  |  ID=3
```

## Quel arbre cela représente?

. . .

![L'arbre correspondant](figs/quad_img_simple.svg)

# Fonctions utiles (2/4)

* On veut transférer la valeur d'une case ligne/colonne dans une feuille.
* Comment?

::: columns

:::: {.column width=40%}

## Soit `ligne=2`, `colonne=3`

```
   SG=0  |  SD=1
 21 | 12 | 4 |  4
  9 |  7 | 4 |  4
-----------------
  1 |  1 | 0 | 31
  1 |  1 | 3 | 27
   IG=2  |  ID=3
```

::::

:::: {.column width=70%}

## Trouver un algorithme

![Déterminer un algorithme.](figs/quad_img_simple.svg)

* Quelle feuille pour 31 (`li=2`, `co=3`)?
* Plus important: quel chemin?

. . .

* `co -> G/D`, `li -> S/I`,
* `2 * (li / 2) + co / 2 -> 2 * 1 + 1 = 3`
* `2 * ((li % 2) / 1) + (co % 2) / 1 -> 2 * 0 + 1 = 1`
* Comment généraliser?

::::

:::

# Fonctions utiles (3/4)

::: columns

:::: {.column width=40%}

## Soit `ligne=2`, `colonne=3`

```
   SG=0  |  SD=1
 21 | 12 | 4 |  4
  9 |  7 | 4 |  4
-----------------
  1 |  1 | 0 | 31
  1 |  1 | 3 | 27
   IG=2  |  ID=3
```

::::

:::: {.column width=70%}

## Trouver un algorithme (prendre plusieurs exemples, 15min, matrix)

![Déterminer un algorithme.](figs/quad_img_simple.svg)

* Comment généraliser?

. . .

```C
noeud position(li, co, arbre)
    d = profondeur(arbre);
    tant_que (d >= 1)
        index = 2 * ((li % 2^d) / 2^(d-1)) +
            (col % 2^d) / 2^(d-1)
        arbre = arbre.enfant[index]
        d -= 1
    retourne arbre
```


::::

:::

# Fonctions utiles (4/4)

\footnotesize

## Pseudo-code

```C
noeud position(li, co, arbre)
    d = profondeur(arbre);
    tant_que (d >= 1)
        index = 2 * ((li % 2^d) / 2^(d-1)) +
            (col % 2^d) / 2^(d-1)
        arbre = arbre.enfant[index]
        d -= 1
    retourne arbre
```

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

```C











```

# Remplir l'arbre

## A partir d'une matrice (pseudo-code, 5min, matrix)?

. . .

```C
arbre matrice_vers_arbre(matrice)
    arbre = creer_arbre(profondeur)
    pour li de 0 à nb_lignes(matrice)
        pour co de 0 à nb_colonnes(matrice)
            noeud = position(li, co, arbre)
            noeud.info = matrice[co][li]
    retourne arbre
```

. . .

## A partir d'une matrice (C, 5min, matrix)?

. . .

\footnotesize

```C
node *matrix_to_qt(int nb_li, int nb_co, int matrix[nb_li][nb_co], int depth) {
    node *qt = qt_create(depth);
    for (int li = 0; li < nb_li; ++li) {
        for (int co = 0; co < nb_co; ++co) {
            node *current = position(li, co, qt);
            current->info = matrix[li][co];
        }
    }
    return qt;
}
```


# Remplir la matrice

## A partir de l'arbre (pseudo-code, 3min, matrix)?

. . .

\footnotesize

```C
matrice arbre_vers_matrice(arbre)
    matrice = creer_matrice(nb_lignes(arbre), nb_colonnes(arbre))
    pour li de 0 à nb_lignes(matrice)
        pour co de 0 à nb_colonnes(matrice)
            noeud = position(li, co, arbre)
            matrice[co][li] = noeud.info
    retourne matrice
```

. . .

## A partir de l'arbre (C, 3min, matrix)?

. . .

\footnotesize

```C
void qt_to_matrix(node *qt, int nb_li, int nb_co, int matrix[nb_li][nb_co]) {
    for (int li = 0; li < nb_li; ++li) {
        for (int co = 0; co < nb_co; ++co) {
            node *current = position(li, co, qt);
            matrix[li][co] = current->info;
        }
    }
}
```


