On souhaite insérer dans une structure de données les différentes hauteurs d'un arbre au fil des années sans y insérer les années. La structure de données la plus adaptée en Python est :
une liste;
un dictionnaire;
une pile;
une file.
Quand on observe l'évolution d'une quantité numérique, ce n'est pas en général pour sortir le premier ou le dernier élément en premier, donc pile et file sont à exclure.
De plus, il n'y a pas d'association donc un dictionnaire est impossible.
Seule la liste convient pour ce genre de problème.
Dans une association, on souhaite enregistrer une liste d'informations pour chaque adhérent : taille, poids, etc. La meilleure structure de données pour cela est :
une liste;
un dictionnaire;
une pile;
une file.
Il s'agit ici d'enregistrer des associations, c'est-à-dire des éléments qui sont rattachés à d'autres (adhérents -> informations), donc le dictionnaire est le plus adapté.
Les clefs seront les adhérents et les valeurs les informations.
Une manière simple de représenter une liste est d'utiliser un tableau de taille fixe dont chaque élément est identifié par son indice.
On peut représenter une liste contenant n éléments avec un tableau L[0..n] comme suit :
La première case du tableau (d'indice 0) contient le nombre d'éléments présents dans la liste.
Les cases suivantes du tableau (d'indices 1 à n) contiennent les éléments de la liste ou bien sont vides.
Ecrire en Python (ou en pseudo-code) le code de la fonction RECHERCHER(L,e) qui recherche l'élément e de la liste L et retourne son index si l'élément est trouvé et Nonecode> sinon.
Les piles sont basées sur le principe LIFO (Last In First Out : le dernier rentré sera le premier à sortir). On retrouve souvent ce principe LIFO en informatique.
Donner les opérations de base que l'ont peut réaliser sur une pile.
On donnera le nom des fonctions avec leur(s) paramètre(s) et la description de ce que fait chaque fonction de base.
Voici les opérations que l'on peut réaliser sur une pile :
CREER_PILE_VIDE() crée et retourne une pile vide.
EMPILER(P,e) : insére l'élément e au sommet de la pile P.
DEPILER(P) : enlève et retourne l'élément au sommet de la pile P.
EST_VIDE(P) : retourne Vrai si la pile P est vide et Faux sinon.
EST_PLEINE(P) : retourne Vrai si la pile P est pleine et Faux sinon.
Les files sont basées sur le principe FIFO (First In First Out : le premier qui est rentré sera le premier à sortir. Ici aussi, on retrouve souvent ce principe FIFO en informatique.
Donner les opérations de base que l'ont peut réaliser sur une file.
On donnera le nom des fonctions avec leur(s) paramètre(s) et la description de ce que fait chaque fonction de base.
Voici les opérations que l'on peut réaliser sur une file :
CREER_FILE_VIDE() crée et retourne une pile vide.
ENFILER(F,e) : insére l'élément e à la queue de la file F.
DEPILER(P) : enlève et retourne l'élément au sommet de la pile P.
EST_VIDE(P) : retourne Vrai si la pile P est vide et Faux sinon.
EST_PLEINE(P) : retourne Vrai si la pile P est pleine et Faux sinon.
Domaine : Arbres 1 - Question n° 8
Quelles sont les principales caractéristiques d'un arbre ?
Les principales caractéristiques d'un arbre sont :
Son nombre de noeuds (la taille)
Sa racine
Son nombre de feuilles
La liste de ses branches
La liste de ses noeuds internes
La liste de ses feuilles
sa hauteur
Donner la définition de l'arité d'un arbre.
L'arité d'un arbre est le nombre maximum de fils qu'un noeud peut avoir.
L'arité d'un arbre binaire non dégénéré est 2.
Donner la définition de la hauteur d'un arbre.
La hauteur d'un arbre est le nombre de noeuds contenus dans sa branche la plus longue sans compter la racine.
On considère l'arbre suivant :
Donner les caractéristiques de cet arbre.
Cet arbre est-il un arbre binaire complet ? Justifier.
L'arbre est bien binaire (arité égale à 2)
L'arbre n'est pas complet : toutes les feuilles n'ont pas la même hauteur (les feuilles E, F et G ont pour hauteur 2 alors que les feuilles I et J ont pour hauteur 3).
Calculer (en détaillant) les mesures suivantes de cet arbre :
Sa taille :
Sa hauteur :
Sa longueur de cheminement : LC
La longueur de cheminement LC est la somme des hauteurs de tous ses noeuds :
Un noeud de hauteur 0 : A
3 noeuds de hauteur 1 : B, C et D
4 noeuds de hauteur 2 : E, F, G et H
2 noeuds de hauteur 3 : I et J
La longueur de cheminement de cet arbre est donc : $LC = 1 \times 0 + 3 \times 1 + 4 \times 2 + 2 \times 2 = 15$.
Sa longueur de cheminement externe : LCE
La longueur de cheminement externe LCE est la somme des hauteurs de tous ses noeuds feuilles:
La longueur de cheminement externe de cet arbre est donc : LCE = H(E) + H(F) + H(G) + H(I) + H(J) = 2 + 2 + 2 + 3 + 3 = 12.
Sa longueur de cheminement interne : LCI
La longueur de cheminement LCI interne est la somme des hauteurs de tous ses noeuds internes.
On a LCI = LC - LCE = 15 - 12 = 3.
Sa profondeur moyenne : PM
La profondeur moyenne PM est le quotient de LC par la taille de l'arbre.
Soit $PM = \frac{LC}{taille} = \frac{15}{10} = 1,5$
Sa profondeur moyenne externe : PME
La profondeur externe PM est le quotient de LCE par le nombre de feuilles NF de l'arbre.
Soit $PME = \frac{LCE}{NF} = \frac{12}{5} = 2,4$
Sa profondeur moyenne interne : PMI
La profondeur interne PMI est le quotient de LCI par (la taille de l'arbre - le nombre de feuilles NF de l'arbre).
Ranger par ordre croissant les 3 profondeurs calculées.
On vérifie que : PMI < PM < PME
Domaine : Arbres 2 - Question n° 11
On nomme h la hauteur d'un arbre binaire.
Donner en fonction de h :
La taille minimale d'un arbre binaire.
L'arbre binaire de taille minimale minimal de hauteur h est un arbre filiforme (une liste) qui contient h + 1 noeuds.
La taille minimale d'un arbre binaire de taille h est h + 1.
La taille maximale d'un arbre binaire.
L'arbre binaire de taille maximale de hauteur h est un arbre binaire complet (une liste) qui contient $ 1 + 2 + 4 + ... 2^h = 2^{h+1} - 1 noeuds.
Comment nomme-t-on un arbre binaire de taille maximale ?
Un arbre binalire de taille maximale est un arbre binaire complet.
Domaine : Arbres 3 - Question n° 12
On définit un arbre de Fibonacci comme un arbre An tel que les sous arbres gauche et droit de An sont respectivement An-1 et An-2, en admettant que A0 est un arbre avec une unique racine et A1 est composé d'une racine ayant un fils gauche et un fils droit.
Voici une représentation sagittale de l'arbre A2.
Donner une représentation sagittale de l'arbre A3.
Les arbres de Fibonacci sont-ils des arbres équilibrés ? Justifier.
Quelle est la formule récurrente qui donne la hauteur d'un arbre en fonction des hauteurs de ses sous arbres gauche et droit ?
Sur votre compte ReplIt traiter le projet nommé Arbres de Fibonacci et hauteur
Rappeler la définition d'un arbre équilibré.
Les arbres de Fibonacci sont-ils équilibrés ? Justifier.
Les arbres de Fibonacci sont équilibrés.
En effet la hauteur de l'arbre de Fibonacci Ak est k.
La différence de hauteur entre Ak et Ak+1 est égale à 1.
Or, comme An a pour fils gauche An-1 de hauteur n - 1 et pour fils droit An-2
de hauteur n - 2, ces deux hauteurs différent de 1.
Donc un arbre de Fibonacci est bien équilibré.
Domaine : Arbres 3 - Question n° 13
On définit un arbre de Fibonacci comme un arbre An tel que les sous arbres droit et gauche de An sont respectivement An-1 et An-2, en admettant que A0 est un arbre avec une unique racine et A1 est composé d'une racine ayant un fils gauche et un fils droit.
Voici une représentation sagittale de l'arbre A2.
Donner une représentation sagittale de l'arbre A3.
Quelle est la formule récurrente qui donne la taille d'un arbre en fonction des tailles de ses sous arbres gauche et droit ?
Sur votre compte ReplIt traiter le projet nommé Arbres de Fibonacci et taille
On nomme Tn la taille de l'arbre de Fibonacci An.
A l'aide de votre programme Python, donner les valeurs de Tn pour des valeurs de n comprises entre 0 et 5.
n
Tn
0
1
1
3
2
5
3
9
4
15
5
25
Conjecturer une relation de récurrence entre Tn, Tn-1 et Tn-2.
La relation de récurrence est : Tn = Tn-1 + Tn-2 + 1
Domaine : Arbres 4 - Question n° 14
Donner la définition d'un arbre binaire de recherche (ABR).
Dessiner tous les arbres binaires de recherche formés des noeuds 1, 2 et 3.
Où se trouve le minimum d'un arbre binaire de recherche
On dispose d'un arbre binaire de recherche A représenté par la liste [racine(A),SAG(A),SAD(A)] où :
racine(A) est la fonction qui retourne la racine de l'arbre A;
SAG(A) est la fonction qui retourne le sous arbre gauche de l'arbre A;
SAD(A) est la fonction qui retourne le sous arbre droit de l'arbre A.
Ecrire sur votre feuille la fonction récursive Python minimum(A) qui retourne le minimum de l'arbre binaire de recherche A.
Domaine : Arbres 4 - Question n° 15
Donner la définition d'un arbre binaire de recherche (ABR).
Dessiner tous les arbres binaires de recherche formés des noeuds 4, 5 et 6.
Où se trouve le maximum d'un arbre binaire de recherche
On dispose d'un arbre binaire de recherche A représenté par la liste [racine(A),SAG(A),SAD(A)] où :
racine(A) est la fonction qui retourne la racine de l'arbre A;
SAG(A) est la fonction qui retourne le sous arbre gauche de l'arbre A;
SAD(A) est la fonction qui retourne le sous arbre droit de l'arbre A.
Ecrire sur votre feuille la fonction récursive Python maximum(A) qui retourne le maximum de l'arbre binaire de recherche A.
