Fiche de révision : Arbres et structure de données

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.

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

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

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.

• 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)

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

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