Aller au contenu

Arbres

Sont traitées dans cette page les notions des CM n°4 et CM n°5.

Arbres binaires

Vocabulaire sur les arbres binaires

Un arbre est une structure de données hiérarchique où chaque élément, appelé nœud, pointe vers un ou plusieurs enfants. Ils sont représentés de haut en bas.

Un arbre binaire est un arbre où chaque nœud possède au plus deux enfants.

On distingue trois types de nœuds particuliers :

  • La racine (root) qui est le premier nœud situé tout en haut de l'arbre
  • Les feuilles qui sont les nœuds ne possédant pas d'enfant
  • Les nœuds internes sont les nœuds qui ne respectent aucune des deux propriétés précédentes

La distance d'un nœud n par rapport à la racine, notée d(root, n) est la longueur du chemin de root vers le nœud. Cette distance est également appelée profondeur.

La hauteur d'un arbre t est la distance maximale entre la racine et le nœud le plus profond de l'arbre. On la note height(t) = max(d(root, n)).

Structures de base pour l'implémentation des arbres binaires

Pour implémenter des arbres binaires, nous allons définir deux structures qui seront à la base de nos algorithmes par la suite. On se base sur le même modèle que pour les listes chaînées étant donné que nous devons créer une structure pour le nœud, que l'on appellera s_node, et également une structure pour l'arbre, qui se nommera s_tree.

Commençons par définir la structure s_node (ainsi que son type associé par le même temps). Un nœud doit contenir 3 informations : sa valeur (value) qui peut être de n'importe quel type, son enfant de gauche (left) qui est un pointeur sur nœud et son enfant de droite (right) qui est aussi un pointeur sur nœud.

Cela nous donne l'implémentation suivante en langage C de la structure s_node et du type t_node :

typedef struct s_node
{
    struct s_node *left;
    T value; // (1)!
    struct s_node *right;
} t_node;

Maintenant que nous avons notre structure de nœud, intéressons-nous à celle d'un arbre. Cette structure contient tout simplement un pointeur sur la racine de l'arbre, c'est-à-dire un pointeur sur nœud.

On obtient l'implémentation suivante en langage C de la structure s_tree et du type t_tree :

typedef struct s_tree
{
    t_node *root;
} t_tree;
  1. Ici, le champ value peut être de n'importe quel type, que l'on désigne par convention T.

Fonctions générales

Créer un nœud

Lorsque l'on va créer un arbre binaire, une des actions que l'on va très souvent répéter est la création de nœuds. Nous allons donc automatiser cette action en l'implémentant dans une fonction dédiée.

On cherche ici à intégrer une valeur donnée (de n'importe que type) dans un nœud, mais également à affecter aux pointeurs left et right l'adresse NULL.

Le prototype de la fonction est :

t_node *createNode(T val)
Implémentation en langage C 
t_node *createNode(T val)
{
    t_node *n = (t_node *)malloc(sizeof(t_node));

    n -> value = val;
    n -> left = NULL;
    n -> right = NULL;

    return n;
}

Calculer la hauteur d'un arbre (de manière récursive)

Pour rappel, une fonction récursive permet de découper un problème et résoudre des sous-problèmes en s'appelant elle-même. Ici, on distingue deux cas : le cas d'un arbre vide où l'on résout directement le problème, et le cas d'un nœud root qui possède comme enfants deux sous-arbres binaires (découpage en sous-problèmes dans ce cas).

Commençons par décider de la hauteur de l'arbre vide : étant donné que la hauteur de l'arbre contenant un unique nœud (root) est de 0, on va poser la hauteur de l'arbre vide à -1.

Exemple de visualisation

Considérons l'arbre binaire suivant :

graph TB
    A((A))-->B((B))
    A-->C((C))
    C-->D((D))

La fonction récursive va réaliser les actions suivantes pour déterminer la profondeur de l'arbre :

Explication de la récursivité
Explication de la récursivité

À partir de ces données et de la visualisation précédente de la méthode de calcul de cette fonction récursive, on peut implémenter notre fonction en langage C suivant ces deux cas : si la liste est vide, alors la hauteur est de -1, sinon la hauteur est 1 + max(height(enfant_gauche), height(enfant_droite)).

Le prototype de la fonction est :

int nodeHeight(t_node *n)

Attention ! Il ne faut pas oublier d'implémenter également la fonction max qui renvoie le maximum entre deux valeurs ! (Ce n'est pas natif en langage C)

Implémentation en langage C

La fonction nodeHeight qui indique, à partir d'un t_node *, la hauteur du sous-arbre dont il est la racine, peut être implémentée comme ceci :

#define max(a,b) ((a)>(b)?(a):(b)) // (1)!

int nodeHeight(t_node *n)
{
    if (n==NULL)
        return -1;

    int leftheight = nodeHeight(n->left);
    int rightheight = nodeHeight(n->right);
    return 1+max(leftheight,rightheight);
}

