Arbres binaires/Définitions et propriétés

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Définition formelle d'un arbre binaire

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

Définition récursive d'un arbre binaire

Étant donné deux ensembles $N$ (valeurs des nœuds) et $F$ (valeurs de feuilles), un arbre binaire est un ensemble fini d'éléments qui est :

• soit égal à l’ensemble vide $\varnothing$ ;
• soit constitué d'une feuille $f\in F$ ;
• soit constitué d'une racine $n\in N$, et de deux arbres binaires disjoints $g$ et $d$ appelés fils gauche et fils droit — on le note $(n,\ g,\ d)$.

Remarque : on appelle aussi sous-arbre le fils d'un arbre binaire.

Représentation des arbres binaires

Un exemple d'arbre binaire

La 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 $a$ vers un nœud $b$ signifie que $b$ est un fils de $a$.

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 $1$. On peut ainsi noter l'arbre sous la forme suivante :

$(1,(2,4,(5,7,8)),(3,\varnothing ,(6,9,\varnothing )))$.

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é

Par 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 $a_{1}$ est le père d'un arbre $a_{2}$ si $a_{2}$ est un fils (droit ou gauche) de $a_{1}$. Par abus de langage, on associera un nœud à sa racine, de sorte que dans l'arbre ci-contre, $n_{1}$ est le père de $n_{2}$ et $n_{3}$.

Indexation des éléments

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Profondeur dans un arbre

Dans un arbre $A$, on définit rapidement la notion de chemin de la racine (notée $a_{0}$) vers une feuille $a$ de $A$ : c’est la donnée d'une suite $(a_{0},a_{1},\dots ,a_{p}=a)$ de nœuds de l'arbre, tels que pour tout $i\in [1,p]$, $a_{i}$ soit le fils de $a_{i-1}$. La longueur de ce chemin est alors égale à $p$, le nombre de nœuds du chemin.

Définition : profondeur

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.

Définition : hauteur

On appelle hauteur d'un arbre $A$, notée ${\rm {{haut}(A)}}$, la profondeur maximale des nœuds de l'arbre : c’est la plus grande longueur d'un chemin de la racine $a_{0}$ de $A$ vers une feuille de l'arbre.

Dans le dernier exemple, les nœuds $n_{2}$ et $n_{3}$ ont une profondeur de $1$, la racine $n_{1}$ une profondeur nulle. La hauteur de l'arbre vaut $2$.

Début d’un théorème

Théorème

Une arbre binaire $A$ de hauteur $h$ et possédant $n$ nœuds et feuilles vérifie :

$h+1\leq n\leq 2^{h+1}-1$.

Fin du théorème

Démonstration

{{{1}}}

 

Définition : arbre équilibré

On dit qu'un arbre binaire $A$ est équilibré si tous les chemins menant de la racine à une feuille ont pour longueur ${\rm {{haut}(A)}}$ ou ${\rm {{haut}(A)-1}}$.

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é $2$.

Début d’un théorème

Théorème

Soit $A$ un arbre binaire équilibré de hauteur $h$, possédant $n$ nœuds et $f$ feuilles. Alors $A$ vérifie :

$2^{h-1}\leq n\leq 2^{h}-1$ et $2^{h-1}+1\leq f\leq 2^{h}$.

Fin du théorème

Squelette d'un arbre binaire

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?