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