Voir la source de Arbres binaires/Définitions et propriétés

{{Chapitre
  | idfaculté = informatique
  | numéro    = 1
  | niveau    = 15
  | précédent = [[../|Sommaire]]
  | suivant   = [[../Implémentation/]]
  | page_liée = Exercices/Arbres en language Caml
}}

== Définition formelle d'un arbre binaire  ==

Un arbre binaire est un [[w:arbre|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
 | titre = Définition récursive d'un arbre binaire
 | contenu =
Étant donné deux ensembles <math>N</math> (valeurs des nœuds) et <math>F</math> (valeurs de feuilles), un arbre binaire est un ensemble fini d'éléments qui est :
* soit égal à l’ensemble vide <math>\varnothing</math> ;
* soit constitué d'une feuille <math>f \in F</math> ;
* soit constitué d'une '''racine''' <math>n \in N</math>, et de deux arbres binaires disjoints <math>g</math> et <math>d</math> appelés '''fils gauche''' et '''fils droit''' — on le note <math>(n,\ g,\ d)</math>.
}}

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

=== Représentation des arbres binaires  ===
[[Fichier:Arbre_binaire_ordonne.svg|Un exemple d'arbre binaire|thumb]]

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

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 <math>1</math>. On peut ainsi noter l'arbre sous la forme suivante :
:<math>(1, (2, 4, (5, 7, 8)), (3,\varnothing, (6, 9, \varnothing)))</math>.

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é  ===

[[Fichier:Arbre_binaire.svg|thumb|100px]]

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 <math>a_1</math> est le '''père''' d'un arbre <math>a_2</math> si <math>a_2</math> est un fils (droit ou gauche) de <math>a_1</math>. Par abus de langage, on associera un nœud à sa racine, de sorte que dans l'arbre ci-contre, <math>n_1</math> est le père de <math>n_2</math> et <math>n_3</math>.

== Indexation des éléments  ==
{{...}}

== Profondeur dans un arbre  ==

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

{{Définition
 | titre = Définition : profondeur
 | contenu =
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
 | titre = Définition : hauteur
 | contenu =
On appelle hauteur d'un arbre <math>A</math>, notée <math>\rm{haut}(A)</math>, la profondeur maximale des nœuds de l'arbre : c’est la plus grande longueur d'un chemin de la racine <math>a_0</math> de <math>A</math> vers une feuille de l'arbre.
}}

Dans le dernier exemple, les nœuds <math>n_2</math> et <math>n_3</math> ont une profondeur de <math>1</math>, la racine <math>n_1</math> une profondeur nulle. La hauteur de l'arbre vaut <math>2</math>.

{{Théorème
 | contenu =
Une arbre binaire <math>A</math> de hauteur <math>h</math> et possédant <math>n</math> nœuds et feuilles vérifie :
:<math>h + 1\leq n \leq 2^{h + 1} - 1</math>.
}}

{{Démonstration déroulante}}

{{Définition
 | titre = Définition : arbre équilibré
 | contenu =
On dit qu'un arbre binaire <math>A</math> est équilibré si tous les chemins menant de la racine à une feuille ont pour longueur <math>\rm{haut}(A)</math> ou <math>\rm{haut}(A) - 1</math>.
}}

'''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é <math>2</math>.

{{Théorème
 | contenu =
Soit <math>A</math> un arbre binaire '''équilibré''' de hauteur <math>h</math>, possédant <math>n</math> nœuds et <math>f</math> feuilles. Alors <math>A</math> vérifie :
:<math>2^{h-1} \leq n \leq 2^h - 1</math> et <math>2^{h-1} +1 \leq f \leq 2^h</math>.
}}

== Squelette d'un arbre binaire  ==
{{...}}


{{Bas de page
  | idfaculté = informatique
  | précédent = [[../|Sommaire]]
  | suivant   = [[../Implémentation/]]
}}