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 est une structure de données constituée 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$

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œud consécutifs de la racine vers une feuille.

Dans cet arbre:

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 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.

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 :

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

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 :

Etiqueter 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 :

É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 bianires.

Code de déblocage de la correction :

Exercice 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.

  1. 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 :

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