Aller au contenu

T1.4.1 Généralités sur les arbres⚓︎

1. Notion d'arbre⚓︎

Un arbre est une structure de données qui permet de représenter des données structurées de façon hiérarchique. On trouve beaucoup d'applications en informatique...

Exemples

Arbre de classification des espèces animales

DOM d'une page web

Arborescence de fichiers

Analyse grammaticale d'une phrase

Analyse d'une expression algébrique \((x+1) \times (3\times y+2)\)

Arbre de jeu

Arbre minimal couvrant (graphes)

Arbre des appels d'une fonction récursive

Vocabulaire

Un arbre est un ensemble de nœuds reliés par des arêtes, de sorte que chaque nœud possède un unique parent, sauf un, appelé racine de l'arbre.

On parle aussi d'arbre enraciné.

Il existe deux types de nœuds:

  • les nœuds internes qui possèdent des successeurs (fils);
  • les feuilles (ou nœuds externes) qui ne possèdent pas de fils.

À chaque sommet est associé une étiquette ou valeur.

Exemples

Dans l'arbre précédent,

  • la racine est le sommet étiqueté A;
  • les nœuds internes sont : B, C, H, K et L;
  • ls feuilles sont : D, E, F, G, I, J, M et N;
  • par exemple, B est le père de C et F;
  • par exemple, L et N sont les fils de K.

2. Sous-arbre⚓︎

En ne considérant que le nœud B et ses descendants, on obtient un nouvel arbre qu'on appelle sous-arbre de racine B.

Structure récursive

On peut donc voir un arbre comme une structure de données récursive (ce sera utile pour les algorithmes utilisant des arbres):

  • soit l'arbre est réduit à un seul nœud, sa racine (cas de base);
  • soit l'arbre est consitué d'une racine R et d'un ensemble de sous-arbres dont les racines sont les fils de R.

3. Caractéristiques⚓︎

Définitions

  • la taille d'un arbre est le nombre de ses nœuds (un arbre sans nœud est un arbre vide, de taille 0);
  • la profondeur d'un nœud est le nombre de nœuds du chemin le plus court vers la racine;
  • un niveau de l'arbre est constitué des nœuds de même profondeur;
  • la hauteur d'un arbre est la plus grande profondeur d'un de ses nœuds. En particulier, un arbre vide a une hauteur de 0 et un arbre réduit à un seul nœud (la racine) a une hauteur de 1.

Différentes définitions de la hauteur

Parfois (dans certains livres ou sujets de bac) on peut trouver une autre définition de la hauteur, comme le nombre d'arêtes du chemin le plus long. Ainsi, un arbre réduit à sa racine a pour hauteur 0, et l'arbre vide a pour hauteur ... -1 .

Il est donc important de bien lire la définition donnée en introduction du problème.

Exercice

Dans l'arbre donné précédemment en exemple, déterminer:

  1. la taille de l'arbre.
  2. la profondeur des nœuds B, J, E, M.
  3. le niveau 3 de l'arbre.
  4. la hauteur de l'arbre.
  1. la taille de cet arbre est 14.
  2. B, J, E, M ont pour profondeurs respectives 2, 3, 4 et 5.
  3. Le niveau 3 de l'arbre est constitué des nœuds C, F, I, J et K.
  4. la hauteur de l'arbre est 5.