Niveau : Terminale générale, enseignement de spécialité NSI
Auteur : Van Zuijlen Stéphan CC BY-NC
Nous rencontrons souvent des schémas qui permettent de mettre en évidence une structure sur des données.
Par exemple : Ce schéma se suffit à lui même pour qui prend la peine de le lire...
De même pour le très classique arbre généalogique
Voici un arbre syntaxique: Un arbre syntaxique représente l’analyse d’une phrase à partir de règles (la grammaire).
Arbre lexicographique : Un arbre lexicographique, ou arbre en parties communes, ou dictionnaire, représente un ensemble de mots. Les préfixes communs à plusieurs mots apparaissent une seule fois dans l’arbre.
Cliquez sur l'image de l'arbre ci-dessus
Editer le diagramme en cliquant sur le crayon
Téléchargez le fichier suivant : Arbre_Lex.xml
Allez sur le site Internet DrawIO
Cliquez sur "Open an existing Diagram" et chargez le fichier téléchargé précédemment.
Ajoutez dans l'arbre lexicographique les mots : malle et portail.
donnez aux 2 mots une couleur différente
Cliquez sur Fichier - Exporter en tant que - SVG... puis Exporter, Télécharger
On peut également représenter les expressions arithmétiques par des arbres étiquetés par des opérateurs, des constantes et des variables. La structure de l’arbre rend compte de la priorité des opérateurs et rend inutile tout parenthésage. Pour l’expression : (y÷2−t)(75 +z) cela donne :
Représenter l’expression : 3 + (7÷3 - 1)3
Les arbres sont très utilisés en informatique, d’une part parce que les informations sont souvent hiérarchisées et peuvent se représenter naturellement sous une forme arborescente, et d’autre part, parce que les structures de données arborescentes permettent de stocker des données volumineuses de façon que leur accès soit efficace.
On peut considérer un arbre comme une généralisation d’une liste car les listes peuvent être représentées par des arbres. Plutôt que de chercher à définir ce qu’est un arbre, nous observerons quelques schémas.
Voici les représentations graphiques :
d’un arbre
une forêt
Attention : Ceci n’est pas un arbre, car il existe un chemin d’un sommet vers lui même (appelé un cycle).
Lorsqu’un sommet se distingue des autres, on le nomme racine de l’arbre et celui-ci devient alors une arborescence (par la suite on utilisera le mot arbre pour une arborescence).
Les 3 arbres ci-dessus représentent la même structure, cependant pour deux d’entre eux, un sommet peut être désigné comme racine. On a l’habitude, lorsqu’on dessine un arbre, de le représenter avec la tête en bas, c’est-à-dire que la racine est tout en haut, et les nœuds fils sont représentés en-dessous du nœud père
Étiquette :
Un arbre dont tous les nœuds sont nommés est dit étiqueté. L’étiquette (ou nom du sommet) représente la "valeur" du nœud ou bien l’information associée au nœud.
Ci-dessous, un arbre étiqueté avec les entiers entre 1 et 10.
Racine, nœud, branche, feuille :
Un arbre est un ensemble organisé de nœuds dans lequel chaque nœud a un père, sauf un nœud que l’on appelle la racine. Si le nœud n’a pas de fils, on dit que c’est une feuille.Les nœuds sont reliés par des branches.
Hauteur d’un nœud :
la hauteur (ou profondeur ou niveau) d’un nœud X est égale au nombre d’arêtes qu’il faut parcourir à partir de la racine pour aller jusqu’au nœud X.
Par convention, la hauteur (ou profondeur)de la racine est égale à 0 (Attention : La définition de la hauteur d’un nœud varie en fonction des auteurs. Pour certains la racine a une hauteur de 1.)
Dans l’exemple ci-contre la hauteur du nœud 9 est de 3 et celle du nœud 7 est de 2.
La hauteur (ou profondeur) d’un arbre est égale à la profondeur du nœud le plus profond.
Dans notre exemple, le nœud le plus profond est de profondeur 3, donc l’arbre est de profondeur 3
Taille d’un arbre :
La taille d’un arbre est égale au nombre de nœuds de l’arbre
Dans notre exemple, l’arbre contient 10 nœuds, sa taille est donc de 10.
Degré d’un nœud, degré d’un arbre :
Le degré d’un nœud est égal au nombre de ses descendants (enfants). Le degré d’un arbre est égal au plus grand des degrés de ses nœuds
Remarques :
Le vocabulaire de lien entre nœuds de niveaux différents et reliés entres eux est emprunté à la généalogie.
Dans notre exemple :
Un arbre dont tous les nœuds n’ont qu’un seul fils est en fait une liste.
Exercice :
Dans l'arbre ci-dessous, déterminez :
la taille : | ||
la hauteur : | ||
le degré de Bob : | ||
3 feuilles : | ||
les fils de tmp : | ||
le parent de music : | ||
un ancêtre de docs : | ||
un descendant de bob : |
Les arbres binaires forment une structure de données qui peut se définir de façon récursive.
Un arbre binaire est :
Les arbres binaires sont utilisés dans de très nombreuses activités informatiques, nous allons étudier et implanter cette structure de données
L’idée est de représenter l’arbre avec un tableau :
La racine suivie de ses fils gauche et droit.
r | a | b |
Puis on rajoute dans l’ordre les fils gauche et droit de a, puis ceux de b.
r | a | b | c | d | e | f |
Remarque :
Chaque nœud se repère par son indice n
dans la liste, son fils gauche se trouvant alors à l’indice
2*n + 1
et son fils droit à l’indice 2*n + 2
.
Exemple :
Le nœud "b"
est à l’indice n=2
son fils gauche se trouve alors à l’indice 5
et son fils droit à l’indice 6
.
Si un nœud n’a pas de fils on le précise en mettant ’None
’ à sa place. Notre arbre est alors représenté par le tableau :
['r','a','b','c','d','e','f',None,None,None,None,None,None,None,None]
Quelle taille doit avoir le tableau ?
Cet arbre est complet (tous les noeuds in-ternes ont deux fils). Il possède 3 niveaux, sa hauteur ou profondeur est donc de 2.
Donc la taille du tableau sera de : 20+ 21+ 22+ 23= 24−1 = 15
il faut compter le nombre de noeuds, y compris les noeuds "fantômes" des feuilles
Exercice 1 :
Quelle devra être la taille du tableau ?
Écrire le tableau représentant cet arbre :
Quelle propriété ont les indices des fils gauches et droits ?
Voici un tableau représentant un arbre binaire : ['*','-',5,2,6,None,None,None,None,None,None,None,None,None,None]
Que peut il représenter ?
Voici un code Python qui crée la liste représentant l’arbre de l’exercice 1 :
Créer les fonctions suivantes :
Arbre_vide(arbre)
qui retourne vrai si l’arbre est vide.Enfants(arbre,noeud)
qui retourne les enfants d'un noeud sous la forme d'un uplet (fg,fd).Fils_gauche(arbre,noeud)
qui retournent le fils gauche d’un noeud et son
homologue Fils_droit(arbre,noeud)
s’ils existent.Racine(arbre,noeud)
qui retourne vrai si le noeud est la racine de
l’arbre.Est_feuille(arbre,noeud)
qui retourne vrai si le noeud est une feuille.Parent(arbre,noeud)
qui retourne le parent du noeud ou False si c'est la racineFrere(arbre,noeud)
qui retourne vrai si le noeud a un frère gauche ou droit
pour
et une liste de noeud=['I','L','O','S']
Aides :
None
.n = arbre.index(noeud)
permet de trouver l'indice n
du noeud dans la liste arbre
.arbre = ['L', 'A', 'I', 'B', 'i'...]
en exécutant le code n = arbre.index('B')
alors n
sera égal à 3
.n
du noeud, on pourra facilement trouver l'indice du fils gauche et droit (formule du cours).fg=2*n+1
est une équation si on recherche le parent (n
), il faut isoler la variable n
de l'équation.
Attention l'indice n
doit toujours être un entier.None
.Résulat souhaité :
Arbre vide : False Taille du tableau 31 Arbre= ['L', 'A', 'I', 'B', 'i', 'S', 'e', 'O', None, None, 'D', None, 'E', None, 's', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None] ('S', 'e') sont les enfants de I S est le fils gauche e est le fils droit I est racine : False I est une feuille : False L est le parent de I I a un frère : True ('A', 'I') sont les enfants de L A est le fils gauche I est le fils droit L est racine : True L est une feuille : False False est le parent de L L a un frère : False (None, None) sont les enfants de O None est le fils gauche None est le fils droit O est racine : False O est une feuille : True B est le parent de O O a un frère : False (None, 'E') sont les enfants de S None est le fils gauche E est le fils droit S est racine : False S est une feuille : False I est le parent de S S a un frère : True
Comme vous l’avez sans doute constaté, il est assez fastidieux de représenter un arbre avec un unique tableau surtout pour un arbre très profond. L’idée est de représenter l’arbre avec un tableau contenant des tableaux
Cet arbre se représente par le tableau:[’r’,[’a’,[],[]],[’b’,[],[]]]
Exercice
2 :
Écrire le tableau représentant cet arbre
Le code Python ci-dessous, construit l’arbre de l’exercice 2 de manière récursive.
Les fonctions l'exercice 2 sont assez évidentes à écrire puisqu’on a accès directement aux noeuds.
Nous allons nous intéresser à la hauteur de l’arbre, ainsi qu’aux différentes façons de le parcourir :
Calcul de la hauteur de l’arbre :
L’idée est la suivante :
Fonction hauteur (arbre) Paramètres : arbre binaire représenté comme tableau de tableaux [racine , [fg] , [fd] ] et fg=[noeud , [fg] , [fd] ] Retourne un entier : la hauteur de l'arbre Si l’arbre est vide alors renvoyer -1
Sinon
h1←1+hauteur(arbre[1])
h2←1+hauteur(arbre[2])
renvoyer max(h1,h2)
Écrire cette fonction dans le code précédent et vérifier que la profondeur de l’arbre est de 2.
Mofofications
Dans le script précédent, implémenter l’arbre
ci-dessous et faites calculer sa profondeur
Le parcours en largeur :
Le parcours d’un arbre en largeur consiste à partir de la racine on visite ensuite son fils gauche puis son fils droit, puis le fils gauche du fils gauche etc.. Comme le montre le schéma ci-dessous:
Fonction Parcours_Largeur(arbre) Paramètre : un arbre binaire Retourne la liste des sommets d'un parcours en largeur f une file vide l une liste vide Pour chaque noeud dans l'arbre faire enfiler le noeud dans la file
Tant quela longueur de f est >0 defiler f dans une variable tmp Si la longueur de tmp >1 alors empiler tmp[0] dans la l Si tmp[1] n’est pas vide alors enfiler tmp[1] dans f Si tmp[2] n’est pas vide alors enfiler tmp[2] dans f Sinon empiler tmp dans l retourne l
Complétez le fichier de simulation de l'algorithme ci-dessus:
arbre = [ 'r' , ['a',[],[]] , ['b',[],[]] ] | ||||||||
---|---|---|---|---|---|---|---|---|
liste | noeud | tmp |
f |
longueur file >0 |
longueur tmp >1 |
|||
f une file vide |
||||||||
liste une liste vide | ||||||||
pour chaque nœud dans l'arbre | ||||||||
enfiler le noeud dans la file | ||||||||
nœud suivant | ||||||||
enfiler le noeud dans la file | ||||||||
nœud suivant | ||||||||
enfiler le noeud dans la file | ||||||||
Tant que la longueur de la file est >0 | ||||||||
defiler la file dans une variable tmp | ||||||||
Si la longueur de tmp >1 alors | ||||||||
empiler tmp[0] dans la liste | ||||||||
Tant que la longueur de la file est >0 | ||||||||
defiler la file dans une variable tmp | ||||||||
Si la longueur de tmp >1 alors | ||||||||
empiler tmp[0] dans la liste | ||||||||
Tant que la longueur de la file est >0 | ||||||||
defiler la file dans une variable tmp | ||||||||
Si la longueur de tmp >1 alors | ||||||||
empiler tmp[0] dans la liste | ||||||||
Tant que la longueur de la file est >0 | ||||||||
retourne liste |
Implémenter cette fonction dans le code du de l'exercice 2. Si vous avez bien programmé, vous pourez faire fonctionner vos ZY...
On se balade autour de l’arbre en suivant les pointillés
Dans le schéma ci-dessus, on a rajouté des "noeuds fantômes" pour montrer que l’on peut considérer que chaque nœud est visité 3 fois
On peut définir les parcours comme suit :
Écrire les sommets dans un parcours préfixe.
Ce qui correspond à : on liste chaque noeud ayant un fils gauche la seconde fois qu’on le voit et chaque noeud sans fils gauche la première fois qu’on le voit.
Écrire les sommets dans un parcours infixe.
Écrire les sommets dans un parcours suffixe.
Définition :
Voici 3 algorithmes récursifs, dire pour chacun d’entre eux à quel parcours il correspond.
Fonction Parcours_(arbre,l=list()) Paramètres : l'arbre binaire et une liste l vide par défaut retourne la liste l des sommets parcourrus Si L’arbre n’est pas vide alors Parcours_(sous-arbre gauche,l) Parcours_(sous-arbre droit,l) Ajouter La racine de l’arbre à l Retourner l
Fonction Parcours_(arbre,l=list()) Paramètres : l'arbre binaire et une liste l vide par défaut retourne la liste l des sommets parcourrus Si L’arbre n’est pas vide alors Ajouter La racine de l’arbre à l Parcours_(sous-arbre gauche,l) Parcours_(sous-arbre droit,l) Retourner l
Fonction Parcours_(arbre,l=list()) Paramètres : l'arbre binaire et une liste l vide par défaut retourne la liste l des sommets parcourrus Si L’arbre n’est pas vide alors Parcours_(sous-arbre gauche,l) Ajouter La racine de l’arbre à l Parcours_(sous-arbre droit,l) Retourner l
Implémenter ces trois fonctions dans le ci-dessous et vérifier vos réponses des 3 questions précédentes.
Remarque : Tout ce que nous venons de faire peut être fait uniquement avec la variable racine qui est un dictionnaire représentant l’arbre de manière tout aussi efficace que la représentation par tableau de tableaux de arbre1.
Nous allons créer une classe Noeud dont les attributs d’instances seront :
De plus on rajoute une méthode spécifique, qui permet d’afficher la racine du noeud avec la fonction print()
Ci-dessous la classe Noeud et la représentation de l’arbre. (La racine possède deux fils qui sont eux mêmes des noeuds possédant deux fils qui.....)
On aurait pu écrire la représentation de l’arbre sur une seule ligne...mais c’est assez compliqué de ne pas se perdre...
Écrire une méthode EstFeuille qui renvoie vrai si le noeud est une feuille et faux sinon.
La hauteur de l’arbre : Reprenons notre fonction Hauteur(arbre) l'exercice 2
Adaptons là à notre contexte :
Rajouter cette fonction au code précédent et
vérifier que la hauteur de notre arbre RUGBYWOMAN
est bien 3.
Exercice 3.2
Et si on en faisait une méthode...
Généralement pour transformer une fonction en méthode, il suffit de remplacer la variable (arbre ici) par self, cependant du fait de la propriété récursive de la fonction, il faudra en plus s’assurer que les arbres gauche et droit existent.
Voici la méthode :
Exercice 3.3
Rajouter cette méthode au code précédent et
tester là avec la commande : print(arbre.hauteur())
.
Les parcours:
Voici les trois fonctions de parcours :
Exercice 3.4 :
Transformer en méthodes ces trois fonctions.
Remarque :
Vaut-il mieux utiliser une méthode ou une fonction ?
Cela dépend en fait de ce que l’on souhaite faire, dans notre cas, si c’est juste pour afficher les parcours, les méthodes suffisent. Mais si c’est pour faire quelque chose avec les noeuds, une fonction sera plus efficace car nous pourrons stocker ces noeuds dans une liste. Comme le montre le code ci-dessous
L’exercice porte sur les arbres binaires de recherche et la programmation objet. Dans un entrepôt de e-commerce, un robot mobile autonome exécute successivement les tâches qu’il reçoit tout au long de la journée.
La mémorisation et la gestion de ces tâches sont assurées par une structure de données.
1. Dans l'hypothèse où les tâches devraient être extraites de cette structure (pour être exécutées) dans le même ordre qu’elles ont été mémorisées, préciser si ce fonctionnement traduit le comportement d’une file ou d’une pile. Justifier.
En réalité, selon l'urgence des tâches à effectuer, on associe à chacune d’elles, lors de la mémorisation, un indice de priorité (nombre entier) distinct : il n'y a pas de valeur en double.
Plus cet indice est faible, plus la tâche doit être traitée prioritairement.
La structure de données retenue est assimilée à un arbre binaire de recherche (ABR) dans lequel chaque nœud correspond à une tâche caractérisée par son indice de priorité.
Rappel :
Dans un arbre binaire de recherche, chaque nœud est caractérisé par une valeur (ici l'indice de priorité), telle que chaque nœud du sous-arbre gauche a une valeur strictement inférieure à celle du nœud considéré, et que chaque nœud du sous- arbre droit possède une valeur strictement supérieure à celle-ci. Cette structure de données présente l'avantage de mettre efficacement en œuvre l'insertion ou la suppression de nœuds, ainsi que la recherche d'une valeur.
Par exemple, le robot a reçu successivement, dans l’ordre, des tâches d’indice de priorité 12, 6, 10, 14, 8 et 13. En partant d’un arbre binaire de recherche vide, l’insertion des différentes priorités dans cet arbre donne la figure 1.
Figure 1 : Exemple d’un arbre binaire
2. En utilisant le vocabulaire couramment utilisé pour les arbres, préciser le terme qui correspond :
a. au nombre de tâches restant à effectuer, c’est-à-dire le nombre total de nœuds de l’arbre ;
b. au nœud représentant la tâche restant à effectuer la plus ancienne ;
c. au nœud représentant la dernière tâche mémorisée (la plus récente).
3. Lorsque le robot reçoit une nouvelle tâche, on déclare un nouvel objet, instance de
la classe Noeud
, puis on l’insère dans l’arbre binaire de recherche (instance de la
classe ABR
) du robot. Ces 2 classes sont définies comme suit :
a. Donner les noms des attributs de la classe Noeud
.
b. Expliquer en quoi la méthode insere
est dite récursive et justifier rapidement
qu’elle se termine.
c. Indiquer le symbole de comparaison manquant dans le test à la ligne 26 de la méthode insere pour que l’arbre binaire de recherche réponde bien à la définition de l’encadré « Rappel » de la page 6.
d. On considère le robot dont la liste des tâches est représentée par l’arbre de la figure 1. Ce robot reçoit, successivement et dans l’ordre, des tâches d’indice de priorité 11, 5, 16 et 7, sans avoir accompli la moindre tâche entretemps. Recopier et compléter la figure 1 après l’insertion de ces nouvelles tâches.
4. Avant d’insérer une nouvelle tâche dans l’arbre binaire de recherche, il faut s’assurer
que son indice de priorité n’est pas déjà présent.
Écrire une méthode est_present
de la classe ABR
qui répond à la description :
5. Comme le robot doit toujours traiter la tâche dont l’indice de priorité est le plus petit, on envisage un parcours infixe de l’arbre binaire de recherche.
a. Donner l’ordre des indices de priorité obtenus à l’aide d’un parcours infixe de l’arbre binaire de recherche de la figure 1.
b. Expliquer comment exploiter ce parcours pour déterminer la tâche prioritaire.
6. Afin de ne pas parcourir tout l'arbre, il est plus efficace de rechercher la tâche du nœud situé le plus à gauche de l'arbre binaire de recherche : il correspond à la tâche prioritaire.
Recopier et compléter la méthode récursive tache_prioritaire
de la classe ABR
:
7. Une fois la tâche prioritaire effectuée, il est nécessaire de supprimer le nœud correspondant pour que le robot passe à la tâche suivante :
Dessiner alors, pour chaque étape, l'arbre binaire de recherche (seuls les indices de priorités seront représentés) obtenu pour un robot, initialement sans tâche, et qui a, successivement dans l'ordre :
Fond : Texte : Tables : Thème du langage:
Auteur : Van Zuijlen Stéphan
adapté en php par Pascal Hassenforder le 05/01/2021
Mise à jour du 19/01/2024