Il est également possible d'implémenter une fonction treeHeight() qui initie la récursivité à la racine d'un arbre donné t. On peut l'implémenter comme ceci :

int treeHeight(t_tree t)
{
    return nodeHeight(t.root);
}
  1. Cette ligne crée une macro (substitution de code) max pour trouver le maximum entre deux valeurs. Pour cela, le corps de la macro (entre parenthèses) est composé comme ceci :
    • (a)>(b) : on fait un test de comparaison "a est-il strictement supérieur à b ?"
    • ? : indique un choix basé sur une condition, ici (a)>(b)
    • (a) : si la condition est vraie, alors on renvoie a
    • :(b) : si elle est fausse, alors on renvoie b

Compter le nombre de nœuds d'un arbre binaire (de manière récursive)

Tout d'abord, puisque l'on construit une fonction récursive, déterminons la condition d'arrêt (le cas particulier où le problème est directement résolu). Ici on souhaite compter le nombre de nœuds d'un arbre, or dans le cas d'un arbre vide ce nombre est nécessairement 0. Ce sera donc notre conditon d'arrêt pour ce programme.

Si l'arbre n'est pas vide, alors on va appliquer la récursivité. Pour cela, on compte d'abord le nœud sur lequel on se situe actuellement, puis on vient réaliser une récursion de cette fonction pour le sous-arbre de gauche du nœud, et de même pour le sous-arbre de droite.

À la fin, la fonction va donc retourner un entier comptant le nœud racine additionné à tous les nœuds du sous-arbre gauche et additionné à tous les nœuds du sous-arbre droit.

Le prototype de la fonction est :

int nodeCount(t_node *pn)
Implémentation en langage C

La fonction nodeCount qui indique, à partir d'un t_node *, le nombre de nœuds situés dans le sous-arbre dont il est la racine, peut être implémentée comme ceci :

int nodeCount(t_node *pn)
{
    if (pn==NULL)
        return 0;

    int leftcount = nodeCount(pn->left);
    int rightcount = nodeCount(pn->right);
    return 1+leftcount+rightcount;
}

Il est également possible d'implémenter une fonction treeNodeCount() qui initie la récursivité à la racine d'un arbre donné t. On peut l'implémenter comme ceci :

int treeNodeCount(t_tree t)
{
    return nodeCount(t.root);
}

Rechercher une valeur dans un arbre (de manière récursive)

On souhaite maintenant implémenter une fonction pour savoir si une valeur est stockée dans un arbre ou non. Si oui, on veut récupérer le sous-arbre dont la racine est le nœud qui stocke la valeur cherchée.

On va (une nouvelle fois) passer par la récursivité pour implémenter cela. Commençons par déterminer la condition d'arrêt, ou plutôt devrait-on dire ici les conditions d'arrêt... car il y en a deux ! La première est le cas de la liste vide, où nécessairement on ne pourra pas trouver la valeur recherchée. La deuxième condition est lorsque la valeur du nœud sur lequel on se situe est la valeur recherchée.

La récursion s'applique donc pour tous les autres cas, et on la réalise sur les deux sous-arbres du nœud actuel (left et right).

Le prototype de la fonction est :

t_node *seekNodeValue(t_node *pn, int val)
Implémentation en langage C 
t_node *seekNodeValue(t_node *pn, int val)
{

    t_node *pleft;
    t_node *pright;

    if (pn==NULL) // (1)!
        return NULL;

    if (pn->value == val) // (2)!
        return pn;

    pleft = seekNodeValue(pn->left,val); // (3)!
    if (pleft!=NULL) // (4)!
        return pleft;

    pright = seekNodeValue(pn->right, val); // (5)!
    if (pright != NULL) 
        return pright;

    return NULL; // (6)!
}
  1. Dans ce cas, il s'agit d'un arbre (ou sous-arbre) vide donc on retourne l'adresse NULL.
  2. On vient de trouver la valeur recherchée sur le nœud actuel ! On retourne donc simplement l'adresse de ce nœud.
  3. La valeur n'étant pas sur le nœud actuel, alors on vient explorer le sous-arbre de gauche du nœud actuel en appelant récursivement la fonction. Le résultat de cette recherche est stocké dans le pointeur pleft.
  4. Si le résultat de la recherche précédente n'a pas renvoyé un nœud d'adresse NULL, alors cela signifie que l'on a trouvé la valeur dans le sous-arbre ! L'adresse de cette valeur étant pleft, on retourne simplement cette adresse.
  5. Si la recherche à gauche n'a rien donné, alors on réalise une récursion sur le sous-arbre de droite. (Même principe que pour le sous-arbre de gauche par la suite)
  6. Si aucune des conditions précédentes n'a été satisfaite, cela signifie que la valeur recherchée n'a pas été trouvée dans l'arbre, ni dans le sous-arbre gauche ni dans le sous-arbre droit. La fonction renvoie donc NULL pour indiquer que la valeur n'a pas été trouvée.

