Arbres binaires/Définitions et propriétés
Définition formelle d'un arbre binaire
modifierUn arbre binaire est un arbre dont chaque nœud comporte au plus deux fils. C'est une structure de données qui apparaît souvent dans les problèmes algorithmiques classiques.
Étant donné deux ensembles (valeurs des nœuds) et (valeurs de feuilles), un arbre binaire est un ensemble fini d'éléments qui est :
- soit égal à l’ensemble vide ;
- soit constitué d'une feuille ;
- soit constitué d'une racine , et de deux arbres binaires disjoints et appelés fils gauche et fils droit — on le note .
Remarque : on appelle aussi sous-arbre le fils d'un arbre binaire.
Représentation des arbres binaires
modifierLa représentation d'un arbre binaire se fait de façon hiérarchique, en plaçant au premier niveau la racine, puis au second ses fils droit et gauche… Une flèche d'un nœud vers un nœud signifie que est un fils de .
L'image ci-contre illustre un arbre binaire où les feuilles et les nœuds sont étiquetés par l’ensemble des entiers naturels. La racine de l'arbre est l'entier . On peut ainsi noter l'arbre sous la forme suivante :
- .
On peut parfois rencontrer la notion de nœud interne et de nœud externe : un nœud externe correspond à une feuille, un nœud interne à ce que l’on nomme nœud. Ici, les nœuds indexés par les entiers 4, 7, 8, 9 sont des feuilles.
Notion de parenté
modifierPar analogie avec un arbre généalogique, il semble intéressant de définir la notion de parenté dans un arbre binaire. On dit ainsi que la racine d'un arbre est le père d'un arbre si est un fils (droit ou gauche) de . Par abus de langage, on associera un nœud à sa racine, de sorte que dans l'arbre ci-contre, est le père de et .
Indexation des éléments
modifierProfondeur dans un arbre
modifierDans un arbre , on définit rapidement la notion de chemin de la racine (notée ) vers une feuille de : c’est la donnée d'une suite de nœuds de l'arbre, tels que pour tout , soit le fils de . La longueur de ce chemin est alors égale à , le nombre de nœuds du chemin.
On appelle profondeur d'un nœud ou d'une feuille dans un arbre binaire le nombre d'arêtes qu’il faut parcourir pour atteindre ce nœud à partir de la racine de l'arbre, elle correspond à la longueur du chemin de la racine vers ce nœud.
On appelle hauteur d'un arbre , notée , la profondeur maximale des nœuds de l'arbre : c’est la plus grande longueur d'un chemin de la racine de vers une feuille de l'arbre.
Dans le dernier exemple, les nœuds et ont une profondeur de , la racine une profondeur nulle. La hauteur de l'arbre vaut .
{{{1}}}
On dit qu'un arbre binaire est équilibré si tous les chemins menant de la racine à une feuille ont pour longueur ou .
Remarque : cette définition peut être généralisée au cas d'arbre quelconque en rajoutant la condition suivante : tous les nœuds ont même degré. Dans le cas d'un arbre binaire, les nœuds ont tous pour degré .
Soit un arbre binaire équilibré de hauteur , possédant nœuds et feuilles. Alors vérifie :
- et .
Squelette d'un arbre binaire
modifier