---
title: "Arbres"
date: "2022-02-23"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto
---

# Les arbres: définition

"Un arbre est un graphe acyclique orienté possédant une unique racine, et tel que tous les nœuds sauf la racine ont un unique parent."

. . .

**Santé!**

## Plus sérieusement

* Ensemble de **noeuds** et d'**arêtes** (graphe),
* Les arêtes relient les noeuds entre eux, mais pas n'importe comment: chaque
  noeud a au plus un **parent**,
* Le seul noeud sans parent est la **racine**,
* Chaque noeud a un nombre fini de **fils**,
* La hiérarchie des noeuds rend les arêtes **orientées** (parent -> fils), et empêche les
  **cycles** (acyclique, orienté).
* La **feuille** ou **noeud terminal** est un noeud sans enfants,
* Le **niveau** est 1 à la racine et **niveau+1** pour les fils,
* Le **degré** d'un noeud est le nombre de fils du noeud.

. . .

* Chaque noeud est un arbre en lui même.
* La **récursivité** sera très utile!


# Arbre ou pas arbre?

::: columns

:::: column
```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    1-->2;
    1-->3;
    3-->2;
    3-->4;
    3-->5;
```
::::

. . .

:::: column
```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    1-->2;
    1-->3;
    3-->4;
    3-->5;
    3-->6;
```
::::

:::

# Arbre ou pas arbre?

::: columns

:::: column
```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    1-->2;
    1-->3;
    3-->4;
    3-->5;
    3-->6;
    6-->7;
    7-->3;
```
::::

. . .

:::: column
```{.mermaid format=pdf width=300 loc=figs/}
graph TD;
    1;
```
::::

:::

# Arbre ou pas arbre?

::: columns

:::: column
```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    1---2;
    1---3;
    3---4;
    3---5;
```
::::

. . .

:::: column
```{.mermaid format=pdf width=300 loc=figs/}
graph BT;
    1-->2;
    1-->3;
    3-->4;
    3-->5;
    3-->6;
```
::::

:::

# Degré et niveau

* Illustration du degré (nombre de fils) et du niveau (profondeur)

::: columns

:::: column
```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    1[degré 2]-->2[degré 0];
    1-->3[degré 3];
    3-->4[degré 0];
    3-->5[degré 0];
    3-->6[degré 0];
```
::::

. . .

:::: column
```{.mermaid format=pdf width=300 loc=figs/}
graph TD;
    1[niveau 1]-->2[niveau 2];
    1-->3[niveau 2];
    3-->4[niveau 3];
    3-->5[niveau 3];
    3-->6[niveau 3];
```
::::

:::

* Les noeuds de degré 0, sont des feuilles.

# Application: recherche rapide

## Pouvez vous construire un arbre pour résoudre le nombre secret?

 . . .

* Le nombre secret ou la recherche dychotomique (nombre entre 0 et 10).

::: columns

:::: column
```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    5-->|<|2;
    5-->|>|7;
    7-->|>|8;
    7-->|<|6;
    8-->|>|9;
    9-->|>|10;
    2-->|<|1;
    2-->|>|3;
    3-->|>|4;
    1-->|<|0;
```
::::

:::: column

**Question:** Quelle est la complexité pour trouver un nombre?

::::

:::

# Autres représentation

* Botanique
* **Exercice:** Ajouter les degrés/niveaux et feuilles

```{.mermaid width=250 format=pdf loc=figs/}
graph TD;
    A-->B;
    A-->C;
    B-->D;
    B-->E;
    B-->F;
    F-->I;
    F-->J;
    C-->G;
    C-->H;
    H-->K;
```

# Autres représentation

* Ensembliste

::: columns

:::: column
```{.mermaid width=300 format=pdf loc=figs/}
graph TD;
    A-->B;
    A-->C;
    B-->D;
    B-->E;
    B-->F;
    F-->I;
    F-->J;
    C-->G;
    C-->H;
    H-->K;
```
::::

. . .

:::: column
![](figs/ensemble.svg)
::::

:::

# Autres représentation

* Liste

::: columns

:::: column
```{.mermaid width=400 format=pdf loc=figs/}
graph TD;
    A-->B;
    A-->C;
    B-->D;
    B-->E;
    B-->F;
    F-->I;
    F-->J;
    C-->G;
    C-->H;
    H-->K;
```
::::

. . .