Parcours d'un arbre binaire

Parcours en profondeur

Parcourir un arbre en profondeur signifie parcourir l'arbre à partir de la racine et d'aller au plus profond possible avant de remonter.

Exemple général par visualisation

On a l'arbre binaire suivant :

graph TB
    A((A))-->B((B))
    A-->C((C))
    B-->D((D))
    C-->E((E))
    C-->F((F))

On considèrera que l'action sur le nœud est d'afficher sa valeur. Pour chacun des trois types de parcours en profondeur présentés ci-dessous, on utilisera ce même arbre en guise d'exemple.

Concernant l'implémentation en langage C de ces parcours, nous allons à chaque fois définir une première fonction qui prend en paramètre un pointeur sur nœud et qui affiche à l'écran les valeurs dans l'ordre du parcours de l'arbre dont ce nœud est la racine.

Il s'agit d'une fonction récursive, donc on doit définir une condition d'arrêt : si l'adresse du pointeur sur nœud est NULL, alors on ne retourne rien et la récursivité s'arrête.

Nous définirons également une seconde fonction qui permettra d'initialiser la récursivité à la racine d'un arbre donné en paramètre.

Il y a 3 types de parcours en profondeur :

  • Parcours préfixe

    Dans le principe, le parcours se déroule selon les étapes suivantes.

    1. Opération sur le nœud 
