---
title: "Arbres AVL et quadtrees"
date: "2022-03-23"
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

## Quel est l'algorithme d'insertion dans un arbre AVL?

. . .

* Insertion comme dans un arbre binaire de recherche.
* Rééquilibrage si le facteur d'équilibre est de -2 ou +2.

## Quelles sont les briques élémentaires du rééquilibrage?

. . .

* La rotation gauche ou droite.

# 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 pour déséquilibrer un autre nœud.
3. On continue à rééquilibrer tant qu'il y a des nœuds à équilibrer.

# Les arbres quaternaires

## Définition

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

![Un exemple de quadtree.](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, 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 neouds.

::::

:::