:::: column
```
(A 
    (B 
        (D) 
        (E) 
        (F 
            (I) 
            (J)
        )
    ) 
    (C
        (G) 
        (H 
            (K)
        )
    )
)
```
::::

:::

# Autres représentation

* Par niveau

::: columns

:::: column
```{.mermaid width=400 format=pdf loc=figs/}
graph TD;
    A-->B;
    A-->C;
    B-->D;
    B-->E;
    B-->F;
    F-->I;
    F-->J;
    C-->G;
    C-->H;
    H-->K;
```
::::

. . .

:::: column
```
1       2       3       4
-------------------------
A       
        B       
                D 
                E 
                F           
                        I
                        J
        C       
                G
                H
                        K
```
::::

:::

# L'arbre binaire

* Structure de données abstraite,
* Chaque noeud a au plus deux fils: gauche et droite,
* Chaque fils est un arbre.

## Comment représenteriez vous une telle structure?

. . .

```C
<R, G, D>
    R: racine
    G: sous-arbre gauche
    D: sous-arbre droite
```

## Comment cela s'écrirait en C?

. . .

```C
typedef struct _node {
    contenu info;
    struct _node *left, *right;
} node;
typedef node *tree;
```

# L'arbre binaire

## Que se passerait-il avec 

```C
typedef struct _node {
    int info;
    struct _node left, right;
} node;
```

* On ne sait pas quelle est la taille de node, on ne peut pas l'allouer!

## Interface minimale

* Qu'y mettriez vous?

. . .

```C 
NULL              -> arbre (vide)
<n, arbre, arbre> -> arbre
visiter(arbre)     -> noeud (la racine de l'arbre)
gauche(arbre)     -> arbre (sous-arbre de gauche)
droite(arbre)     -> arbre (sous-arbre de droite)
```

* Les autres opérations (insertion, parcours, etc) dépendent de ce qu'on stocke
  dans l'arbre.

# Exemple d'arbre binaire

* Représentez `(c - a * b) * (d + e / f)` à l'aide d'un arbre binaire (matrix)

. . .

::: columns

:::: column
```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    A[*]-->B[-];
    B-->C[c];
    B-->D[*];
    D-->E[a];
    D-->F[b];
    A-->G[+];
    G-->H[d];
    G-->I["/"];
    I-->J[e];
    I-->K[f];
```
::::


:::: column

## Remarques

* L'arbre est **hétérogène**: le genre d'info est pas le même sur chaque noeud
  (opérateur, opérande).
    * Les feuilles contiennent les opérandes.
    * Les noeuds internes contiennent les opérateurs.

::::

:::

# Parcours d'arbres binaires

* Appliquer une opération à tous les noeuds de l'arbre,
* Nécessité de **parcourir** l'arbre,
* Utiliser uniquement l'interface: visiter, gauche,
  droite.

## Une idée de comment parcourir cet arbre?

* 3 parcours (R: Racine, G: sous-arbre gauche, D: sous-arbre droit):


::: columns

:::: column
```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    A[*]-->B[-];
    B-->C[c];
    B-->D[*];
    D-->E[a];
    D-->F[b];
    A-->G[+];
    G-->H[d];
    G-->I["/"];
    I-->J[e];
    I-->K[f];
```
::::

:::: column

1. Pacrours **préfixe** (R, G D),
2. Parcours **infixe** (G, R, D),
3. Parcours **postfixe** (G, D, R).

::::

:::

# Le parcours infixe (G, R, D)

