Arbres et arbres binaires

Les arbres sont des types abstraits très utilisés en informatique, notamment quand on a besoin d’une structure hiérarchique des données.

Exemples :

  • arborescence des fichiers et dossiers dans les systèmes de fichiers des OS,
  • expressions arithmétiques : elles peuvent être représentées par des arbres étiquetés par des opérateurs, des constantes et des variables. La structure de l’arbre rend compte de la priorité des opérateurs et rend inutile tout parenthésage.
  • théorie des jeux : certaines stratégies nécessitent l’exploration (partielle) d’arbres de jeu (voir morpion ou puissance 4)
Expressions arithmétiques

Écrire sous forme d’arbre la formule de Pythagore : \(c^2=a^2+b^2\)

Écrire sous forme d’arbre l’expression \(\frac{-b+\sqrt{b^2-4ac}}{2a}\)

 

Définitions et terminologie

Nœuds

Un arbre est constitué de nœuds, reliés entre eux par des arêtes selon une relations pères -fils.

On distingue trois types de nœuds :

  • La racine de l’arbre est l’unique nœud ne possédant pas de parent.
  • les feuilles (ou nœuds externes), éléments ne possédant pas de fils dans l’arbre ;
  • les nœuds internes, éléments possédant des fils (sous-branches).

Le chemin à la racine d’un nœud est la liste des nœuds qu’il faut parcourir depuis la racine jusqu’au nœud considéré.

 

Mesures

La profondeur d’un nœud est la distance (nombre d’arêtes) de la racine au nœud.

La hauteur d’un arbre est la plus grande profondeur d’une feuille de l’arbre.

La taille d’un arbre est son nombre de nœuds, la longueur de cheminement est la somme des profondeurs de chacune des feuilles.

Cette structure de donnée est récursive : chaque nœud est lui même nœud-racine d’un sous-arbre (également appelé branche)

 

Remarque importante : il n’existe pas de définition universelle pour la hauteur d’un arbre et la profondeur d’un nœud dans un arbre.
Dans certains cas la profondeur des nœuds est comptée à partir de 1 et/ou la hauteur est égale au nombre de profondeurs différentes …
Parfois également, la taille d’un arbre ne tient pas compte des feuilles !!

 

Activité

Soit l’arbre suivant :

  • Quelle est la racine de cet arbre ?
  • Donner la hauteur et la taille de cet arbre.
  • Donner le(s) fils du nœud 7.
  • Donner le père du nœud 11
  • Donner toutes les feuilles de cet arbre.

Soir l’arbre suivant :

  • Donner la hauteur et la taille de cet arbre.
  • Donner le(s) fils du nœud R.
  • Donner le père du nœud B.
  • Donner toutes les feuilles de cet arbre.
  • Donner le chemin à la racine du nœud P.

 

Étiquette

La finalité d’un arbre est le plus souvent de structurer des données : chaque nœud peut être identifié par une étiquette.

L’étiquette représente directement la valeur du nœud ou bien une clé associée à une donnée.

Un arbre dont tous les nœuds sont nommés est dit étiqueté.

Exemples :

    • l’arbre ci-dessous est étiqueté avec les entiers entre 1 et 10.
    • l’organisation des fichiers et des dossiers dans un système de fichiers de type UNIX peut également être représenté par un arbre étiqueté avec les noms des fichiers et dossiers :

 

 

 


Arbres binaires

Les arbres binaires (AB) sont des cas particuliers d’arbres où chaque nœud possède au maximum deux fils.

Les fils d’un nœud sont classés : un fils droit et/ou un fils gauche. Ils ne sont pas intervertibles !

 

Arbres complet/filiforme

Il est possible d’avoir des arbres binaires de même taille mais de « forme » très différente :

  • Arbre parfait : tous ses nœuds possèdent exactement 2 fils (sauf les feuilles qui en ont zéro !)

 

  • Arbre équilibré : toutes ses feuilles sont à la même profondeur

 

  • Arbre filiforme (ou dégénéré) : tous ses nœuds possèdent un unique fils (on parle aussi de peigne)

