GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Implémentations d'un arbre ======

On trouve diverses options selon la façon dont on choisit de stocker les liens entre nœuds.

===== Les nœuds pointent sur leurs enfants =====

Un arbre est composé de nœuds. Chaque nœud peut contenir des données et avoir des enfants. Dans le cas des **arbres binaires**, il ne peut y avoir que deux enfants mais en général il peut y en avoir plus.

=== Dictionnaire ===

Cas où chaque nœud contient les attributs a, b, c, ... Les nœuds peuvent avoir plus de 2 enfants.

<code python>
node = {
    "a":...,
    "b":...,
    "c":...,
    etc
    "children": [tableaux contenant les enfants]
}
</code>

Une variante.

<code python>
node = {
    "data": {"a":..., etc },
    "children": [ ... ]
}
</code>

Et dans un cas avec seulement 2 enfants :

<code python>
node = {
    "data": {"a":..., etc },
    "child_left": ...,
    "child_right": ...
}
</code>

<WRAP important>Pour une première approche, utiliser un dictionnaire est possible. Mais ce n'est pas très raisonnable d'un point de vue théorique : En effet, un arbre est une structure de base qui doit pouvoir être implémentée avec des structures élémentaires. Python nous fournit le dictionnaire ce qui nous donne l'illusion que c'est une structure simple. En vérité, le dictionnaire est une table de hachage et est plus complexe dans son fonctionnement que l'arbre !</WRAP>

=== Tableau ===

Cette option est possible mais pas tellement lisible :

<code python>
node = [
    valeur de a,
    valeur de b,
    valeur de c,
    ...,
    [tableaux contenant les enfants]
]
</code>

=== Objet ===

C'est la meilleure solution car elle permet de faire ce que l'on veut.

<code python>
class Node:
    def __init__(self, a, b, c,...):
        self.a = a
        self.b = b
        self.c = c
        children = []
    def add_child(c):
        children.append(c)
        # il faut faire attention avec l'enfant ajouté :
        # un nœud ne peut pas être enfant de lui-même,
        # un nœud ne peut pas être son propre ancêtre !
</code>

=== Quand il n'y a pas d'objets ===
Certains langages non orientés objet comme C permettent de définir des types de données personnalisables : des ''struct''. On définira :

<code c>
typedef struct Node Node; // un peu verbeux. Permet de prévenir qu'il y aura un type nommé Node
struct Node
{
    int a;
    int b;
    int c;
    Node *left_child; // pointe vers l'enfant gauche
    Node *right_child; // pointe vers l'enfant droit
};
</code>
Une grande différence entre un ''struct'' et un objet est que le ''struct'' ne peut contenir de méthode. Les fonctions devront donc être à l'extérieur du ''struct''

<code c>
#include <stdbool.h>
#include <stdlib.h>

bool has_left_child(Node *n) {
    if (n == NULL){
        exit(EXIT_FAILURE);
    }
    if (n->left_child != NULL){
        return true;
    } else {
        return false;
    }
}
</code>

<WRAP tip>Pour info :
  * C ne contient pas de type booléen. Pour C, ''0'' est faux et les autres entiers sont vrai. Le type ''bool'' est juste un //sucre syntaxique// qui définit ''true'' à ''1'' et ''false'' à ''0''. C'est défini dans ''stdbool.h''.
  * C n'est pas aussi plaisant que Python : pas question ici d'écrire ''%%return n->left_child != NULL;%%''
  * Un programme C se termine en renvoyant ''0'' en cas de succès et un autre entier en cas d'erreur. On peut modifier la valeur de l'entier d'erreur pour gérer des messages d'erreur. On pourrait donc se contenter de ''exit(1)''. Mais c'est peur parlant alors ''stdlib'' définit la constante ''EXIT_FAILURE'' qui vaut ''1'' et rend le programme plus lisible.
</WRAP>

===== Nœuds numérotés =====

Dans le cas d'un arbre binaire, il est possible de numéroter toutes les positions de l'arbre et donc de placer le nœuds dans un tableau. Un exemple en est donné dans cet [[nsi:sujets:sujet_0:exercice_3|exercice]].

Cela ne fonctionnera que pour un arbre binaire. De plus, si l'arbre n'est pas complet, il faudra réserver en mémoire un tableau avec beaucoup de cases vides.

