3-04. Les arbres
Les arbres sont des graphes particuliers ayant une structure appelée structure hiérarchique. Il s’agit d’une structure de données très utilisée en informatique.
Généralités
- Identifier des situations nécessitant une structure de données arborescente.
Un arbre est un type de graphe particulier, non orienté connexe et acyclique.
Vocabulaire associé aux arbres
| Nœud | Sommet d’un graphe de type arbre |
|---|---|
| Taille | Nombre de nœuds |
| Père | Prédécesseur d’un nœud donné |
| Fils | Successeur d’un nœud donné |
| Racine | Nœud particulier n’ayant pas de père, placé au sommet de l’arbre |
| Feuille | Nœud sans fils |
| Sous-arbre de racine N | Arbre des descendants de N |
| Profondeur d’un nœud N | Distance entre N et la racine |
| Niveau | Ensemble de tous les nœuds de même profondeur |
| Hauteur d’un arbre | La profondeur de sa feuille la plus profonde |
Arbre binaire
- Évaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.).
Définition
Un arbre binaire est un cas particulier d’arbre dont chaque nœud a au plus deux fils, que l’on désigne généralement par gauche et droit.
Les arbres sont des structures récursives : les fils d’un nœud sont des arbres (sous-arbre gauche et un sous-arbre droite dans le cas d’un arbre binaire), ces arbres sont eux-mêmes constitués d’arbres…
Hauteur d’un arbre binaire
Soit un arbre binaire ayant 7 nœuds, noté de A à G. On peut avoir deux cas extrêmes :
- L’arbre est filiforme (ou dégénéré). Chaque nœud n’a qu’un seul fils, sauf le dernier qui est une feuille. Sa hauteur sera alors de 6.
- L’arbre est complet. Chaque nœud a deux fils, sauf les feuilles, qui se situent toutes au même niveau (voir ci-dessous). Sa hauteur est alors de 2.
On peut montrer facilement qu’un arbre binaire de taille $*n*$ a une hauteur comprise entre $*n*$–1 et la partie entière de $*\mathrm{log}_2(n)*$, notée $*\lfloor \mathrm{log}_2(n) \rfloor*$.
Arbre binaire
Soit l’arbre binaire suivant :
1. Cet arbre est-il un arbre binaire ? Justifiez votre réponse.
2. Donnez la clé (valeur) de la racine de cet arbre.
3. Quels sont les fils du nœud B.
4. Donnez l’arbre droit du nœud A.
5. Le nœud C est-il une feuille ? Justifiez votre réponse.
6. Donnez la taille de cet arbre.
7. Donnez la profondeur du nœud B (on prendra la profondeur de la racine égale à 0).
8. Donnez la hauteur de cet arbre (on prendra la profondeur de la racine égale à 0).
Correction
Arbre binaire de recherche
Un arbre binaire de recherche est un cas particulier d’arbre binaire, avec les propriétés suivantes :
- il faut que les clés de nœuds composant l’arbre soient ordonnables (on doit pouvoir classer les nœuds, par exemple, de la plus petite clé à la plus grande)
- Si on considère deux nœuds
xetyd’un arbre binaire de recherche et queyest un descendant dex, alorsy.clé≤x.clésiyappartient au sous-arbre gauche dex, ety.clé≥x.clésiyappartient au sous-arbre droit dex.
Arbre binaire de recherche
Soit l’arbre binaire suivant :
1. Expliquez pourquoi cet arbre binaire n'est pas un arbre binaire de recherche.
2. Modifiez cet arbre pour le transformer en arbre binaire de recherche.
Correction
Construire un arbre binaire de recherche
Soit les valeurs suivantes : 14, 22, 8, 47, 42, 13, 1, 24, 33, 74.
Construisez un arbre binaire de recherche à partir de ces valeurs.