cours_18.md

title: "Tri par tas et arbres AVL"
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

• Qu'est-ce qu'un arbre AVL?

. . .

• Un arbre binaire qui a la propriété suivante:
  • La différence de hauteur de chaque noeud est d'au plus 1.
  • Tous les noeuds ont fe = hd - hg = {-1, 0, 1}.

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?

graph TD;
    id0((12))-->id1((1));
    id0-->id2((19));

::::

:::: column

. . .

• hd = hg

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?

graph TD;
    id0((12))-->id1((1));
    id0-->id2((19));
    id2-->id3((18));
    id2-->id4((  ));
    style id4 fill:#fff,stroke:#fff

::::

:::: column

. . .

• hd < hg

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)

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

::: columns

:::: column

• hd ? hg.
• Insertion de 4?

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

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

::::

:::: column

Cas 1a

• Comment rééquilibrer?

. . .

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

::::

:::

Les cas de déséquilibre

::: columns

:::: column

Cas 1b (symétrique 1a)

::::

:::: column

Cas 1b (symétrique 1a)

• Comment rééquilibrer?

. . .

::::

:::

Les cas de déséquilibre

::: columns

:::: column

Cas 2a

• v1, v2, u, w même hauteur.
• déséquilibre en C après insertion dans v2

::::

:::: column

Cas 2a

• Comment rééquilibrer?

. . .

• ramène u, v1, v2, w à la même hauteur.
• v2 à droite de B (gauche de C)
• B à droite de A (gauche de C)
• v1 à droite de A (gauche de B)

::::

:::

Les cas de déséquilibre

::: columns

:::: column

Cas 2b (symétrique 2a)

::::

:::: column

Cas 2b (symétrique 2a)

• Comment rééquilibrer?

. . .

::::

:::

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é

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

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