Code de déblocage de toutes les corrections :

Demandez le programme !

Les arbres

Nous allons travailler sur la structure de donnée "arbre". Cette structure n'est pas linéaire mais hiérarchique.

Arbre

Un arbre (ou arbre enraciné) est une structure non vide de données constituées de nœuds.

Le sommet de l'arbre s'appelle la racine.

Le nœud $B$ situé sous un nœud $A$ est appelé enfant du nœud $A$ ; le nœud $A$ est aussi appelé parent du nœud $B$.

Un nœud qui ne possède pas d'enfant est appelé feuille.

Les nœuds autre que la racine et les feuilles sont appelés nœuds internes.

Une branche est une suite de nœuds consécutifs de la racine vers une feuille.

Dans cet arbre:

Comme un arbre (enraciné) peut être vu comme un nœud ayant 0, 1 ou plusieurs enfants qui sont eux-mêmes des arbres, la récursivité sera utile pour les étudier.

On donne l'arbre suivant :

  1. Quelle est la racine de cet arbre ?

  2. Combien y-a-t-il de nœuds ?

  3. Combien y-a-t-il de feuilles ?

  4. Combien y-a-t-il de branches ?

  5. L'ensemble des nœuds internes compte combien d'éléments ?

  6. Quels sont les enfants de Gragim ?

Code de déblocage de la correction :

On peut caractériser un arbre par différentes caractéristiques :

On reprend l'arbre de la définition d'un arbre :

On donne l'arbre suivant :

Déterminer l'arité, la taille et la hauteur de cet arbre.

Code de déblocage de la correction :

On donne le répertoire à télécharger ici

Représenter l'arborescence des répertoires et des fichiers à l'aide d'un arbre.

Code de déblocage de la correction :

Arbres binaires

Définitions

Arbres binaires

On appelle arbre binaire une structure hiérarchique qui est soit vide, soit est un arbre d'arité inférieure ou égale à 2.

Les arbres binaires sont constitués de nœuds de 0, 1 ou 2 enfants.

Sous-arbre droit/gauche

Quand un nœud a deux enfants, il possède un sous-arbre gauche et un sous-arbre droit.

Pour un nœud $\alpha$, on notera :

Remarquez bien que les sous-arbres gauche et droit sont aussi des arbres binaires, si bien que les arbres binaires ont naturellement une structure récursive.
C'est la raison pour laquelle, plusieurs fonctions définies par la suite et portant sur les arbres seront définies elles aussi de manière récursive.

Une autre définition distincte (et plus rigoureuse) existe pour les arbres binaires en ne les voyant plus comme un arbre mais de manière récursive :
Un arbre binaire est :

Avec cette définition alternative, un arbre binaire n'est plus un arbre (enraciné) mais surtout la hauteur de l'arbre binaire est modifiée par rapport à celle d'un arbre (enraciné) puisque les feuilles d'un arbre binaire sont alors forcément vides.
Ainsi, avec cette définition, un arbre binaire a un seul nœud (et donc deux fils gauche et droite vides) a une hauteur de 1 au lieu de 0 si vu comme un arbre (enraciné) réduit à sa racine.
Il vous faudra être attentif aux définitions données dans les sujets de bac, en particulier pour celle de hauteur.

Parmi les arbres suivants, lesquels sont binaires?

Code de déblocage de la correction :

Mesures sur les arbres binaires

Les arbres binaires étant particuliers, on peut calculer un certains nombres de caractéristiques d'un arbre binaire.

La taille d'un arbre B correspond au nombre de ses nœuds, elle est définie par :

On donne l'arbre suivant :

Déterminer la taille de cet arbre.

Code de déblocage de la correction :

On peut refaire l'exercice en travaillant de manière récursive.

La hauteur d'un nœud ou la profondeur de $x$ correspond au nombre d'arêtes au-dessus $x$ pour revenir à la racine, elle est définie par :

On donne l'arbre suivant :

Déterminer la hauteur des nœuds $Bob$ et $\alpha$.

