cours_19.md

title: "Arbres AVL et quadtrees"
date: "2022-03-16"
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 à un point

Suppression dans un arbre AVL

::: columns

:::: column

Algorithme par problème: supprimer 10

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

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

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

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

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

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

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é!

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

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.

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

::::

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

Sous la forme d'un arbre quaternaire?

. . .

Économie?

. . .

Image 64 pixels, arbre 25 neouds.

::::

:::

Structure de données

::: columns

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

Pseudocode?

. . .

struct node
    info
    node sup_gauche, sup_droit,
        inf_gauche, inf_droit

::::

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

En 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?

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?

. . .

struct node
    info
    node enfant[4]

Structure de données

En C?

. . .

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

Fonction is_leaf(node *tree)?

. . .

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),
  • Le remplir 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 dévident pas trop on supprime le quadrant (avec perte)

Fonctions utiles (1/N)

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

. . .

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)?

. . .

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

Fonctions utiles (2/N)

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?

. . .

Fonctions utiles (3/N)

• On veut transformer une ligne/colonne en 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

• Quelle feuille?
• 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 (4/N)

::: 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

• Comment généraliser?

. . .

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
    retourn arbre

::::

:::

Remplir l'arbre

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

. . .

arbre matrice_à_arbre(matrice, arbre)
    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)?

node *matrice_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 < nd_li; ++li) {
        for (int co = 0; co < nd_co; ++co) {
            node *current = position(li, co, qt);
            current->info = matrix[li][co];
        }
    }
    return qt;

Interface

Quelles sont les fonctions à implémenter?

Implémentation