Arbres et structure de données

information-icon

Les premières épreuves du bac 2024 sont pour bientôt ! Consulte notre dossier sur le contrôle continu et le calcul des notes de ton bac pour maximiser ta préparation pour les révisions à ton examen 💪

Caractérisation des arbres

  • Un arbre est une structure de données liant entre eux des nœuds par l’intermédiaire d’arêtes formant des branches.
  • L’organisation des nœuds d’un arbre comporte une dimension hiérarchique.
  • L’élément de base est le nœud racine d’où peuvent partir des arêtes reliant d’autres nœuds.
  • Des nœuds liés entre eux forment des branches.
  • Un nœud enfant est rattaché dans le sens ascendant à un nœud parent.
  • Un sous-arbre est une portion d’arbre à partir d’un nœud qui constitue la racine de ce sous-arbre.
  • Chaque nœud peut stocker une information, appelée valeur ou clé du nœud.
  • Les arbres informatiques sont représentés avec la racine tout en haut du schéma.
  • On dit d’une structure de données organisée comme un arbre qu’elle est « arborescente ».
  • L’organisation du système de fichiers d’un ordinateur est arborescente : les fichiers sont organisés de manière hiérarchique à partir d’une racine.
  • Il existe différentes sortes d’arbres :
  • les arbres généraux qui peuvent posséder un nombre de branches variable ;
  • les arbres binaires et les arbres binaires de recherche qui sont caractérisés par des propriétés particulières.
  • Arbre binaire
  • Un nœud d’un arbre binaire comporte au plus deux sous-arbres enfants appelés « gauche » et « droit ».
  • Certains nœuds non terminaux peuvent n’avoir qu’une seule branche.
  • Les branches d’un arbre ou d’un sous-arbre binaire ne sont pas nécessairement de longueurs égales.
  • Arbre binaire de recherche
  • Un arbre binaire de recherche est un cas particulier d’arbre binaire qui se distingue par le caractère ordonné des nœuds (donc des clés) qui le composent.
  • Le placement des clés est effectué de la façon suivante :
  • les valeurs situées dans le sous-arbre gauche sont nécessairement inférieures à celle de la clé du nœud considéré ;
  • les valeurs situées dans le sous-arbre droit sont nécessairement supérieures à celle de la clé du nœud considéré.
  • On peut mesurer la taille (nombre de nœuds) et la hauteur (nombre de nœuds parcourus sur le plus long chemin) des arbres.
  • Les structures de type arbre sont généralement implémentées en programmation objet, avec un recours fréquent à l’approche récursive pour les méthodes.

Implémentations sur des arbres binaires

  • Notre implémentation des arbres binaires repose sur deux classes distinctes :
  • une classe modélisant des nœuds ;
  • une classe modélisant des arbres binaires à partir des nœuds.
  • Classe Nœud
  • La classe Noeud définit des objets composés d’une valeur (la clé du nœud) et de deux branches, la gauche et la droite, identifiées par leur nœud racine .
  • Les modalités de création d’un nœud sont précisées dans la définition de la méthode spéciale __init__ :
  • seule la valeur de la clé doit être précisée au moment de la création d’un nœud ;
  • ses sous-branches sont initialisées avec l’objet None, qui exprime l’absence de valeur.
  • La création d’un nœud s’effectue ainsi : noeud = Noeud('A').
  • Les attributs de l’objet peuvent ensuite être modifiés.
  • Pour afficher la valeur des clés gauche et droite, il suffit d'employer les commandes suivantes :
    print(noeud.gauche.cle)
    print(noeud.droite.cle)
  • Classe ArbreBinaire
  • La classe ArbreBinaire définit des objets composés initialement d’un nœud racine, auquel pourront être rattachés des nœuds aux différentes sous-branches.
    class ArbreBinaire:

def __init__(self, racine):

self.racine = Noeud(racine)

  • La création d’un arbre binaire s’effectue par initialisation de l’arbre avec un nœud racine.
  • On peut ensuite ajouter des nœuds aux branches du nœud racine, puis aux nœuds qui y sont rattachés, sans limitation de profondeur.
  • Une implémentation plus complète peut intégrer la possibilité d’ajout, de modification et de suppression de nœuds de l’arbre par des méthodes dédiées.
  • Déterminer la taille d’un arbre binaire revient à compter l’ensemble des nœuds composant cet arbre.
  • Pour déterminer la taille d’un arbre binaire, on définit la méthode taille avec comme paramètres :
  • self qui désigne l’instance de la classe ;
  • le nœud à traiter.
  • L’appel initial est effectué avec une valeur par défaut correspondant au nœud racine de l’arbre.
  • Les appels suivants sont effectués de manière récursive sur les sous-arbres (leur nombre de nœuds est ajouté au nœud courant).
  • La récursion s’arrête en l’absence de nœud en sous-arbre. Pour déterminer la hauteur d’un arbre binaire, on définit la méthode hauteur avec comme paramètres :
  • self qui désigne l’instance de la classe ;
  • le nœud à traiter.
  • Les retours des appels récursifs sur les sous-branches gauches et droites sont passés en arguments à la fonction max, laquelle retourne la plus grande des valeurs fournies.
  • On peut ainsi déterminer la hauteur de tout type d’arbre binaire.
  • Parcourir un arbre consiste à explorer l’ensemble de ses nœuds.
  • Il existe trois modes de parcours binaires pour effectuer cette exploration :
  • le parcours préfixe (nœud racine $\rightarrow$ nœud gauche $\rightarrow$ nœud droit) ;
  • le parcours infixe (nœud gauche$\rightarrow$ nœud racine $\rightarrow$ nœud droit) ;
  • le parcours suffixe (nœud gauche$\rightarrow$ nœud droit $\rightarrow$ nœud racine).

Implémentations sur les arbres binaires de recherche

Notre implémentation des arbres binaires de recherche repose sur deux classes distinctes :

  • une classe modélisant des nœuds ;
  • une classe modélisant des arbres binaires de recherche à partir des nœuds.
  • La recherche de clé dans un arbre binaire de recherche exploite le caractère ordonné des clés.
  • Une méthode de recherche qui détermine, de manière récursive à partir du nœud racine, si la clé du nœud courant correspond ou non à la valeur recherchée, peut être définie.
  • Si la clé du nœud courant ne correspond pas, la méthode compare la clé à la valeur recherchée en évaluant si elle y est supérieure ou inférieure.
  • Les clés de l’arbre étant ordonnées, cela permet de déterminer dans quelle sous-arbre la valeur se situe nécessairement, si elle est présente dans l’arbre.
  • En d’autres termes, le caractère ordonné de l’arbre permet d’éliminer un sous-arbre sur deux à chaque étape.
  • L’ajout d’une clé dans un arbre binaire de recherche doit s’effectuer de manière à préserver le caractère ordonné des clés.
  • On effectue donc une démarche similaire à celle de la recherche, pour déterminer l’emplacement auquel la nouvelle clé doit être insérée.
  • L’implémentation doit par ailleurs s’assurer que la clé qu’on cherche à ajouter ne s’y trouve pas déjà.
  • La méthode retourne True en cas d’insertion réussie, et False dans le cas contraire, c'est-à-dire le cas où la valeur est déjà présente dans l'arbre.
  • La position d’insertion de la nouvelle valeur est dictée par la propriété ordonnée de l’arbre binaire de recherche, elle n’est donc pas spécifiée par l’utilisateur·rice mais déterminée par l’algorithme.
  • Dans le cas d’un arbre binaire ou d’un arbre général, l’emplacement serait en revanche choisi par l’utilisateur·rice.