<WRAP tip>Le second problème se pose moins avec Python puisque les tableaux sont dynamiques et que l'on peut leur ajouter des cases. Toutefois, il parait plus pertinent de se placer dans le cas plus courant où cette possibilité est absente. //N'oubliez pas que, bien que Python soit notre langage favori, on essaie de raisonner de façon plus générale et que nous ne sommes pas en spécialité Python !//</WRAP>

<code python>
'''
exemple : on prévoit de la place pour un arbre complet de 10 étages, soit 1023
la première case contient la taille de l'arbre. Cela ne sert pas à grand chose
mais le système de numérotation des noeuds est plus simple si numérote à partir de 1
donc la case 0 du tableau est laissée inutilisée.
'''
arbre = [None]*1024
arbre[0] = 0

def has_left_child(arbre, i_noeud):
    '''
    arbre: tableau représentant l'arbre
    i_noeud: indice du noeud recherché
    renvoie True si le noeud a un enfant gauche
    '''
    assert i_noeud < arbre[0] and arbre[i_noeud] != None, "noeud inexistant"
    i_gauche = 2*i_noeud
    return i_gauche < arbre[0] and arbre[i_gauche] != None

def get_value(arbre, i_noeud):
    '''
    arbre: tableau représentant l'arbre
    i_noeud: indice du noeud recherché
    renvoie la valeur du noeud
    '''
    assert i_noeud < arbre[0] and arbre[i_noeud] != None, "noeud inexistant"
    return arbre[i_noeud]

# etc
</code>    
    
Avec cette approche, comme vous le voyez, on est dans la situation des tableaux : on doit en permanence bien distinguer l'indice d'un nœud et sa valeur, c'est à dire la position et le contenu.

Au contraire, quand on a défini un arbre avec une classe, quand on désigne un objet ''Node'', on désigne le nœud lui même. C'est plus facile à lire.

===== Distinguer arbre et nœuds =====

D'un point de vue théorique, le concept d'arbre se distingue des nœuds. Mais une fois qu'on a défini les relations que les nœuds doivent avoir les uns avec les autres, on sait tout ce qu'il y a à savoir : après tout, un arbre est juste un ensemble de nœuds, si on sait ce qu'est un nœud, on sait ce qu'est un arbre !

Il sera donc fréquent que l'on se contente d'une classe ''Node''.

Pourtant, il peut être utile de définir une classe ''Tree'' qui gère l'ensemble des nœuds. Voici quelques arguments :
  * pour définir des fonctions qui concernent l'ensemble de l'arbre. C'est plus lisible de les placer dans la définition de celui qui gère l'arbre dans son entier que dans la définition des nœuds eux-mêmes ;
  * pour prendre en charge des arbres vides : si tout le fonctionnement est défini dans les nœuds et qu'on n'a pas de nœud, comment faire ?
  * quand il s'agit de modifier le nœud racine. Un exemple ci-dessous :

<code python>
# on suppose un arbre binaire qui contient des lettres
# je ne donne pas la définition des classes, les noms des méthodes sont explictes
r = Node('R') # racine
a = Node('A')
b = Node('B')
c = Node('C')
r.set_left_child(a)
r.set_right_child(b)
a.set_left_child(c)
</code>

On peut donc juger que cela suffit.On atteint l'arbre par sa racine ''r''. Donc, avec cette approche, ''r'' désigne à la fois la racine et l'arbre lui-même. Voyons quel problème cela pose :

<code python>
def fonction_qui_modifie_racine(r, valeur):
    '''
    ajoute un noeud au-dessus de la racine.
    r devient l'enfant gauche de ce noeud.
    '''
    n = Node(valeur)
    n.set_left_child(r)
</code>

Suite à l'exécution de ''%%fonction_qui_modifie_racine(r, 10)%%'' par exemple, ''r'' n'est plus la racine, c'est juste un nœud parmi d'autres dans l'arbre.

<WRAP>Je résume : tout le contenu utile semble concerner les nœuds eux-mêmes. On se dit alors que définir une classe ''Node'' pour les nœuds devrait suffire et qu'il est inutile de créer une classe ''Tree'' pour l'ensemble de l'arbre. On décide donc d'atteindre l'arbre pas sa racine ''r'' et de faire passer par là toute demande concernant l'arbre. La variable désignant la racine est désigne donc en même temps l'arbre.

Mais quand on modifie la racine de l'arbre, l'arbre est toujours le même arbre mais la racine n'est plus la même. Que faire de la variable ''r'' ?

Il y a moyen de contourner ce problème, même sans passer par une classe pour l'arbre. Mais créer une classe est parfois le plus simple.
</WRAP>