* Gauche, Racine, Droite:
    1. On descend dans l'arbre de gauche tant qu'il est pas vide,
    2. On visite la racine du sous arbre,
    3. On descend dans le sous-arbre de droite (s'il est pas vide),
    4. On recommence.

. . .

## Incompréhensible?

* La récursivité c'est la vie.
    
```
parcours_infixe(arbre a)
    si est_pas_vide(gauche(a))
       parcours_infixe(gauche(a))
    visiter(A)
    si est_pas_vide(droite(A))
       parcours_infixe(droite(A))
```

# Graphiquement (dessinons)

::: columns

:::: column
```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    A[*]-->B[-];
    B-->C[c];
    B-->D[*];
    D-->E[a];
    D-->F[b];
    A-->G[+];
    G-->H[d];
    G-->I["/"];
    I-->J[e];
    I-->K[f];
```
::::

:::: column

```
parcours_infixe(arbre a)
    si est_pas_vide(gauche(a))
       parcours_infixe(gauche(a))
    visiter(A)
    si est_pas_vide(droite(A))
       parcours_infixe(droite(A))
```

::::

:::


# Graphiquement (`mermaid` c'est super)

::: columns

:::: column
```{.mermaid format=pdf width=400 loc=figs/}
graph TD;
    A[*]-->B[-];
    A[*]-.->|1|B[-];
    B-->C[c];
    B-.->|2|C[c];
    C-.->|3|B;
    B-->D[*];
    B-.->|4|D;
    D-->E[a];
    D-.->|5|E;
    E-.->|6|D;
    D-->F[b];
    D-.->|7|F;
    F-.->|8|A;
    A-->G[+];
    A-.->|9|G;
    G-->H[d];
    G-.->|10|H;
    H-.->|11|G;
    G-->I["/"];
    G-.->|12|I;
    I-->J[e];
    I-.->|13|J;
    J-.->|14|I;
    I-->K[f];
    I-.->|15|K;
```
::::

:::: column

```
parcours_infixe(arbre a)
    si est_pas_vide(gauche(a))
       parcours_infixe(gauche(a))
    visiter(A)
    si est_pas_vide(droite(A))
       parcours_infixe(droite(A))
```

## Remarque 

Le noeud est visité à la **remontée**.

## Résultat

```
c - a * b * d + e / f
```

::::

:::

# Et en C?

## Live code

\footnotesize

. . .

```C
typedef int data;
typedef struct _node {
    data info;
    struct _node* left;
    struct _node* right;
} node;
typedef node* tree_t;
void tree_print(tree_t tree, int n) {
    if (NULL != tree) {
        tree_print(tree->left, n+1);
        for (int i = 0; i < n; i++) {
            printf(" ");
        }
        printf("%d\n", tree->info);
        tree_print(tree->right, n+1);
    }
}
```

# Question

## Avez-vous compris le fonctionnement?

. . .

## Vous en êtes sûr·e·s?

. . .

## OK, alors deux exercices:

1. Écrire le pseudo-code pour le parcours R, G, D (matrix).
2. Écrire le pseudo-code pour la parcours G, D, R (matrix),

## Rappel

```
parcours_infixe(arbre a)
    si est_pas_vide(gauche(a))
       parcours_infixe(gauche(a))
    visiter(A)
    si est_pas_vide(droite(A))
       parcours_infixe(droite(A))
```

# Correction

\footnotesize

* Les deux parcours sont des modifications **triviales**[^1] de l'algorithme
  infixe.

## Le parcours postfixe

```python
parcours_postfoxe(arbre a)
    si est_pas_vide(gauche(a))
       parcours_postfixe(gauche(a))
    si est_pas_vide(droite(a))
       parcours_postfixe(droite(a))
    visiter(a)
```

## Le parcours préfixe

```python
parcourx_préfixe(arbre a)
    visiter(a)
    si est_pas_vide(gauche(a))
        parcours_préfixe(gauche(a))
    si est_pas_vide(droite(a))
        parcours_préfixe(droite(a))
```

. . .

**Attention:** L'implémentation de ces fonctions en C sont **à faire** en
exercice (inspirez vous de ce qu'on a fait avant)!

# Exercice: parcours

## Comment imprimer l'arbre ci-dessous?

```
                        f
                /
                        e
        +
                d
*
                c
        -
                        b
                *
                        a
```

. . .

## Bravo vous avez trouvé! 

* Il s'agissait du parcours D, R, G.

# Implémentation

## Vous avez 5 min pour implémenter cette fonction et la poster sur matrix!

. . .

```C 
void pretty_print(tree_t tree, int n) {
    if (NULL != tree) {
        pretty_print(tree->right, n+1);
        for (int i = 0; i < n; ++i) {
            printf(" ");
        }
        printf("%d\n", tree->info);
        pretty_print(tree->left);
    }
}
```

# Exercice supplémentaire (sans corrigé)

Écrire le code de la fonction 

```C
int depth(tree_t t);
```

qui retourne la profondeur maximale d'un arbre.

Indice: la profondeur à chaque niveau peut-être calculée à partir du niveau des
sous-arbres de gauche et de droite.

# La recherche dans un arbre binaire

* Les arbres binaires peuvent retrouver une information très rapidement.
* À quelle complexité? À quelle condition?

. . .

## Condition

* Le contenu de l'arbre est **ordonné** (il y a une relation d'ordre (`<`, `>`
  entre les éléemts).

## Complexité

* La profondeur de l'arbre (ou le $\mathcal{O}(\log_2(N))$)

. . .

## Exemple: les arbres lexicographiques

* Chaque noeud contient une information de type ordonné, la **clé**,
* Par construction, pour chaque noeud $N$:
    * Toutes clé du sous-arbre à gauche de $N$ sont inférieurs à la clé de $N$.
    * Toutes clé du sous-arbre à droite de $N$ sont inférieurs à la clé de $N$.

# Algorithme de recherche

* Retourner le noeud si la clé est trouvée dans l'arbre.

```python
arbre recherche(clé, arbre)
    tante_que est_non_vide(arbre)
        si clé < clé(arbre)
            arbre = gauche(arbre)
        sinon si clé > clé(arbre)
            arbre = droite(arbre)
        sinon
            retourne arbre
    retourne NULL
```

# Algorithme de recherche, implémentation (live)

\footnotesize

. . .

```C 
typedef int key_t;
typedef struct _node {
    key_t key;
    struct _node* left;
    struct _node* right;
} node;
typedef node* tree_t;
tree_t search(key_t key, tree_t tree) {
    tree_t current = tree;
    while (NULL != current) {
        if (current->key > X) {
            current = current->gauche;
        } else if (current->key < X){
            current = current->droite;
        } else {
            return current;
        }
    }
    return NULL;
}
```

# Exercice (5-10min)

Écrire le code de la fonction

```C 
int tree_size(tree_t tree);
```

qui retourne le nombre total de noeuds d'un arbre et poster le résutat sur
matrix.

Indication: la taille, est 1 + le nombre de noeuds du sous-arbre de gauche
additionné au nombre de noeuds dans le sous-arbre de droite.

. . .

```C
int arbre_size(tree_t tree) {
    if (NULL == tree) {
        return 0;
    } else {   
        return 1 + tree_size(tree->left) 
            + tree_size(tree->right);
    }
}
```

# L'insertion dans un arbre binaire

* C'est bien joli de pouvoir faire des parcours, recherches, mais si on peut
  pas construire l'arbre....

## Pour un arbre lexicographique

* Rechercher la position dans l'arbre où insérer.
* Créer un noeud avec la clé et le rattacher à l'arbre.

# Exemple d'insertions

* Clés uniques pour simplifier.
* Insertion de 5, 15, 10, 25, 2, -5, 12, 14, 11.
* Rappel:
    * Plus petit que la clé courante => gauche,
    * Plus grand que la clé courante => droite.
* Faisons le dessins ensemble

```









```

## Exercice (3min, puis matrix)

* Dessiner l'arbre en insérant 20, 30, 60, 40, 10, 15, 25, -5 


# Pseudocode d'insertion (1/2)

* Deux parties:
    * Recherche le parent où se passe l'insertion.
    * Ajout du fils dans l'arbre.

## Recherche du parent

```
arbre position(arbre, clé)
    si est_non_vide(arbre)
        si clé < clé(arbre)
            suivant = gauche(arbre)
        sinon
            suivant = droite(arbre)
        tant que clé(arbre) != clé && est_non_vide(suivant)
            arbre = suivant
            si clé < clé(arbre)
                suivant = gauche(arbre)
            sinon
                suivant = droite(arbre)
            
    retourne arbre
```

# Pseudocode d'insertion (2/2)

* Deux parties:
    * Recherche de la position.
    * Ajout dans l'arbre.

## Ajout du fils

```
ajout(arbre, clé)
    si est_vide(arbre)
        arbre = noeud(clé)
    sinon
        si clé < clé(arbre)
            gauche(arbre) = noeud(clé)
        sinon si clé > clé(arbre)
            droite(arbre) = noeud(clé)
        sinon
            retourne
```

# Code d'insertion en C (1/2)

## Recherche du parent (ensemble)

. . .

```C
tree_t position(tree_t tree, key_t key) {
    tree_t current = tree;
    if (NULL != current) {
        tree_t subtree = key > current->key ? current->right :
        current->left;
        while (key != current->key && NULL != subtree) {
            current = subtree;
            subtree = key > current->key ? current->right :
            current->left;
        }
    }
    return current;
}
```

[^1]: Copyright cours de mathématiques pendant trop d'années.
