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)
  
• recherche accélérée : les arbres binaires de recherche permettent de rechercher un élément avec une complexité temporelle considérablement réduite par rapport à un tableau.
• …

Définitions et terminologie

Nœuds et arêtes

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.

L’arité d’un nœud est son nombre de fils.

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

É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 !

Types d’arbres binaires

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 (presque) complet: toutes ses feuilles sont à la même profondeur et les feuilles manquantes sont toutes à droite
  

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

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 :

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 :

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

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

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

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

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 …

Algorithmique

• Parcours d’arbres binaires
• Arbres binaires de recherche

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