Code de déblocage de la correction :

La hauteur d'un arbre B correspond au nombre d'arêtes entre la racine et la feuille la plus éloignée :

Considérons $B$ un arbre binaire non vide.
Nommons $gauche(B)$ le sous-arbre gauche (éventuellement vide) de la racine de $B$ et $droit(B)$ les sous-arbre droit (éventuellement vide) de la racine de $B$.

La $Hauteur$ d'un arbre binaire $B$ non vide peut être définie de manière récursive ainsi :

On donne l'arbre suivant :

Déterminer la hauteur de cet arbre.

Code de déblocage de la correction :

Voici un exercice à faire en autonomie pour tester votre maîtrise sur les fonctions hauteur et taille permettant d'obtenir respectivement la hauteur et la taille d'un objet de type arbre binaire.
Il est important pour le bac de savoir écrire ces deux fonctions.
Vous retravaillerez aussi dans cet exercice les notions de programmation objet et de récursivité.
Cet exercice est issu du site collaboratif de la forge.

Cliquer sur ce lien pour accéder à l'exercice.

La longueur de cheminement d'un arbre B correspond à la somme des hauteurs de chacun des nœuds. :

On donne l'arbre suivant :

Déterminer la longueur de cheminement de cet arbre.

Code de déblocage de la correction :

La longueur de cheminement externe d'un arbre B correspond à la somme des hauteurs de chacune des feuilles :

On donne l'arbre suivant :

Déterminer la longueur de cheminement externe de cet arbre.

Code de déblocage de la correction :

La longueur de cheminement interne d'un arbre B correspond à la somme des hauteurs des nœuds internes de B :

On donne l'arbre suivant :

Déterminer la longueur de cheminement interne de cet arbre.

Code de déblocage de la correction :

Déterminer une relation entre $LC(B)$, $LCE(B)$ et $LCI(B)$.

Code de déblocage de la correction :

La profondeur moyenne d'un arbre B est définie par : $$PM(B)=\frac{LC(B)}{T(B)}$$

On donne l'arbre suivant :

Déterminer la profondeur moyenne de cet arbre.

Code de déblocage de la correction :

La profondeur moyenne externe d'un arbre B est définie par : $$PME(B)=\frac{LCE(B)}{NF}$$

$NF$ désigne ici le nombre de feuilles.

On donne l'arbre suivant :

Déterminer la profondeur moyenne externe de cet arbre.

Code de déblocage de la correction :

La profondeur moyenne interne d'un arbre B est définie par : $$PMI(B)=\frac{LCI(B)}{T(B)-NF}$$

On donne l'arbre suivant :

Déterminer la profondeur moyenne interne de cet arbre.

Code de déblocage de la correction :

La longueur de cheminement et la profondeur moyenne seront utiles pour les algorithmes sur les arbres binaires.

On donne l'arbre $B$ suivant :

Déterminer :

  1. la racine,

  2. le nombre de feuilles,

  3. le nombre de branches,

  4. l'arité,

  5. sa taille $T(B)$,

  6. La hauteur de $B$, $H(B)$,

  7. $LC(B)$,

  8. $LCE(B)$,

  9. $LCI(B)$,

  10. $PM(B)$,

  11. $PME(B)$,

  12. $PMI(B)$.

Code de déblocage de la correction :

renforcement

Arbre binaire de recherche

Un arbre binaire de recherche est un arbre binaire dans lequel l'étiquette d'un nœud est appelé clé et est un entier. L'arbre binaire vérifie deux propriétés :

Quels sont parmi les arbres proposés ci-dessous les arbres binaires de recherche?

Code de déblocage de la correction :

Compléter cet arbre pour que ce soit un arbre binaire de recherche :

Code de déblocage de la correction :

renforcement

Un étiquetage intéressant d'un arbre de recherche est le suivant :

  1. La racine est étiquetée 1.

  2. La premier nœud du sous arbre gauche prend l'étiquette de son père auquel on ajoute un 0.

  3. La premier nœud du sous arbre droit prend l'étiquette de son père auquel on ajoute un 1.

Quelle est l'étiquette de 25 dans l'arbre précédent ?

Code de déblocage de la correction :

Étiqueter comme l'exemple précédent l'arbre suivant :

Code de déblocage de la correction :

On observe que les étiquettes des nœuds de profondeur p sont constituées de p + 1 bits, et sont deux à deux distinctes. On en déduit que toutes les étiquettes des nœuds d'un même arbre sont deux à deux distinctes.

Les étiquettes peuvent être vues comme les écritures de numéros en base 2 : on a ainsi numéroté les différents nœuds de l'arbre.

Pour la propriété suivante vous devez connaître deux notations mathématiques :

  1. La notation $\lfloor x \rfloor$ désigne la partie entière.

    • $\lfloor 1,1 \rfloor=1$.

    • $\lfloor 2,8 \rfloor=2$.

    • $\lfloor -1,1 \rfloor=-2$.

  2. La fonction $log_2$ est une fonction définie sur $]0;+\infty[$ par $log_2(x)=\frac{ln(x)}{ln(2)}$. Elle se nomme logarithme en base 2.

    3. Un résultat à retenir pour la suite : $log_2(2^n)=n$

    Nous aurons l'occasion de réutiliser cette fonction dans le cours A3

Pour un arbre binaire de recherche de hauteur $h$ et de taille $n$ les inégalités : $$\lfloor \log_2(n)\rfloor \leq h\leq n-1$$

Pour démontrer ce résultat nous allons observer le cas où l'arbre est le plus profond et le cas où l'arbre est le moins profond.

Vérifions cette inégalité sur cet arbre :

La taille de cet arbre est 15.

La hauteur est 6.

$log_2(15)=3,9$ à $10^{-1}$ près.

$\lfloor 3,9 \rfloor=3$

On a bien : $3\leq 6 \leq 14$

Vérifier l'exactitude de l'inégalité sur cet arbre:

Code de déblocage de la correction :

Une implémentation de l'objet arbre binaire de recherche en Python

La classe arbre binaire de recherche (ABR) avec Python

class ABR:

    def __init__(self, valeur, fg=None, fd=None):
        self.v = valeur
        self.fg = fg
        self.fd = fd

    def ajoute(self, valeur):
        if self == None:
            return ABR(valeur, None, None)
        elif valeur < self.v:
            return ABR(self.v, ABR.ajoute(self.fg,valeur), self.fd)
        else:
            return ABR(self.v, self.fg, ABR.ajoute(self.fd, valeur))

    def affiche(self):
        if self == None:
            return None
        else :
            return [self.v, ABR.affiche(self.fg), ABR.affiche(self.fd)]
        
# À tester pour exemple
arbre = ABR(25).ajoute(17).ajoute(32).ajoute(5)
arbre.affiche()
# Utiliser l'affichage pour faire une représentation de l'arbre

Implémenter, avec cette implémentation, l'arbre suivant :

Code de déblocage de la correction :

Revenons aux deux fonctions qu'il est essentiel de savoir programmer en python une fois une interface d'arbre donnée.

Écrire en Python une méthode taille qui renvoie la taille d'un arbre binaire.

Vous pouvez vous aider de la relation du cours accessible ici.

Code de déblocage de la correction :

Écrire en Python une méthode hauteur qui renvoie la hauteur d'un arbre binaire.

Pour vous aider, chercher une méthode récursive assez simple qui utilise la fonction max et utilise la structure récursive des arbres binaires.

Code de déblocage de la correction :

Voici un exercice à faire en autonomie pour tester votre maîtrise sur les arbres binaires de recherche.
Vous retravaillerez aussi dans cet exercice sur les tuples au vu de l'implémentation particulière d'un nœud sous forme de tuple proposée dans cet exercice.
Cet exercice est issu du site collaboratif de la forge.

Cliquer sur ce lien pour accéder à l'exercice.

Vous n'avez qu'à traiter la première fonction maximum_abr en utilisant le fait que le maximum d'un ABR se situe toujours à un endroit particulier d'un ABR.

Une fois la fonction correcte obtenue, n'hésitez pas à lire la correction et la remarque liées pour trouver deux manières (récursives et itératives) de traiter le problème.

Exercices du baccalauréat

Cet exercice porte sur les arbres binaires de recherche.

Dans cet exercice, les arbres binaires de recherche ne peuvent pas comporter plusieurs fois la même clé. De plus, un arbre binaire de recherche limité à un nœud a une hauteur de 1.

On considère l'arbre binaire de recherche représenté ci-dessous, où val représente un entier :

    1. Donner le nombre de feuilles de cet arbre et préciser leur valeur (c'est-à-dire leur étiquette).

    2. Donner le sous arbre-gauche du nœud 23.

    3. Donner la hauteur et la taille de l’arbre.

    4. Donner les valeurs entières possibles de val pour cet arbre binaire de recherche.

    2. On suppose, pour la suite de cet exercice, que val est égal à 16.

  2. On considère la classe Noeud définie de la façon suivante en Python : 

    class Noeud:
    def __init__(self, v):
        self.ag = None
        self.ad = None
        self.v = v

    def insere(self, v):
        n = self
        est_insere = False
        while not est_insere :
            if v == n.v:
                # début du bloc 1
                est_insere = True
                # fin du bloc 1
            elif v < n.v:
                # début du bloc 2
                if n.ag != None:
                    n = n.ag
                else:
                    n.ag = Noeud(v)
                    est_insere = True
                # fin du bloc 2
            else:
                # début du bloc 3
                if n.ad != None:
                    n = n.ad
                else:
                    n.ad = Noeud(v)
                    est_insere = True
                # fin du bloc 3

    def insere_tout(self, vals):
        for v in vals:
            self.insere(v)

    1. Représenter l'arbre construit suite à l’exécution de l’instruction suivante : 

      racine = Noeud(18) 
racine.insere_tout([12, 13, 15, 16, 19, 21, 32, 23])

    2. Écrire les deux instructions permettant de construire l’arbre de la figure précédente. On rappelle que le nombre val est égal à 16.

    3. On considère l’arbre tel qu’il est présenté sur la figure précédente. Déterminer l’ordre d’exécution des blocs (repérés de 1 à 3) suite à l’application de la méthode insere(19) au nœud racine de cet arbre.

  3. Écrire une méthode recherche(self, v) qui prend en argument un entier v et renvoie la valeur True si cet entier est une étiquette de l'arbre, False sinon.

Code de déblocage de la correction :

Code de déblocage de la correction :

Coin cybersécurité

Le Bitcoin est une crypto-monnaie (ou crypto-actif) fondée sur la technologie de la Blockchain.
Une seule chaîne de blocs (=blockchain) contient toutes les transactions validées en bitcoins depuis sa création le 3 janvier 2009. En août 2026, en cette chaîne pèse environ 450 Go et environ toutes les 10 minutes, un nouveau bloc d'environ 4 Mo est rajouté à cette chaîne unique.
Comment vérifier qu'une transaction en bitcoin a bien eu lieu au lieu d'analyser l'intégralité des 450 Go ?
C'est là qu'apparaît l'utilisation de l'arbre de Merkle.
Chaque bloc (de 2 Mo environ) contient une en-tête de 80 octets qui contient, entre autres deux empreintes numériques :

Pour simplifier, considérons un bloc avec 7 transactions, notées trans1 à trans7.
Voici les étapes pour obtenir l'arbre de Merkle de ce bloc réduit et son empreinte finale de 32 bits, notée ci-dessous Racine_Merkle_Bloc :

  1. Étape 1 : hachage de chaque transaction :

    Chaque transaction est hachée deux fois par SHA-256 pour obtenir les feuilles de l'arbre de Merkle.
    Ainsi, H1 l'empreinte de trans1 par ce hachage est une feuille de 256 bits soit de 32 octets.

  2. Étape 2 : hachage du niveau supérieur aux feuilles :

    Les feuilles obtenues sont appariées (donc 2 par 2) et le hachage de la paire deux fois par SHA-256 donne le nœud parent des deux feuilles considérées.
    Par exemple, H12 = SHA-256(SHA-256(H1+H2)).
    En cas d'un nombre impair de hash, ici 7, le dernier est dupliqué pour former une pair avec lui-même ; ici : H77 = SHA-256(SHA-256(H7+H7)).

  3. Étape 3 : poursuivre jusqu'à la racine :

    À partir de chaque niveau, on obtient les nœuds parents avec le même principe d'appariement et de double hachage avec SHA_256 (et de duplication du dernier en cas de nombre impair).
    On s'arrête une fois obtenue la racine Racine_Merkle_Bloc.

En pratique, un détenteur de bitcoins utilise une application (portefeuille mobile, ...) pour vérifier l'inclusion d'une transaction sans télécharger une copie de la blockchain en entier.
Avec la blockchain, un système d'indexation permet d'associer à chaque transaction un identifiant, un bloc et la place de cette transaction dans ce bloc.
Pour vérifier une transaction, l'application interroge une copie de la blockchain complète. Celle-ci localise le bloc contenant la transaction et génère une preuve de Merkle : il identifie la position de la transaction dans l'arbre de Merkle du bloc grâce à l'indexation, puis fournit la racine de Merkle (stockée dans l'en-tête du bloc) ainsi que les hashs frères nécessaires pour reconstruire le chemin de la transaction jusqu'à cette racine.
Avec ces informations, l'application recalcule les hashs successifs en combinant le hash de la transaction avec chaque hash frère, jusqu'à obtenir la racine de Merkle du bloc. Si cette racine recalculée correspond à celle de l'en-tête du bloc, la transaction est bien présente et intacte. Par contre, une différence prouve que la transaction a été modifiée.

Par exemple, pour vérifier la transaction trans3, il suffit à l'application de recevoir les informations suivantes : H4, H12 et H5677 ainsi que Racine_Merkle_Bloc.
En effet, à partir de la transaction à vérifier trans3, l'application peut calculer H3.
Avec ce H3 calculé et le H4 reçu, elle peut calculer ensuite H34.
Avec ce H34 calculé et le H12 reçu, elle peut calculer ensuite H1234.
Avec ce H1234 calculé et le H5677 reçu, elle peut calculer ensuite Racine_Merkle_Bloc puis comparer avec l'empreinte attendue.

  1. Déterminer les empreintes (les hashs frères) que doit recevoir l'application pour vérifier que la transaction trans6 est bien dans le bloc (sans modification) ?

  2. Déterminer le nombre d'empreintes à transmettre pour vérifier qu'une transaction apparaît bien telle quelle dans un arbre de Merkle possédant 2000 feuilles.

  3. Sachant que chaque empreinte possède 32 octets, déterminer le nombre d'octets à transmettre pour vérifier l'appartenance d'une transaction à un bloc usuel d'environ 2000 transactions et d'environ 2Mo.

  4. Quel est le rapport d'économie de transfert permis par ce mécanisme de preuve de Merkle par rapport à la transmission de tout le bloc ?

  5. Peut-on falsifier une preuve de Merkle ?

Code de déblocage de la correction :

Renforcement

On donne l'arbre $B$ suivant :

Déterminer :

  1. la racine,

  2. le nombre de feuilles,

  3. le nombre de branches,

  4. l'arité,

  5. sa taille $T(B)$,

  6. La hauteur de $B$, $H(B)$,

  7. $LC(B)$,

  8. $LCE(B)$,

  9. $LCI(B)$,

  10. $PM(B)$,

  11. $PME(B)$,

  12. $PMI(B)$.

Code de déblocage de la correction :

Compléter cet arbre pour que ce soit un arbre binaire de recherche :

Code de déblocage de la correction :

Savoir faire et Savoir

Licence Creative Commons
Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International

▲