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 :
- l’arbre ci-dessous est étiqueté avec les entiers entre 1 et 10.
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 :
\(\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 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 Arbre
et 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"))
Interface
Parmi les méthodes constituant l’interface usuelle d’un arbre, on peut rencontrer :
est_feuille()
→bool
: renvoieTrue
si le nœud est une feuille.branche(noeud)
→Arbre
: renvoie une branche, de typeArbre
, dont la racine est le nœudnoeud
,hauteur()
→int
: renvoie la hauteur de l’arbre,profondeur(noeud)
→int
: renvoie la profondeur du nœudnoeud
,- et toutes les méthodes permettant de visiter les différents nœuds …
Algorithmique
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