2. Récursion à gauche 
3. Récursion à droite
    Exemple de parcours préfixe

    Réalisons le parcours préfixe du graphe présenté dans l'exemple général. Suivons les étapes de ce parcours :

    • On affiche le nœud de départ, qui est A
    • On fait la récursion à gauche, puis on affiche la valeur B
    • On fait la récursion à gauche, puis on affiche la valeur D
    • On fait la récursion à gauche, il n'y a pas d'enfant ; donc on fait la récursion à droite, il n'y pas d'enfant non plus, donc on remonte
    • La récursion à gauche ayant déjà été faite, on fait la récursion à droite, il n'y a pas d'enfant ; donc on remonte
    • Et ainsi de suite...

    Lorsque l'on réalise la récursion vers la gauche, on met une flèche verte. Lorsque c'est vers la droite, on met une flèche rouge. Et si on revient au nœud précédent, on met une flèche bleue. Les cases en vert indiquent l'ordre d'affichage des valeurs lors du parcours.

    On note les étapes successives du parcours sur le graphe comme suit :

    graph TB
    A((A))-- 1 -->B((B))
    A-- 5 -->C((C))
    B-- 2 -->D((D))
    C-- 6 -->E((E))
    C-- 8 -->F((F))
    D -- 3 --> B
    B -- 4 --> A
    E -- 7 --> C
    F -- 9 --> C
    C -- 10 --> A

    AF1(#1) -.-> A
    AF2(#2) -.-> B
    AF3(#3) -.-> D
    AF4(#4) -.-> C
    AF5(#5) -.-> E
    AF6(#6) -.-> F
    style AF1 fill:#DBFCC0
    style AF2 fill:#DBFCC0
    style AF3 fill:#DBFCC0
    style AF4 fill:#DBFCC0
    style AF5 fill:#DBFCC0
    style AF6 fill:#DBFCC0

    linkStyle 0 stroke: green
    linkStyle 1 stroke: red
    linkStyle 2 stroke: green
    linkStyle 3 stroke: green
    linkStyle 4 stroke: red
    linkStyle 5 stroke: blue
    linkStyle 6 stroke: blue
    linkStyle 7 stroke: blue
    linkStyle 8 stroke: blue
    linkStyle 9 stroke: blue

    En fin de compte, on obtient l'affichage suivant :

    A - B - D - C - E - F

    Le prototype de la fonction est :

    void nodePrefixTraversal(t_node* p_n)
    Implémentation en langage C 
    void nodePrefixTraversal(t_node* p_n)
{

    if (NULL == p_n){ //(1)!
        return;
    }

    printf(" %d : ", p_n->value); //(2)!
    nodePrefixTraversal(p_n->left);
    nodePrefixTraversal(p_n->right);
}

    void treePrefixTraversal(t_tree t)
{
    printf("tree [");
    nodePrefixTraversal(t.root);
    printf("]\n");
    return;
}
    1. Si le pointeur sur nœud renvoie à l'adresse NULL, alors on a fini la récursivité.
    2. Dans le cas contraire, on affiche la valeur du nœud puis on réalise la récursion à gauche puis à droite.

  • Parcours infixe

    Dans le principe, le parcours se déroule selon les étapes suivantes.

    1. Récursion à gauche 
2. Opération sur le nœud 
3. Récursion à droite
    Exemple de parcours infixe

    Réalisons le parcours infixe du graphe présenté dans l'exemple général. Suivons les étapes de ce parcours :

    • On fait la récursion à gauche
    • On fait la récursion à gauche
    • On fait la récursion à gauche, il n'y a pas d'enfant, donc on affiche la valeur D ; puis on fait la récursion à droite, il n'y a pas d'enfant non plus, donc on remonte
    • La récursion à gauche ayant déjà été faite, on affiche la valeur B ; puis on fait la récursion à droite, il n'y a pas d'enfant ; donc on remonte
    • Et ainsi de suite...

    Lorsque l'on réalise la récursion vers la gauche, on met une flèche verte. Lorsque c'est vers la droite, on met une flèche rouge. Et si on revient au nœud précédent, on met une flèche bleue. Les cases en vert indiquent l'ordre d'affichage des valeurs lors du parcours.

    On note les étapes successives du parcours sur le graphe comme suit :

    graph TB
    A((A))-- 1 -->B((B))
    A-- 5 -->C((C))
    B-- 2 -->D((D))
    C-- 6 -->E((E))
    C-- 8 -->F((F))
    D -- 3 --> B
    B -- 4 --> A
    E -- 7 --> C
    F -- 9 --> C
    C -- 10 --> A

    AF1(#3) -.-> A
    AF2(#2) -.-> B
    AF3(#1) -.-> D
    AF4(#5) -.-> C
    AF5(#4) -.-> E
    AF6(#6) -.-> F
    style AF1 fill:#DBFCC0
    style AF2 fill:#DBFCC0
    style AF3 fill:#DBFCC0
    style AF4 fill:#DBFCC0
    style AF5 fill:#DBFCC0
    style AF6 fill:#DBFCC0

    linkStyle 0 stroke: green
    linkStyle 1 stroke: red
    linkStyle 2 stroke: green
    linkStyle 3 stroke: green
    linkStyle 4 stroke: red
    linkStyle 5 stroke: blue
    linkStyle 6 stroke: blue
    linkStyle 7 stroke: blue
    linkStyle 8 stroke: blue
    linkStyle 9 stroke: blue

    En fin de compte, on obtient l'affichage suivant :

    D - B - A - E - C - F

    Le prototype de la fonction est :

    void nodeInfixTraversal(t_node* p_n)
    Implémentation en langage C 
    void nodeInfixTraversal(t_node* p_n)
{
    if (p_n->left != NULL) nodeInfixTraversal(p_n->left); //(1)!
    if (p_n != NULL) printf(" %c ", p_n->value); 
    if (p_n->right != NULL) nodeInfixTraversal(p_n->right);

    return; //(2)!
}

    void treeInfixTraversal(t_tree t)
{
    printf("tree [");
    nodeInfixTraversal(t.root);
    printf("]\n");
    return;
}
    1. On débute d'abord par la récursion à gauche, puis on affiche et enfin on fait la récursion à droite en vérifiant à chaque fois que la condition d'arrêt ne soit pas respectée.
    2. Si l'on arrive à cette ligne, cela signifie que l'adresse du nœud présent est NULL (ainsi que celles de ses sous-arbres droit et gauche) donc la récursion s'arrête.

  • Parcours postfixe

    Dans le principe, le parcours se déroule selon les étapes suivantes.

    1. Récursion à gauche 
2. Récursion à droite 
3. Opération sur le nœud
    Exemple de parcours postfixe

    Réalisons le parcours infixe du graphe présenté dans l'exemple général. Suivons les étapes de ce parcours :

    • On fait la récursion à gauche
    • On fait la récursion à gauche
    • On fait la récursion à gauche, il n'y a pas d'enfant, donc on fait la récursion à droite, il n'y a pas d'enfant non plus, donc on affiche la valeur D ; puis on remonte
    • La récursion à gauche ayant déjà été faite, on fait la récursion à droite, il n'y a pas d'enfant, donc on affiche la valeur B ; puis on remonte
    • La récursion à gauche ayant déjà été faite, on fait la récursion à droite
    • On fait la récursion à gauche
    • On fait la récursion à gauche, il n'y a pas d'enfant, donc on fait la récursion à droite, il n'y a pas d'enfant non plus, donc on affiche la valeur E ; puis on remonte
    • Et ainsi de suite...

    Lorsque l'on réalise la récursion vers la gauche, on met une flèche verte. Lorsque c'est vers la droite, on met une flèche rouge. Et si on revient au nœud précédent, on met une flèche bleue. Les cases en vert indiquent l'ordre d'affichage des valeurs lors du parcours.

    On note les étapes successives du parcours sur le graphe comme suit :

    graph TB
    A((A))-- 1 -->B((B))
    A-- 5 -->C((C))
    B-- 2 -->D((D))
    C-- 6 -->E((E))
    C-- 8 -->F((F))
    D -- 3 --> B
    B -- 4 --> A
    E -- 7 --> C
    F -- 9 --> C
    C -- 10 --> A

    AF1(#6) -.-> A
    AF2(#2) -.-> B
    AF3(#1) -.-> D
    AF4(#5) -.-> C
    AF5(#3) -.-> E
    AF6(#4) -.-> F
    style AF1 fill:#DBFCC0
    style AF2 fill:#DBFCC0
    style AF3 fill:#DBFCC0
    style AF4 fill:#DBFCC0
    style AF5 fill:#DBFCC0
    style AF6 fill:#DBFCC0

    linkStyle 0 stroke: green
    linkStyle 1 stroke: red
    linkStyle 2 stroke: green
    linkStyle 3 stroke: green
    linkStyle 4 stroke: red
    linkStyle 5 stroke: blue
    linkStyle 6 stroke: blue
    linkStyle 7 stroke: blue
    linkStyle 8 stroke: blue
    linkStyle 9 stroke: blue

    En fin de compte, on obtient l'affichage suivant :

    D - B - E - F - C - A

    Le prototype de la fonction est :

    void nodePostfixTraversal(t_node* p_n)
    Implémentation en langage C 
    void nodePostfixTraversal(t_node* p_n)
{
    if(p_n == NULL)
    {
        return;
    }

    nodePostfixTraversal(p_n->left);
    nodePostfixTraversal(p_n->right);
    printf(" %d :", p_n->value);
}

    void treePostfixTraversal(t_tree t)
{
    printf("tree [");
    nodePostfixTraversal(t.root);
    printf("]\n");
    return;
}

Parcours en largeur

Effectuer un parcours en largueur consiste à parcourir tous les nœuds du niveau 1 au dernier niveau en allant de la gauche vers la droite pour chaque niveau.

Exemple par visualisation

On considère l'arbre binaire suivant :

graph TB
        A((A)) -->B((B))
        A-->C((C))
        B-->D((D))
        C-->E((E))
        C-->F((F))
        E-->G((G))

Avant de réaliser le parcours en largeur, représentons les différents niveaux de l'arbre binaire :

graph TB
        A((A))-->B((B))
        A-->C((C))
        B-->D((D))
        C-->E((E))
        C-->F((F))
        E-->G((G))
        subgraph Niveau 1
        A
        end
        subgraph Niveau 2
        B
        C
        end
        subgraph Niveau 3
        D
        E 
        F
        end
        subgraph Niveau 4
        G 
        end

Puis on lit simplement de gauche à droite les nœuds contenus dans chaque niveau (en allant du premier au dernier niveau), et on obtient notre parcours en largeur dont le résultat d'affichage est :

A - B - C - D - E - F - G

Le parcours en largeur est basé sur une file, dans laquelle on dépose au fur et à mesure les pointeurs sur les nœuds 'enfant' gauche puis droit. On crée ainsi un tableau de valeurs, que l'on peut afficher ensuite, comme pour les parcours en profondeur.

On définit cette structure de file particulière comme suit :

typedef struct s_queue_tab
{
    t_node *values[MAX];
    int first, last;
} t_queue_tab;

On doit donc modifier les fonctions déjà implémentées dans la partie sur les Files en fonction de cette nouvelle définition de structure.

Modification des fonctions sur les files 
void enqueue(t_queue_tab *pq, t_node *val) //(3)!
{
    int pos;
    pos = pq->last % MAX;
    pq->values[pos] = val;
    pq->last = pq->last+1;
}

t_node *dequeue(t_queue_tab *pq) //(1)!
{
    t_node *res;
    int pos = pq->first%MAX;
    res = pq->values[pos];
    pq->first = pq->first+1;
    return res;
}

void displayQueue(t_queue_tab q)
{
    printf(" out <- ");
    for (int cpt = q.first ; cpt < q.last; cpt++)
    {
        printf("%d <- ", q.values[cpt%MAX]->value); //(2)!
    }

    printf("in\n");

    return;
}
  1. Désormais on ne renvoie pas un entier (int) mais un pointeur sur nœud (t_node *).
  2. Il faut rajouter ->value car le tableau stocke des pointeurs sur nœuds, on doit donc à chaque reprise pointer vers la valeur de la structure pointée.
  3. On prend en deuxième paramètre un pointeur sur nœud t_node * et non un entier.

Implémentons désormais la fonction du parcours en largeur. Le prototype de la fonction est :

void BFVisit(t_tree);
Implémentation en langage C 
void BFVisit(t_tree t)
{
    t_node *pcur;
    t_queue_tab visitqueue=createEmptyQueue();
    printf("[");
    if (t.root != NULL)
    {
        enqueue(&visitqueue, t.root); 
        while (isQueueEmpty(visitqueue) == 0) //(1)!
        {
            pcur = dequeue(&visitqueue); //(2)! 
            if (pcur->left != NULL) //(3)!
            {
                enqueue(&visitqueue, pcur->left);
            }
            if (pcur->right != NULL)
            {
                enqueue(&visitqueue, pcur->right);
            }
            printf(" %d :", pcur->value);
        }
    }
    printf("]");
    return;
}
  1. Tant que visitqueue.first != visitqueue.last.
  2. On récupère le premier élément de la file, c'est-à-dire la racine, et on stocke le pointeur sur nœud dans pcur.
  3. Si le sous-arbre gauche du nœud n'est pas vide, alors on l'enfile. Il est positionné à la case suivante de l'emplavement où était stocké le dernier nœud.

Arbres binaires de recherche (BST)

Définition d'un arbre binaire de recherche

C'est un arbre binaire dans lequel il est possible d'effectuer une recherche efficace. On peut y appliquer la recherche dichotomique pour trouver un élément avec une faible complexité si l’arbre est équilibré.

La particularité de ces arbres réside dans leur construction et plus précisément dans l'arrangement des valeurs des nœuds qui le composent. En effet, depuis n'importe quel nœud de cet arbre :

  • Les valeurs stockées dans son sous-arbre de gauche sont inférieures à sa valeur.
  • Les valeurs stockées dans son sous-arbre de droite sont supérieures à sa valeur

Opérations générales sur les BST

Tester si un arbre est un BST

Comme toutes les opérations récursives implémentées jusqu'à présent, nous allons créer deux fonctions : une permettant de vérifier à partir d'un nœud quelconque si l'arbre dont il est la racine est un BST, et une autre qui initie la récursivité à partir de la racine d'un arbre donné.

La première fonction renvoie ici un entier : 1 si l'arbre est un BST, 0 sinon. On a 3 conditions d'arrêt possibles :

  • Si l'arbre est vide, alors on retourne 1 (par définition un arbre vide est un BST)
  • Si la valeur de l'enfant gauche est supérieure à la valeur du nœud où l'on se trouve, alors on retourne 0
  • Si la valeur de l'enfant droit est inférieure à la valeur du nœud où l'on se trouve, alors on retourne 0

Le prototype de la fonction est :

int isNodeBST(t_node *pn)
Implémentation en langage C 
int isNodeBST(t_node *pn)
{
    if (pn == NULL)
    {
        return 1;
    }
    if (pn->left != NULL)
    {
        if (pn->value < pn->left->value)
        {
            return 0;
        }
    }
    if (pn->right != NULL)
    {
        if (pn->value > pn->right->value)
        {
            return 0;
        }
    }

    return isNodeBST(pn->left) && isNodeBST(pn->right);

}

int isBST(t_tree t)
{
    return isNodeBST(t.root);
}

Insertion d'un nœud dans un BST

Cette fois, nous implémentons une unique fonction itérative pour cette action. Nous insérerons uniquement des valeurs qui ne sont pas déjà présentes dans le BST mis en paramètre, et cette insertion se fera toujours en tant que feuille.

En respectant les règles de construction d'un BST énoncées précédemment, on réalise l'insertion comme indiqué dans la visualisation suivante.

Exemple d'insertion d'une valeur dans un BST
Exemple d'insertion d'une valeur dans un BST

Le prototype de la fonction est :

void insertBST(t_tree *pt, int value)
Implémentation en langage C 
void insertBST(t_tree *pt, int value)
{
    t_node *pn = createNode(value);
    t_node *cur;
    t_node *father;

    if (pt->root == NULL)
    {
        pt->root = pn;
    }
    else
    {
        cur = pt->root;
        while (cur != NULL)
        {
            father = cur;
            if (pn->value > cur->value)
            {
                cur = cur->right;
            }
            else
            {
                cur = cur->left;
            }
        }
        if (pn->value > father->value)
        {
            father->right = pn;
        }
        else
        {
            father->left = pn;
        }
    }
    return;
}

Recherche d'un élément dans un BST

Chercher une valeur revient en fait à chercher le nœud qui la stocke. On écrira donc une fonction itérative qui retourne le pointeur sur le nœud qui stocke cette valeur, plutôt que cette valeur elle-même.

Le prototype de la fonction est :

t_node *searchBST(t_tree tree, int val)
Implémentation en langage C 
t_node *searchBST(t_tree tree, int val)
{
    t_node *pn = tree.root;
    while (pn != NULL)
    {
        if (pn->value == val)
        {
            return pn;
        }
        else if (pn->value > val)
        {
            pn = pn->left;
        }
        else
        {
            pn = pn->right;
        }
    }
    return NULL;
}

Catégories d'arbres binaires

4 types d'arbres binaires

  • Un arbre strict ou localement complet est un arbre où tous les nœuds ont 0 ou 2 enfants.
  • Un arbre parfait est un arbre strict où toutes les feuilles sont au même niveau de profondeur.
  • Un arbre binaire complet est un arbre où tous les niveaux sont remplis, sauf éventuellement le dernier où les feuilles sont alignées le plus à gauche possible.
  • Un arbre dégénéré est un arbre dont chaque nœud a au plus un enfant (c'est la même chose qu'une liste chaînée).

Complexité des BST

La structure de données BST est adaptée à une recherche efficace :

  • Il peut utiliser une méthode dichotomique pour trouver une valeur avec une faible complexité si l'arbre est équilibré.
  • Le meilleur cas est un arbre parfait ou un arbre complet.
  • Le pire cas est un arbre dégénéré (c'est-à-dire une liste).

Tester si un arbre est parfait

Soit mytree un arbre de hauteur H et stockant un nombre de nœuds N. L'arbre mytree est dit "parfait" si N = 2^(H+1)-1.

Implémentation en langage C 
int isPerfectTree(t_tree t)
{
    return ((intpow(2,treeHeight(t)+1)-1)==treeNodeCount(t));
}

Tester si un arbre est dégénéré

Soit un arbre de hauteur H et stockant un nombre de nœuds N. L'arbre est dit "dégénéré" si N = H + 1.

Implémentation en langage C 
int isDegeneratedTree(t_tree t)
{
    return (treeHeight(t)+1==treeNodeCount(t));
}

Tester si un arbre est strict

Soit un arbre binaire. Cet arbre est strict si chaque cellule pointe :

  • soit pointe vers NULL
  • soit possède exactement 2 enfants
Implémentation en langage C 
int isStrictNode(t_node *pn)
{
    if (pn==NULL)
    {
        return 1;
    }
    if ((pn->left == NULL) != (pn->right == NULL))
    {
        return 0;
    }

    int strictleft = isStrictNode(pn->left);
    int strictright = isStrictNode(pn->right);

    return (strictleft && strictright);
}

int isStrictTree(t_tree t)
{
    return isStrictNode(t.root);
}

Tester si un arbre est équilibré

Un arbre équilibré est un arbre pour lequel, pour tous les nœuds, la différence de hauteur entre son sous-arbre gauche et son sous arbre droit est au maximum égal à 1.

Implémentation en langage C 
int isBalancedNode(t_node *pn)
{
    if (pn==NULL)
    {
        return 1;
    }

    int diffHeight = nodeHeight(pn->left)-nodeHeight(pn->right);

    if (abs(diffHeight) > 1)
    {
        return 0;
    }

    return ((isBalancedNode(pn->left)) && (isBalancedNode(pn->right)));
}

int isBalancedTree(t_tree t)
{
    if (isPerfectTree(t))
    {
        return 1;
    }
    if (isDegeneratedTree(t) && treeNodeCount(t) > 3)
    {
        return 0;
    }

    return isBalancedNode(t.root);
}

Arbres AVL

Définition d'un arbre AVL

Un arbre AVL (Adelson-Velsky and Landis) est un arbre binaire de recherche tel que la hauteur du sous-arbre de gauche et la hauteur du sous-arbre de droite diffèrent d'au plus 1. Ces arbres permettent d'équilibrer un BST de telle façon à optimiser la recherche de valeur.

Un AVL est donc nécessairement un BST, mais l'inverse n'est pas forcément vrai (un BST n'est pas forcément un AVL, comme on l'a vu précédemment).

Facteur d'équilibre

Afin de transformer des arbres en AVL, nous avons besoin du facteur déquilibre : il s'agit, au niveau d'un nœud, de la différence entre la hauteur de son sous-arbre gauche et la hauteur de son sous-arbre droit. On redéfinit donc la structure de nœud de telle sorte à stocker la hauteur height de chaque nœud ainsi que son facteur d'équilibre BF :

typedef struct s_node
{
    int value;
    struct s_node *left, *right;
    int height;
    int BF;
}t_node;

Pour inclure ce facteur dans nos BST, nous allons d'abord écrire une fonction récursive pour stocker dans chaque nœud la hauteur de l'arbre dont il est la racine. La condition d'arrêt est que le nœud soit vide, c'est-à-dire que le pointeur mis en paramètre pointe vers NULL.

Le prototype de la fonction est :

void updateNodeHeight(t_node *pn)
Implémentation en langage C (1/2) 
void updateNodeHeight(t_node *pn)
{
    int hl, hr;
    if (pn != NULL)
    {
        updateNodeHeight(pn->left); //(1)!
        updateNodeHeight(pn->right);

        if (pn->left == NULL) //(2)!
        {
            hl = -1;
        }
        else //(3)!
        {
            hl = pn->left->height;
        }

        if (pn->right == NULL)
        {
            hr = -1;
        }
        else
        {
            hr = pn->right->height;
        }

        pn->height = 1+max(hl, hr); //(4)!
    }
    return;
}
  1. On initie la récursion à gauche puis la récursion à droite pour parcourir tous les nœuds de l'arbre, de telle sorte à obtenir la forme d'un parcours postfixe (récursions avant opération).
  2. Si le sous-arbre de gauche du nœud présent est vide, alors la hauteur gauche hl est définie à -1.
  3. Sinon, on définit la hauteur du sous-arbre de gauche hl directement en allant la récupérer dans la structure.
  4. La hauteur du nœud est définie telle que l'on ajoute 1 à la hauteur maximale de ses 2 sous-arbres.

Désormais, il nous faut créer une nouvelle fonction calculant tous les facteurs d'équilibre des nœuds de l'arbre de telle sorte à remplir les champs BF jusque alors encore vides. La structure du code est très similaire à la fonction void updateNodeHeight(t_node *pn).

Le prototype de la fonction est :

void updateNodeBF(t_node *pn)
Implémentation en langage C (2/2) 
void updateNodeBF(t_node *pn)
{
    int hl, hr;
    if (pn != NULL)
    {
        updateNodeBF(pn->left); 
        updateNodeBF(pn->right);

        if (pn->left == NULL)
        {
            hl = -1;
        }
        else
        {
            hl = pn->left->height;
        }

        if (pn->right == NULL)
        {
            hr = -1;
        }
        else
        {
            hr = pn->right->height;
        }
        pn->BF = hl-hr;
    }
}

Tester si un arbre est un AVL

Nous allons réaliser une fonction récursive possédant 2 conditions d'arrêt :

  • Si le nœud actuel est vide, c'est-à-dire si pn pointe vers NULL, alors il s'agit d'un AVL et on renvoie 1
  • Si le facteur d'équilibre du nœud est inférieur ou égal à -2 ou bien supérieur ou égal à 2, alors ce n'est pas un AVL et on renvoie 0

Le prototype de la fonction est :

int isAVLnode(t_node* pn)
Implémentation en langage C 
int isAVLnode(t_node* pn)
{
    if (pn == NULL)
    {
        return 1;
    }

    if (pn->BF<2 && pn->BF>-2) //(1)!
    {
        return isAVLnode(pn->left)&&isAVLnode(pn->right);
    }
    else
    {
        return 0;
    }
}
  1. Si le facteur d'équilibre est compris entre -2 et 2 non inclus, alors on continue la récursivité de manière à vérifier si les deux sous-arbres du nœud sont aussi des AVL.

Rotation d'arbre à droite

Réaliser une rotation à droite revient à faire une suite d'étapes de transformations d'un arbre. Pour cela, on considère le cas de départ suivant :

Arbre à transformer
Arbre à transformer

On réalise les étapes suivantes :

1. Le sous-arbre de gauche P devient la racine du nouvel arbre
2. On garde le sous-arbre gauche de P ainsi que le sous-arbre droit de Q
3. On place le sous-arbre B comme sous-arbre gauche de Q

On obtient ainsi l'arbre suivant :

Rotation à droite
Rotation à droite

Le prototype de la fonction est :

t_node *rightRotation(t_node *pn)
Implémentation en langage C 
t_node *rightRotation(t_node *pn)
{
    t_node *pivot = pn->left;
    pn->left = pivot->right;
    pivot->right = pn;
    pn = pivot;
    return pn;
}

Rotation d'arbre à gauche

Réaliser une rotation à droite revient à faire une suite d'étapes de transformations d'un arbre. Pour cela, on considère le cas de départ suivant :

Arbre à transformer
Arbre à transformer

On réalise les étapes suivantes :

1. Le sous-arbre de droite Q devient la racine du nouvel arbre
2. On garde le sous-arbre gauche de P ainsi que le sous-arbre droit de Q
3. On place le sous-arbre B comme sous-arbre droit de P

On obtient ainsi l'arbre suivant :

Rotation à gauche
Rotation à gauche

Le prototype de la fonction est :

t_node *leftRotation(t_node *pn)
Implémentation en langage C 
t_node *leftRotation(t_node *pn)
{
    t_node *pivot = pn->right;
    pn->right = pivot->left;
    pivot->left = pn;
    pn = pivot;
    return pn;
}

Équilibrer un arbre

Pour transformer un arbre en AVL, on réalise des rotations selon les facteurs d'équilibre de chaque nœud. On se réfère ainsi au tableau ci-dessous pour la gestion complète d'un AVL :

Tableau des transformations symétriques
Tableau des transformations symétriques

Rotations doubles

L'équilibrage doit donc être fait lorsqu'un nœud a un facteur d'équilibre de +2 ou -2. En fonction des facteurs d'équilibre d'un de ses nœuds fils, il faut appliquer soit une rotation simple, soit une rotation double.

Il y a deux types de rotations doubles que nous allons implémenter ici :

  1. Double rotation gauche : rotation à droite sur le sous-arbre droit du nœud puis rotation à gauche sur le nœud
  2. Double rotation droite : rotation à gauche sur le sous-arbre gauche du nœud puis rotation à droite sur le nœud

Les prototypes de ces deux fonctions sont :

t_node *doubleLeftRotation(t_node *pn)
t_node *doubleRightRotation(t_node *pn)
Implémentation en langage C (Double rotation gauche) 
t_node *doubleLeftRotation(t_node *pn)
{
    pn->right =rightRotation(pn->right);
    pn = leftRotation(pn);
    return pn;
}
Implémentation en langage C (Double rotation droite) 
t_node *doubleRightRotation(t_node *pn)
{
    pn->left = leftRotation(pn->left);
    pn = rightRotation(pn);
    return pn;
}