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ée 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 cette arbre:

On donne l'arbre suivant :

  1. Quelle est la racine de cette 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 cette 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 :

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 cette 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 a racine et la feuille la plus éloignée :

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 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)]
        
# A 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 a

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 a

Pour vous aider, chercher une méthode récursive assez simple qui utilise la fonction max.

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 :

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