cours_15.md

title: "Arbres"
date: "2023-03-10"

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

. . .

• Chaque nœud est un arbre en lui même.
• La récursivité sera très utile!

Arbre ou pas arbre?

::: columns

:::: column

graph TD;
    1-->2;
    1-->3;
    3-->2;
    3-->4;
    3-->5;

::::

. . .

:::: column

graph TD;
    1-->2;
    1-->3;
    3-->4;
    3-->5;
    3-->6;

::::

:::

Arbre ou pas arbre?

::: columns

:::: column

graph TD;
    1-->2;
    1-->3;
    3-->4;
    3-->5;
    3-->6;
    6-->7;
    7-->3;

::::

. . .

:::: column

graph TD;
    1;

::::

:::

Arbre ou pas arbre?

::: columns

:::: column

graph TD;
    1---2;
    1---3;
    3---4;
    3---5;

::::

. . .

:::: column

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

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

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 nœuds 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 dichotomique (nombre entre 0 et 10).

::: columns

:::: column

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

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

graph TD;
    A-->B;
    A-->C;
    B-->D;
    B-->E;
    B-->F;
    F-->I;
    F-->J;
    C-->G;
    C-->H;
    H-->K;

::::

. . .

:::: column ::::

:::

Autres représentation

• Liste

::: columns

:::: column

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

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 nœud a au plus deux fils: gauche et droite,
• Chaque fils est un arbre.

Comment représenteriez vous une telle structure?

. . .

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

Comment cela s'écrirait en C?

. . .

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

L'arbre binaire

Que se passerait-il avec

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?

. . .

NULL              -> arbre (vide)
<n, arbre, arbre> -> arbre
visiter(arbre)    -> nœud (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

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 nœud (opérateur, opérande).
  • Les feuilles contiennent les opérandes.
  • Les nœuds internes contiennent les opérateurs.

::::

:::

Parcours d'arbres binaires

• Appliquer une opération à tous les nœuds 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

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. Parcours 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

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

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 nœud est visité à la remontée.

Résultat

c - a * b * d + e / f

::::

:::

Et en C?

Live code

\footnotesize

. . .

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¹ de l'algorithme infixe.

Le parcours postfixe

parcours_postfixe(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

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

. . .

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, n+1);
    }
}

Exercice supplémentaire (sans corrigé)

Écrire le code de la fonction

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éments).

Complexité

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

. . .

Exemple: les arbres lexicographiques

• Chaque nœud contient une information de type ordonné, la clé,
• Par construction, pour chaque nœud 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 nœud si la clé est trouvée dans l'arbre.

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

. . .

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

int tree_size(tree_t tree);

qui retourne le nombre total de nœuds d'un arbre et poster le résultat sur matrix.

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

. . .

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