On pourra aussi dire que l’arbre filiforme est déséquilibré alors que l’arbre complet est équilibré.

 

Encadrement de la hauteur

La hauteur d’un arbre filiforme de taille \(n\) est égale à \(n−1\).

La hauteur d’un arbre complet de taille \(n\) est égale à \(\lfloor\log_2(n)\rfloor\)

Exemples des arbres précédents :

\(\log_2(7)=2,8\) : hauteur de l’arbre complet égale à \(2\).

Un arbre filiforme et un arbre complet étant deux cas extrêmes, on peut encadrer la hauteur \(h\) d’un arbre binaire quelconque de taille \(n\) par :

\(\bbox[5px,border:2px solid]{\large{\lfloor\log_2(n)\rfloor\leq h\leq n−1}}\)

 

Encadrement de la taille

De la même manière, on peut encadrer la taille \(n\) d’un arbre binaire que l’on peut obtenir pour une hauteur \(h\) donnée :

\(\bbox[5px,border:2px solid]{\large{h+1\leq n\leq 2^{h+1}-1}}\)

 

Exemple : la taille d’un ardre de hauteur \(3\) est comprise entre \(3+1=4\) et \(2^{3+1}-1=15\)

 

Implémentation

Diagramme de classe

Une instance d’arbre binaire peut être définie par un objet de type Arbre, possédant exactement une racine, de type Nœud.

Chaque nœud possède quant à lui de 0 (feuille) à 2 fils de type Nœud  :

La récursivité  de cette structure est bien visible : un nœud père peut posséder des nœuds fils.

 

En Python

Python ne propose pas de façon native l’implémentation des arbres binaires.

Il est cependant très aisé de définir un arbre binaire en définissant des classes Arbreet  Noeud:

class Arbre:
    def __init__(self, racine = None):
        self.racine = racine # type : Noeud

class Noeud:
    def __init__(self, v, g = None, d = None):
        self.g = g # type Noeud
        self.d = d # type Noeud
        self.v = v

Et on implémente un arbre ainsi :
arbre = Arbre(Noeud("A"))

 

Activité : création d'un arbre

Soit l’arbre dont l’instance est définie par les instructions suivantes :

ng = Noeud(9) 
nd = Noeud(4) 
ng = Noeud(1, ng, nd) 
nd = Noeud(12) 
nd = Noeud(6, ng, nd) 
ngd = Noeud(3) 
ng = Noeud(10, d = ngd) 
arbre = Arbre(Noeud(5, ng, nd))

Représenter cet arbre graphiquement.

Interface

Parmi les méthodes constituant l’interface usuelle d’un arbre, on peut rencontrer :

  • est_feuille() →  bool : renvoie Truesi le nœud est une feuille.
  • branche(noeud)  → Arbre  : renvoie une branche, de type Arbre, dont la racine est le nœud noeud,
  • hauteur()  → int  : renvoie la hauteur de l’arbre,
  • profondeur(noeud)  → int  : renvoie la profondeur du nœud noeud,
  • et toutes les méthodes permettant de visiter les différents nœuds …
Activité : implémentation d'une interface

Continuer l’implémentation de la classe Noeud, en écrivant les méthodes :

  • est_feuille()→  bool : renvoie True  si le nœud est une feuille.
  • branche(noeud)Arbre  : renvoie une branche, de type  Arbre, dont la racine est le nœud noeud.

Suite de l’interface dans parcours d’arbres binaires

 

 

Sources :
https://fr.wikipedia.org/wiki/Arbre_enraciné
https://fr.wikipedia.org/wiki/Arbre_binaire
https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche
http://pageperso.lif.univ-mrs.fr/~francois.denis/algoMPCI/chap1.pdf

 

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *